Run it
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 therefore 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 explicitly. Candidates who write this from memory usually cannot say why moving the shorter side is the correct choice.
The stack alternative
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 naming as an alternative.
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, which 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 specifically, 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 — essentially Dijkstra's algorithm.
Product of array except self. Unrelated in topic, identical in technique: prefix and suffix arrays, then combine.
What it is testing
Do you find the per-position formula? min(left_max, right_max) - height[i] is the insight; without it there is nothing to optimise.
Do you eliminate the repeated maxima? Precomputing them is the step from O(n²) to O(n).
Do you reach O(1) space? The two-pointer argument — only the smaller maximum binds — is the part that requires real thought.
Can you justify moving the shorter side? Being able to explain why that is safe distinguishes understanding from memorisation.
Do you check the degenerate inputs? Empty, sorted, and fewer than three bars.
Recap in one screen
- Water above a bar is
min(left_max, right_max) - height[i], never negative. - Precomputing the two maxima arrays gives O(n) time and O(n) space in three simple passes.
- Two pointers reach O(1) space: process whichever side is shorter, since its running maximum is the binding wall.
- A monotonic stack solves it by regions instead of columns — the same pattern as the histogram problems.
- Any monotonic input traps nothing, because water needs walls on both sides.