Trapping Rain Water
Water above a bar is the smaller of the tallest walls on each side, minus its own height.
Approach
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.
Time complexity
O(n)
Space complexity
O(1)
Common mistake
Recomputing the max-left/max-right for every index (O(n²)) instead of maintaining them incrementally.
See it run, step by step
Generate an interactive lesson for Trapping Rain Water — trace every variable and watch the algorithm execute until it clicks.
Start a lesson on Trapping Rain Water