Trapping Rain Water

Two pointers with running wall maxes

time O(n)space O(1)

Water above any bar rises to min(tallest wall on its left, tallest wall on its right) minus its own height. Instead of precomputing those walls, two pointers walk inward and always settle the side whose CURRENT bar is shorter — the opposite end's tall bar guarantees the other side can't be the bottleneck, so one running leftMax (or rightMax) decides each cell's water on the spot.

Details

Animated on: Given elevations [4, 2, 0, 3, 2, 5], compute how much rain water is trapped between the bars.

Problem:Trapping Rain WaterHard

Pattern:Two Pointers

Two pointers with running wall maxes

step 1 / 13

[0]

[1]

[2]

[3]

[4]

[5]

Six bars: [4,2,0,3,2,5]. Park l on the first bar (4) and r on the last (5). leftMax/rightMax remember the tallest wall seen from each side; water starts at 0.

l=0· arr[0] = 4
r=5· arr[5] = 5

Pseudocode

1To find how much water is trapped:
2  put a left marker on the first bar and a right marker on the last; leftMax, rightMax and water all start at 0
3  keep going while the left marker is before the right marker:
4    if the left bar is shorter than the right bar:
5      raise leftMax to whichever is taller: leftMax or the left bar
6      add (leftMax minus the left bar) to water, then move the left marker one step right
7    otherwise:
8      raise rightMax to whichever is taller: rightMax or the right bar
9      add (rightMax minus the right bar) to water, then move the right marker one step left
10  the answer is the total water collected

← / → step · space play · Home restart

Every step in words

Show all 13 steps

Six bars: [4,2,0,3,2,5]. Park l on the first bar (4) and r on the last (5). leftMax/rightMax remember the tallest wall seen from each side; water starts at 0.
Round 1: h[l] = 4 vs h[r] = 5 - the LEFT bar is shorter. Settle index 0 now: a wall of height 5 already stands somewhere to its right, so the level above this cell depends only on the tallest LEFT wall.
leftMax = max(0, 4) = 4 - a real boundary wall. Water above it: leftMax - h[0] = 4 - 4 = 0; a wall's own top traps nothing. Advance l to index 1.
Round 2: h[1] = 2 vs h[5] = 5 - still shorter on the left. The untouched 5-wall on the right guarantees the level above index 1 is decided by the left wall alone.
h[1] = 2 does not beat leftMax = 4, so the wall stands taller. Water above index 1: 4 - 2 = 2 units. Running total: 0 + 2 = 2. Advance l to index 2.
Round 3: h[2] = 0 vs h[5] = 5 - left shorter again. This pit sits between the 4-wall behind it and the 5-wall ahead of it, so expect it to fill deepest.
leftMax stays max(4, 0) = 4 - the zero changes nothing about the tallest left wall. Water above index 2: 4 - 0 = 4 units, the biggest single contribution. Total: 2 + 4 = 6. Advance l to index 3.
Round 4: h[3] = 3 vs h[5] = 5 - left shorter once more. The water level here is still capped by leftMax = 4, not by this bar's own height of 3.
leftMax stays 4 because 3 < 4. Water above index 3: 4 - 3 = 1 unit - even a near-tall bar pools a sliver on top. Total: 6 + 1 = 7. Advance l to index 4.
Round 5: h[4] = 2 vs h[5] = 5 - left shorter for the last interior cell. Same guarantee as every round: the right wall outranks everything the left walk has met so far (max so far: 4).
leftMax stays 4. Water above index 4: 4 - 2 = 2 units. Total: 7 + 2 = 9. l advances onto index 5 - pointers meet, every interior cell has been settled.
Pointers met at l = r = 5, so the loop exits. Note r never moved: heights[5] = 5 is the TALLEST bar overall, so it won every comparison against the left walk (whose best was 4). One dominant end pinning still gives a correct O(n) sweep.
Answer: the interior cells hold 2 + 4 + 1 + 2 = 9 units of water above [4,2,0,3,2,5] - the two outer bars are the container walls and hold nothing. Return 9.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Trapping Rain Water in the editor All Arrays problems Back to roadmap