How to Solve: Trapping Rain Water – Complete Guide for FAANG Interviews

How to Solve: Trapping Rain Water – Complete Guide for FAANG Interviews

? Introduction

"This problem appears in 1 out of every 3 onsite interviews—master it, and you prove you can break down complex spatial reasoning into clean, efficient code under pressure."

? WHAT YOU NEED TO KNOW FIRST

Before tackling Trapping Rain Water, ensure you’re fluent in: 1. Two-pointer technique – Used to traverse arrays from both ends while maintaining invariants. 2. Prefix/suffix arrays – Storing cumulative max values to avoid recomputation. 3. Stack-based monotonic sequences – Tracking decreasing/increasing sequences for spatial problems.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK (Mental Checklist)

Run this every time you see a "trapping water" problem:

1. Clarify the problem:
2. Is the input 1D (e.g., elevation map) or 2D (e.g., grid)?
3. Are there negative values? (Assume no unless stated.)

4. What’s the expected output? (Total trapped water, or per-cell water?)

5. Visualize the problem:

6. Sketch the elevation map as a bar chart.

7. Identify "valleys" where water can be trapped.

8. Choose a technique:

9. Two-pointer: Best for 1D, O(1) space.
10. Prefix/Suffix Max: Best for 1D, O(n) space, easy to explain.

11. Monotonic Stack: Best for 2D or when you need per-cell water.

12. Implement the invariant:

13. For two-pointer: left_max and right_max must always be the max heights seen so far from left/right.

14. For prefix/suffix: Precompute left_max[i] and right_max[i] for all i.

15. Compute trapped water:

16. For each cell, water trapped = min(left_max, right_max) - height[i] (if positive).

17. Edge cases:

18. Empty input → return 0.
19. Single bar → return 0 (no water trapped).

20. All bars same height → return 0.

21. Optimize:

22. Can you reduce space? (Two-pointer does this.)
23. Can you handle 2D? (Monotonic stack or BFS.)

? WORKED EXAMPLES

Example 1 – Basic (1D, Two-Pointer)

Problem: Given height = [0,1,0,2,1,0,1,3,2,1,2,1], compute trapped water.

Step-by-Step: 1. Initialize left = 0, right = n-1, left_max = 0, right_max = 0, water = 0. 2. While left < right:
- If height[left] < height[right]:
- If height[left] >= left_max: Update left_max.
- Else: Add left_max - height[left] to water.
- Move left++.
- Else:
- If height[right] >= right_max: Update right_max.
- Else: Add right_max - height[right] to water.
- Move right--. 3. Return water.

Code (Python):

def trap(height):

    if not height:

        return 0

    left, right = 0, len(height) - 1

    left_max, right_max = height[left], height[right]

    water = 0

    while left < right:

        if height[left] < height[right]:

            left += 1

            left_max = max(left_max, height[left])

            water += left_max - height[left]

        else:

            right -= 1

            right_max = max(right_max, height[right])

            water += right_max - height[right]

    return water

Complexity: - Time: O(n) (single pass). - Space: O(1) (two pointers).

Why this works: - The two-pointer approach ensures we always move the pointer with the smaller max, guaranteeing that the other side has a taller wall to trap water.

Example 2 – Medium (Prefix/Suffix Max)

Problem: Same as above, but compute trapped water for each cell.

Step-by-Step: 1. Precompute left_max[i] = max height from 0 to i. 2. Precompute right_max[i] = max height from i to n-1. 3. For each i, trapped water = min(left_max[i], right_max[i]) - height[i] (if positive).

Code (Python):

def trap(height):

    if not height:

        return 0

    n = len(height)

    left_max = [0]  n

    right_max = [0]  n

    left_max[0] = height[0]

    for i in range(1, n):

        left_max[i] = max(left_max[i-1], height[i])

    right_max[-1] = height[-1]

    for i in range(n-2, -1, -1):

        right_max[i] = max(right_max[i+1], height[i])

    water = 0

    for i in range(n):

        water += min(left_max[i], right_max[i]) - height[i]

    return water

Complexity: - Time: O(n) (three passes). - Space: O(n) (two arrays).

Why this works: - Precomputing left_max and right_max allows O(1) lookups for each cell’s bounding walls.

Example 3 – Hard (2D Grid, Monotonic Stack)

Problem: Given a 2D grid where 1 = wall and 0 = empty, compute trapped water.

Step-by-Step: 1. For each row, use a monotonic stack to track walls in decreasing order. 2. When a taller wall is found, pop the stack and compute trapped water between the current wall and the new top of the stack. 3. Water trapped = (min(current_wall, stack_top_wall) - popped_wall) distance.

Code (Python):

def trapRainWater(heightMap):

    if not heightMap or not heightMap[0]:

        return 0

    rows, cols = len(heightMap), len(heightMap[0])

    if rows < 3 or cols < 3:

        return 0

    # Use a min-heap to process boundaries

    heap = []

    visited = [[False for _ in range(cols)] for _ in range(rows)]

    # Push all boundaries into the heap

    for i in range(rows):

        for j in [0, cols-1]:

            heapq.heappush(heap, (heightMap[i][j], i, j))

            visited[i][j] = True

    for j in range(1, cols-1):

        for i in [0, rows-1]:

            heapq.heappush(heap, (heightMap[i][j], i, j))

            visited[i][j] = True

    water = 0

    directions = [(0,1), (1,0), (0,-1), (-1,0)]

    while heap:

        height, x, y = heapq.heappop(heap)

        for dx, dy in directions:

            nx, ny = x + dx, y + dy

            if 0 <= nx < rows and 0 <= ny < cols and not visited[nx][ny]:

                if heightMap[nx][ny] < height:

                    water += height - heightMap[nx][ny]

                visited[nx][ny] = True

                heapq.heappush(heap, (max(height, heightMap[nx][ny]), nx, ny))

    return water

Complexity: - Time: O(mn log(mn)) (heap operations). - Space: O(mn) (visited matrix).

Why this works: - The heap processes cells in order of increasing height, ensuring water is trapped by the smallest bounding wall.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Alright, let’s lock this in. For Trapping Rain Water: 1. Clarify: Is it 1D or 2D? Non-negative heights? 2. Visualize: Sketch the elevation map. Water traps in valleys. 3. Choose:
- 1D: Two-pointer (O(1) space) or prefix/suffix (O(n) space).
- 2D: BFS/heap or monotonic stack. 4. Implement:
- For two-pointer: Track left_max and right_max, move the smaller pointer.
- For prefix/suffix: Precompute max arrays, then min(left_max, right_max) - height[i]. 5. Edge cases: Empty input, single bar, all same height. 6. Optimize: Two-pointer wins for space; prefix/suffix is easier to explain.

You’ve got this. Walk in, sketch the bar chart, pick your approach, and code it cleanly. Now go crush it!

Final Note: This guide is 100% whiteboard-ready. Print it, practice the examples, and internalize the framework. Good luck! ?