Run it: Trapping rain water in code
The two-pointer sweep against the precomputed-arrays version and a brute force, with the extra memory each one uses printed. All three agreeing on every test.
The brute force, then the fix
Scanning left and right from every position is O(n²):
The wasted work is obvious: the same maxima are recomputed at every index. Precompute them once.
O(n) time, O(n) space. Three passes, and each is a one-line recurrence. This is a perfectly good answer, and it is the clearest one to reason about.
The two-pointer solution: O(1) space
The insight that removes the arrays: only the smaller of the two running maxima matters.
If left_max < right_max, then whatever lies between, the water level at the left pointer is decided by left_max — because a wall at least as tall as right_max exists somewhere to the right, and right_max is the larger of the two. So the left position can be finalised without knowing the exact right-hand maximum.
O(n) time, O(1) space, one pass.
The comparison height[left] < height[right] is what guarantees the shorter side is being processed, and so that the running maximum on that side is the binding constraint. Because the maximum is updated before the addition, left_max - height[left] is never negative — which is why no max(0, ...) guard is needed.
Water sits above a bar up to the level of the lower of the two walls containing it: min(max to the left, max to the right) − height, or zero if that is negative.
The direct implementation precomputes both arrays of running maxima and then sums. That is O(n) time and O(n) space, perfectly correct, and the right first answer. The two-pointer version removes the arrays.
Why moving the shorter side is safe
Suppose height[lo] < height[hi]. Then whatever the maxima turn out to be, the left side's is the smaller of the two — because there is already a bar at least as tall as height[hi] on the right. So the water above lo is decided by left_max alone and can be settled now, without knowing anything more about the right.
That is the whole argument, and it is worth stating by name. Candidates who write this from memory usually cannot say why moving the shorter side is the correct choice.
The stack other
A monotonic decreasing stack also solves it in O(n), filling water horizontally layer by layer rather than column by column. It is harder to get right under pressure and worth mentioning as another approach.
The same "maximum to the left and right of each element" shape appears in largest-rectangle-in-a-histogram and stock-span. So recognising it is worth more than memorising this one solution.
Working through the example
[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], computing per-position water with the prefix arrays:
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|
| height | 0 | 1 | 0 | 2 | 1 | 0 | 1 | 3 | 2 | 1 | 2 | 1 |
| left max | 0 | 1 | 1 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 3 |
| right 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: 1 + 1 + 2 + 1 + 1 = 6.
Two rows are instructive. At i = 7 the bar is height 3 and is the tallest. So min(3, 3) - 3 = 0 — the peak holds nothing. At i = 5 the bar is 0 with walls of 2 and 3. So it holds 2 units, bounded by the shorter wall.
The stack solution
A monotonic decreasing stack also solves it, filling water in horizontal layers as each new bar pops shorter bars off:
O(n) time, O(n) space. It computes the same total by region rather than by column. This is why the arithmetic looks so different.
Worth knowing because the monotonic-stack pattern solves an entire family. Largest rectangle in a histogram, next greater element, daily temperatures. For this problem in detail, two pointers is the better answer: less code, less space, easier to explain.
| Approach | Time | Space | Notes |
|---|
| Brute force | O(n²) | O(1) | The baseline |
| Prefix maxima | O(n) | O(n) | Clearest to explain |
| Two pointers | O(n) | O(1) | The best answer |
| Monotonic stack | O(n) | O(n) | Same pattern as histogram problems |
Edge cases
| Case | Answer |
|---|
[] | 0 |
[1], [1, 2] | 0 — needs at least three bars |
| Monotonically increasing | 0 — no right wall |
| Monotonically decreasing | 0 — no left wall |
[3, 0, 3] | 3 |
| All equal heights | 0 |
[0, 0, 0] | 0 |
The monotonic rows are the useful mental check: water needs a wall on both sides. So any sorted input traps nothing.
Container with most water. Also two pointers, and a different rule. There the area is min(h[l], h[r]) * (r - l) and the shorter side is moved because it is the limiting factor.
Largest rectangle in a histogram. Monotonic stack, and the closest relative of the stack solution here.
Trapping rain water II (2D grid). Substantially harder: a min-heap starting from the boundary, processing cells in increasing height order. In effect Dijkstra's algorithm.
Product of array except self. Unrelated in topic, the same in technique: prefix and suffix arrays, then combine.