The problem
Given bar heights, compute how much rain water the bars trap between them.
Stuck? Reveal hints one at a time
How to approach it
- 1left = 0, right = n − 1, maxLeft = maxRight = 0, total = 0.
- 2While left < right: if height[left] < height[right], the left side is bound by maxLeft — add max(0, maxLeft − height[left]), update maxLeft, left++.
- 3Otherwise do the mirror on the right.
- 4Return total.
Key insight
When height[left] < height[right], SOME right wall at least height[right] exists — so min(maxLeft, maxRight) for the left cell is decided by maxLeft alone, no lookahead needed.
The solution
Watch out for
- Updating the running max BEFORE adding water makes the contribution never negative — order matters.
- The stack solution (pop valleys, add horizontal slabs) is also O(n) and worth knowing for the follow-up discussion.