Trapping Rain Water

Interview Prep

HardTwo Pointersarraystwo-pointers

The problem

Given an array of non-negative integers representing the elevation of a 1D landscape, compute how much rainwater could be trapped after a downpour. Each unit-width column traps water up to the lowest "wall" on either side, minus its own elevation.

Pattern: water at i = min(left max, right max) − height[i]

The water above column i is bounded above by the higher of the two surrounding peaks, but actually limited by the lower of them — water spills over the lower wall first. So water[i] = min(left_max[i], right_max[i]) − height[i], clamped at zero.

Once you've internalised that formula, every solution to this problem is just a different way to compute left_max and right_max efficiently.

Solution 1 — precomputed prefix and suffix maxes

def trap(height: list[int]) -> int:
    n = len(height)
    if n == 0:
        return 0

    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[n - 1] = height[n - 1]
    for i in range(n - 2, -1, -1):
        right_max[i] = max(right_max[i + 1], height[i])

    return sum(min(left_max[i], right_max[i]) - height[i] for i in range(n))

O(n) time, O(n) extra space. Two passes to fill the prefix-max and suffix-max arrays, one pass to sum. Clean and easy to reason about.

Solution 2 — two pointers, O(1) space

def trap(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    water = 0

    while left < right:
        if height[left] < height[right]:
            # Left side is the bottleneck. The right side has at least
            # this height somewhere, so left_max alone bounds the water.
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1

    return water

O(n) time, O(1) extra space. The insight: at any moment, the pointer pointing at the lower wall has a guaranteed bound on the water it sees — the running max from its side is enough, because the other side has a wall at least as tall waiting somewhere. Move whichever pointer is lower; the running max on that side rules.

This is one of the most elegant pointer arguments in the canon. If you can derive it on a whiteboard you've made the case for the senior bonus.

Walkthrough

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

    bar     0  1  0  2  1  0  1  3  2  1  2  1
    L max   0  1  1  2  2  2  2  3  3  3  3  3
    R max   3  3  3  3  3  3  3  3  2  2  2  1
    min     0  1  1  2  2  2  2  3  2  2  2  1
    water   0  0  1  0  1  2  1  0  0  1  0  0     →  total = 6

Edge cases

Related