Trapping Rain Water

Trapping Rain Water looks like a geometry puzzle but is really a two-pointer classic. The trick is realizing that the water above any bar depends only on the tallest walls to its left and right — and you can discover those walls without ever scanning twice.

The slow way first

For each bar, the water sitting on top of it is min(tallest wall to the left, tallest wall to the right) − its own height (never less than zero). The obvious solution scans left and right from every bar to find those two walls:

That is O(n²) — for each of the n bars we do an O(n) scan. Correct, but wasteful, because we recompute the same maxima over and over.

The idea: move the shorter wall

Put a pointer l at the left end and r at the right, and track left_max (tallest bar seen from the left so far) and right_max (tallest from the right). The insight:

If height[l] <= height[r], then whatever sits to the right, the right wall is at least as tall as the bar at l. So the water above bar l is decided entirely by left_max — we can settle it right now and move l inward. Otherwise the symmetric argument settles bar r.

Because we always advance the shorter side, the taller side's max is a guaranteed upper bound — so the shorter side's own running max is the true water level there.

Walk through it

Step through the animation. Pointers l and r start at the ends. At each step we compare the two end bars and work the shorter one: update its running max, add max − height to the total, and slide that pointer in. Watch the dips behind a wall fill up (+1, +2, +1) and the running maxes climb. When l and r meet, every bar has been settled exactly once and the total is 6.

Pseudocode

l = 0, r = last index
left_max = right_max = 0
water = 0
while l < r:
    if height[l] <= height[r]:
        left_max  = max(left_max,  height[l])
        water    += left_max - height[l]
        l += 1
    else:
        right_max = max(right_max, height[r])
        water    += right_max - height[r]
        r -= 1
return water

The Python solution

def trap(height):
    l, r = 0, len(height) - 1
    left_max = right_max = 0
    water = 0
    while l < r:
        if height[l] <= height[r]:
            left_max = max(left_max, height[l])
            water += left_max - height[l]
            l += 1
        else:
            right_max = max(right_max, height[r])
            water += right_max - height[r]
            r -= 1
    return water

• The while l < r loop runs until the pointers meet — each iteration finalizes exactly one bar.
• if height[l] <= height[r] picks the shorter end; that side's water is safe to settle now.
• left_max = max(left_max, height[l]) raises the left wall, then water += left_max - height[l] adds the gap (zero when the current bar is the wall).
• The else branch is the mirror image for the right side.
• left_max and right_max are plain integers, so we never allocate an array — O(1) extra space.

Complexity

The two-pointer version matches the speed of the prefix-array approach while dropping its memory down to a couple of integers.

When this pattern shows up

Practice