Trapping Rain Water (LeetCode 42)

The problem

You get an array height of non-negative integers; each is the height of a bar of width 1. After it rains, water collects in the dips between bars. Return the total units of water trapped.

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

The bars of height 4 and 5 form the walls. Above the inner bars the water level is 4, so they hold 2 + 4 + 1 + 2 = 9 units.

How to think about it

Start with brute force. For each bar, look left for the tallest bar and right for the tallest bar. The water above bar i is min(maxLeft, maxRight) − height[i] (never negative). Scanning both directions for every bar is O(n²).

A better version: precompute. Build leftMax[i] and rightMax[i] arrays in two passes, then sum min(leftMax[i], rightMax[i]) − height[i]. That’s O(n) time but O(n) space.

The key insight: you only need the smaller side. The water above a bar depends on the smaller of its two maxima. Keep pointers l and r at the ends, with lm the tallest bar seen from the left and rm the tallest from the right. If lm < rm, then for the bar just inside l, its true right maximum is at least rm, which is bigger than lm. So its water level is fully decided by lm, and you can settle that bar now without knowing anything else about the right side. Move l, update lm, add lm − height[l]. Mirror this when rm ≤ lm. That’s O(n) time and O(1) space.

Which pattern is this? Converging two pointers, where the side with the smaller running max moves. The tell is “each position is limited by the best value on its left and on its right”. It’s also a monotonic-stack problem, shown below.

Approach

1. Set l = 0, r = n - 1, lm = height[0], rm = height[n-1], water = 0.
2. While l < r: if lm < rm, move l right, update lm = max(lm, height[l]), and add lm − height[l].
3. Otherwise move r left, update rm, and add rm − height[r].
4. Return water.

Updating the max before adding means the added amount is never negative: a new tallest bar simply adds 0.

Solution

def trap(h):
    if not h: return 0
    l, r = 0, len(h) - 1
    lm, rm = h[l], h[r]; water = 0          # tallest bar seen from each side
    while l < r:
        if lm < rm:                           # left side is the bottleneck
            l += 1; lm = max(lm, h[l]); water += lm - h[l]
        else:                                 # right side is the bottleneck
            r -= 1; rm = max(rm, h[r]); water += rm - h[r]
    return water
# trap([0,1,0,2,1,0,1,3,2,1,2,1]) -> 6

Alternative: monotonic stack

def trap_stack(h):
    st = []; water = 0                         # indices with decreasing heights
    for i, height in enumerate(h):
        while st and h[st[-1]] < height:       # current bar closes a valley
            mid = st.pop()
            if not st: break                   # no left wall: water spills
            dist = i - st[-1] - 1
            bounded = min(h[st[-1]], height) - h[mid]
            water += dist * bounded            # fill one horizontal layer
        st.append(i)
    return water
# trap_stack([0,1,0,2,1,0,1,3,2,1,2,1]) -> 6

The stack version fills water in horizontal layers: whenever a taller bar arrives, it pops the valley floor and adds the slab between the new bar and the wall below it on the stack. It’s also O(n) time, but it needs O(n) space for the stack. The two-pointer version adds water column by column in O(1) space, so it’s the one to lead with. The stack version is worth knowing because the same “pop when a taller bar arrives” idea solves Largest Rectangle in Histogram.

Dry run

Two-pointer version on height = [4, 2, 0, 3, 2, 5]. Start: l = 0, r = 5, lm = 4, rm = 5.

Now l == r, so the answer is 9. (The stack version also returns 9 on this input, adding 2, 2, 1 and 4 as it pops at indices 3 and 5.)

Complexity

• Time: O(n) for both versions. The pointers meet after n − 1 moves; in the stack version each index is pushed and popped at most once.
• Space: O(1) for two pointers; O(n) for the stack in the worst case (a strictly decreasing array).

Edge cases and pitfalls

• Empty array returns 0 (the first line guards h[0]). Arrays of length 1 or 2 also return 0.
• Strictly increasing or decreasing bars trap nothing: one side never forms a wall.
• Moving the wrong pointer. Always advance the side with the smaller running max. Moving the other side settles a bar whose limiting wall you haven’t seen yet.
• Adding before updating the max can add negative water. Update lm first, then add.
• Confusing it with Container With Most Water, where the bars in between are ignored.

Related problems

• Container With Most Water (LeetCode 11): the same “the shorter side decides” reasoning, for one pair of walls.
• Largest Rectangle in Histogram (LeetCode 84): the monotonic-stack version’s closest cousin.
• Product of Array Except Self (LeetCode 238): another “combine what’s on the left with what’s on the right” problem using prefix and suffix passes.