Module 04 · Two Pointers and In-Place Read/Write State

039. Trapping Rain Water

Interview · Download this solution · All solutions and shared helpers

Problem

Return total water trapped above unit-width bars with nonnegative heights. Water at a position is limited by the tallest bar on each side, including the position itself. Empty input returns zero. Do not change the heights.

Examples

Example 1

trapped_water([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])
=> 6

Contributions across all valleys sum to six.

Example 2

trapped_water([])
=> 0

There are no bars.

Example 3

trapped_water([3, 0, 2, 0, 4])
=> 7

Interior contributions are three, one and three.

Reveal the worked solution and reasoning

Why this mechanism works

A prefix/suffix maximum solution stores both walls for every cell. Two pointers avoid those arrays: finalize the side whose known wall is lower. The opposite side already supplies a wall at least that high. A taller current bar raises its side's wall and contributes zero rather than negative water.

State and boundaries

left_max and right_max are walls established by consumed bars on their sides. water is final for consumed cells; [left,right] remains unresolved.

Protocol

Start both known walls and water at zero.
Choose the side with the lower known wall.
Update that side's wall from its current bar.
Add wall minus bar height.
Consume that cell and repeat.

Visualization

bars: 3 0 2 0 4
water:0 3 1 3 0
limiting interior wall: min(3,4)=3

Python implementation

def trapped_water(heights):
    left, right = 0, len(heights) - 1
    left_max = right_max = water = 0
    while left <= right:
        if left_max <= right_max:
            left_max = max(left_max, heights[left])
            water += left_max - heights[left]
            left += 1
        else:
            right_max = max(right_max, heights[right])
            water += right_max - heights[right]
            right -= 1
    return water

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

trapped_water([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])

L2 trapped_water: left, right = 0, len(heights) - 1
heights=[0, 1, 0, 2, 1, 0, 1, 3, ...]; left=0; right=11

L3 trapped_water: left_max = right_max = water = 0
heights=[0, 1, 0, 2, 1, 0, 1, 3, ...]; left=0; right=11; left_max=0; right_max=0; water=0

L8 trapped_water: left += 1
heights=[0, 1, 0, 2, 1, 0, 1, 3, ...]; left=1; right=11; left_max=0; right_max=0; water=0

L6 trapped_water: left_max = max(left_max, heights[left])
heights=[0, 1, 0, 2, 1, 0, 1, 3, ...]; left=1; right=11; left_max=1; right_max=0; water=0

L8 trapped_water: left += 1
heights=[0, 1, 0, 2, 1, 0, 1, 3, ...]; left=2; right=11; left_max=1; right_max=0; water=0

L10 trapped_water: right_max = max(right_max, heights[right])
heights=[0, 1, 0, 2, 1, 0, 1, 3, ...]; left=2; right=11; left_max=1; right_max=1; water=0

L12 trapped_water: right -= 1
heights=[0, 1, 0, 2, 1, 0, 1, 3, ...]; left=2; right=10; left_max=1; right_max=1; water=0

L7 trapped_water: water += left_max - heights[left]
heights=[0, 1, 0, 2, 1, 0, 1, 3, ...]; left=2; right=10; left_max=1; right_max=1; water=1

... 12 intermediate state changes omitted ...

L8 trapped_water: left += 1
heights=[0, 1, 0, 2, 1, 0, 1, 3, ...]; left=8; right=9; left_max=3; right_max=2; water=5

L11 trapped_water: water += right_max - heights[right]
heights=[0, 1, 0, 2, 1, 0, 1, 3, ...]; left=8; right=9; left_max=3; right_max=2; water=6

L12 trapped_water: right -= 1
heights=[0, 1, 0, 2, 1, 0, 1, 3, ...]; left=8; right=8; left_max=3; right_max=2; water=6

L12 trapped_water: right -= 1
heights=[0, 1, 0, 2, 1, 0, 1, 3, ...]; left=8; right=7; left_max=3; right_max=2; water=6

Result: 6. Contributions across all valleys sum to six.

trapped_water([])

L2 trapped_water: left, right = 0, len(heights) - 1
heights=[]; left=0; right=-1

L3 trapped_water: left_max = right_max = water = 0
heights=[]; left=0; right=-1; left_max=0; right_max=0; water=0

Result: 0. There are no bars.

Why the solution is correct

If the chosen bar is below its known wall, the opposite known wall is high enough to support exactly that limiting level. If the bar exceeds the known wall, it cannot hold water and becomes the new wall. Every cell is finalized once with a nonnegative correct contribution.

Time and space

O(n) time and O(1) auxiliary space.

Common mistakes

Adding a difference before raising the wall may subtract water. Container area and trapped volume have different per-position meanings.

Reasoning card

State: left_max and right_max are walls established by consumed bars on their sides. water is final for consumed cells; [left,right] remains unresolved.

Invariant: Processed positions have their final trapped-water contribution.

Decision to rehearse: Advance the side with the smaller known boundary maximum.

Finish: Consume that cell and repeat

Transfer exercise

Implement the two-array wall method as an independent oracle and compare both methods on short random arrays.