Trapping Rain Water
Given bar heights, compute how much rain water the bars trap.
- n == height.length
- 1 <= n <= 2 * 10⁴
- 0 <= height[i] <= 10⁵
Intuition
Trapping rain water gives an elevation map of bar heights and asks how much water is held after rain. The key is to stop thinking about pools and think about one column at a time.
Water sitting above bar i is bounded by the tallest bar to its left and the tallest to its right. Water fills to the lower of those two walls, so:
- water at i = min(maxLeft, maxRight) − height[i], and never below zero.
Summing that over every column gives the answer. Precomputing two arrays of running maxima makes this an easy O(n) solution using O(n) space.
The two-pointer version removes those arrays, and the reasoning behind it is the interesting part. Put pointers at both ends and track leftMax and rightMax seen so far. Now suppose leftMax <= rightMax. The water above the left pointer is decided by min(leftMax, trueRightMax) — and although you have not seen the whole right side yet, you know trueRightMax >= rightMax >= leftMax. So the minimum is leftMax regardless of what the unexplored right side holds.
The smaller wall is always the binding one, and that is what makes the decision safe with incomplete information. Settle that column, move the pointer inward, and repeat — each step finalises exactly one column in O(1) space.
The two-pointer version comes from noticing that water at a position depends on min(tallest left, tallest right) — and you don't need both numbers, only the smaller one. Whenever a quantity is bounded by a minimum of two running maxima, walk inward from both ends and process whichever side is currently shorter: that side's bound is already known, so it can be settled immediately. The same trick turns container-with-most-water into one pass.
Approach
Before reading on: price up what the direct approach costs here, then ask what makes it safe to discard one end without checking it against everything. Aim for O(n) time and O(1) space.
Work out the per-column formula
Column i holds min(maxLeft, maxRight) - height[i] water, clamped at zero. Thinking per column rather than per pool is what makes the problem tractable — pools have irregular shapes, columns do not.
Start with the two-array solution
Build maxLeft in a forward pass and maxRight in a backward pass, then sum the formula over every index. This is O(n) time and O(n) space, and it is the version to write first because its correctness is obvious.
Move two pointers inward
Place l at the start and r at the end, tracking leftMax and rightMax as you go. Each iteration settles the column at whichever pointer stands on the smaller maximum, then advances that pointer.
Understand why the smaller side is safe
If leftMax <= rightMax, then the true right maximum is at least rightMax, hence at least leftMax. So min of the two is leftMax whatever lies in the unexplored middle — this is the argument that licenses deciding a column before seeing the whole array.
Update the running max before adding
On each step, first update the relevant maximum with the current height, then add max - height[i]. Doing it in this order means the value is never negative and no explicit clamp is needed.
Cost of the two-pointer sweep
The pointers meet after n steps, giving O(n) time and O(1) space — an improvement on the two-array version's O(n) space. Each column is settled exactly once, so nothing is recomputed.
Solution & live demo
Common pitfalls
Comparing the running maxima instead of the current bars
if left_max <= right_max:
...
l += 1if height[l] <= height[r]:
...
l += 1Both maxima start at 0 and update lazily, so the comparison can pick a side whose true bound isn't settled yet and bank water that a taller bar later invalidates. Comparing the actual bars is what proves the shorter side is limited by its own max — that's the invariant the whole method rests on.
Adding water before updating the wall
water += left_max - height[l] left_max = max(left_max, height[l])
left_max = max(left_max, height[l]) water += left_max - height[l]
If the current bar is the tallest so far it should hold no water, but against the stale left_max the subtraction goes negative and quietly removes water banked earlier. Raising the wall first makes the term exactly zero for a new peak.
Edge cases
Smaller wall is always the current bar itself — every contribution is 0.
No basin can form; loop yields 0.