visual walkthrough
Trapping Rain Water
The most famous two-pointer Hard; also solvable with prefix maxima or a stack.
The idea
Water sits above a bar up to the height of the shorter of the two tallest walls on either side. Computing both maxima for every bar is slow.
With two pointers you don't need both: whichever end is currently shorter has a taller wall somewhere on the other side, so its own side's max is the limit and its water can be settled immediately.
Complexity
| approach | time | space |
|---|---|---|
| Look left and right | O(n²) | O(1) |
| Two pointers | O(n) | O(1) |