Trapping Rain Water
Water above a bar is the smaller of the tallest walls on each side, minus its own height.
Two-Pointer Trace
Problem
Given an array of nonnegative bar heights, determine how many units of water remain after rain falls between the bars. Water can sit above a bar only when taller boundaries exist on both sides, and the amount is limited by the shorter boundary.
Examples
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Input: height = [4,2,0,3,2,5]
Output: 9
The Goal
Rain falls on bars of different heights. Count how much water stays.
Water above bar i rises to the shorter of two walls: the tallest bar to its left and the tallest to its right. Anything higher spills.
water[i] = max(0, min(maxLeft, maxRight) - height[i])
For [3, 1, 2], the middle bar sits under min(3, 2) = 2, so it holds 1.
The shorter wall caps the water
Water spills over the shorter side before it can reach the taller one.
Settle the side whose running maximum is smaller.
Key Idea: Two Running Maxima
Walk in from both ends, keeping leftMax and rightMax, the tallest bars seen from each side.
If leftMax <= rightMax, the left bar's level is settled. Whatever lies further right, its right wall is at least rightMax, so leftMax caps it. Add its water and move left in. Otherwise, do the same on the right.
With leftMax = 2 and rightMax = 5, a left bar of height 1 holds 1.
The smaller maximum fixes the level at its pointer.
The left level is 2.
The Algorithm
Each pass settles one bar for good, so the total only ever grows by water that's final.
while left <= right:
if left_max <= right_max:
left_max = max(left_max, height[left])
answer += left_max - height[left]
left += 1
else:
right_max = max(right_max, height[right])
answer += right_max - height[right]
right -= 1Update the maximum before you subtract. A new tallest bar then adds 0, never a negative amount.
| Approach | Time | Space | How |
|---|---|---|---|
| Two pointers | O(n) | O(1) | Settle the side with the smaller maximum |
| Monotonic stack | O(n) | O(n) | Fill layers when a taller wall appears on the right |
Walkthrough
Run it on [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1].
The left side is the bottleneck for most of the run. It fills bar 2 with 1, then bars 4, 5 and 6 with 1, 2 and 1. Once left reaches the 3, the right side becomes the bottleneck, and bar 9 adds the last 1.
That's 1 + 1 + 2 + 1 + 1 = 6.
Checkpoint · predict the next step
Step 5 of 14 on the stage: leftMax 1 ≤ rightMax 1, so the left side is the bottleneck. Bar 2 is 0, under leftMax: it holds 1 − 0 = 1. Water: 1.
left on 0 (index 2) · right on 2 (index 10) · leftMax 1 · rightMax 1 · water 1
Pitfalls
- Rescanning both sides for every bar gets the right answer in
O(n²). Keep the maxima as you go. - Compare
leftMaxandrightMax, not the current bar heights. - Move one pointer per step. Moving both can skip a bar that isn't settled yet.
- Rising, falling and flat bars, or fewer than three bars, all hold 0, with no special cases.
Which mistake makes this O(n²)?
Complexity
Each step moves one pointer inward and neither turns back, so each bar is settled once: O(n) time. You keep two pointers, two maxima and a total, so extra space is O(1).
A monotonic stack is also O(n) time, but it needs O(n) space.
One pass from both ends
- Move the pointersInward only.dominantO(n)
- Update maxima and add waterConstant work per bar.dominantO(n)
- Extra statePointers, maxima and the total.O(1)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(n) | 10 | 100 | 1K | 10K |
One pass, constant extra memory.
In short
Two pointers track the max height seen from the left and right. Whichever side has the smaller running max is the bottleneck, so you can safely add its trapped water and advance it. This computes the answer in one pass and O(1) space; a monotonic stack is an alternative that fills water layer by layer.
Common mistake
Recomputing the max-left/max-right for every index (O(n²)) instead of maintaining them incrementally.