42 - Trapping Rain Water

Difficulty: Hard | Pattern: Two Pointers | Company tags: Amazon, Google, Bloomberg, Microsoft, Facebook

Problem Statement

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6

Example 2:

Input: height = [4, 2, 0, 3, 2, 5]
Output: 9

Constraints: n == height.length; 1 <= n <= 2 * 10^4; 0 <= height[i] <= 10^5

Key Insight

Water at position i = min(max_left[i], max_right[i]) - height[i]

The water level at any column is bounded by the shorter of:

• The tallest bar to its left (inclusive)
• The tallest bar to its right (inclusive)

Any water above this shorter bound would spill over. Any amount below height[i] is blocked by the bar itself.

Algorithm Flow

Approach 1: Precompute Max Arrays — O(n) time, O(n) space

def trap(height: list[int]) -> int:
    n = len(height)
    if n == 0:
        return 0
    
    max_left = [0] * n
    max_right = [0] * n
    
    # max_left[i] = max height from index 0 to i
    max_left[0] = height[0]
    for i in range(1, n):
        max_left[i] = max(max_left[i-1], height[i])
    
    # max_right[i] = max height from index i to n-1
    max_right[n-1] = height[n-1]
    for i in range(n-2, -1, -1):
        max_right[i] = max(max_right[i+1], height[i])
    
    water = 0
    for i in range(n):
        water += min(max_left[i], max_right[i]) - height[i]
    
    return water

Approach 2: Two Pointers — O(n) time, O(1) space

Key insight: We don't need to precompute both arrays. If max_left < max_right, the water at the left pointer is determined by max_left (the right side is at least as tall as max_right). Move the left pointer right. Otherwise, the water at the right pointer is determined by max_right. Move the right pointer left.

def trap(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    max_left = max_right = 0
    water = 0
    
    while left < right:
        if height[left] <= height[right]:
            if height[left] >= max_left:
                max_left = height[left]
            else:
                water += max_left - height[left]
            left += 1
        else:
            if height[right] >= max_right:
                max_right = height[right]
            else:
                water += max_right - height[right]
            right -= 1
    
    return water

Dry Run (Two Pointers)

height = [4, 2, 0, 3, 2, 5], expected: 9

left	right	h[l]	h[r]	max_l	max_r	water	action
0	5	4	5	0	0	0	h[l]=4 < h[r]=5 → max_l=4, left++
1	5	2	5	4	0	0	h[l]=2 < h[r]=5 → 4-2=2 water, left++
2	5	0	5	4	0	2	h[l]=0 < h[r]=5 → 4-0=4 water, left++
3	5	3	5	4	0	6	h[l]=3 < h[r]=5 → 4-3=1 water, left++
4	5	2	5	4	0	7	h[l]=2 < h[r]=5 → 4-2=2 water, left++
5	5	—	—	—	—	9	left >= right, done

Result: 9 ✓

Edge Cases

• Empty or single element → 0 water
• Monotonically increasing or decreasing → 0 water
• All same height → 0 water (water can't be trapped)

Complexity

Approach	Time	Space
Precompute arrays	O(n)	O(n)
Two pointers	O(n)	O(1)

Prefer the two-pointer approach in interviews for optimal space.

Key Terms

Term	Definition
Two pointers	Technique using left/right indices converging from opposite ends of an array to avoid nested loops.
Prefix max / suffix max	The tallest bar seen so far scanning from the left (or right) up to a given index.
Bounding argument	The proof idea that water at index i is capped by min(max_left[i], max_right[i]), never by whichever side is taller.
Amortized invariant	In the two-pointer version, max_left/max_right act as a safe lower bound for the side not yet fully known, letting one pointer move without recomputing the whole array.

FAQ

Q: Can this be solved without extra space? A: Yes — the two-pointer approach achieves O(1) space by maintaining running max_left/max_right instead of full arrays.

Q: What if the input array is empty or has one element? A: No water can be trapped with fewer than 3 bars, so the function correctly returns 0 in both cases.

Q: Why does moving the pointer with the smaller height work correctly? A: If height[left] <= height[right], then some bar on the right side is at least height[left], guaranteeing max_right >= height[left], so the water above left is safely determined by max_left alone — no need to know the exact max_right.

Q: How does this generalize to trapping water in a 2D elevation map? A: That's LeetCode 407 (Trapping Rain Water II), which requires a min-heap based Dijkstra-like approach instead of two pointers, since water can escape in any of 4 directions on a grid.

Q: What if all bars have the same height? A: No water is trapped — min(max_left[i], max_right[i]) - height[i] evaluates to 0 for every index since all heights are equal.

Quick Revision

• Goal: total water trapped between bars, bounded by min(max_left[i], max_right[i]) - height[i] per column.
• Brute force: for each index compute max to its left and right — O(n²).
• Optimized: precompute max_left[] and max_right[] arrays in one pass each — O(n) time, O(n) space.
• Best: two pointers from both ends, tracking running max_left/max_right — O(n) time, O(1) space.
• Move the pointer on the side with the smaller height, since that side's water level is already determined.
• Add water when the current bar is shorter than the running max on its side; otherwise update the running max.
• Edge cases: empty/single-element array → 0; monotonic array → 0; uniform heights → 0.
• Prefer the two-pointer solution in interviews to show optimal space complexity.

Related Problems

• 167 - Two Sum II — canonical two-pointer pattern on a sorted array.
• LeetCode 11 (Container With Most Water) — same two-pointer skeleton but maximizes area between two bars instead of summing trapped volume.
• LeetCode 407 (Trapping Rain Water II) — the 2D grid generalization of this problem, solved with a min-heap instead of two pointers.