Why it works
- Water over a bar rises to the lower of two walls: the highest bar on its left and the highest bar on its right. Any higher and it spills over the lower one.
- If leftMax ≤ rightMax, the right side already has a wall at least leftMax high, and the real highest bar on the right can only be higher. So the water over left is leftMax minus its height, whatever stands between the pointers. The right side works the same way, mirrored.
- That is why the side with the lower max moves: the water over its bar is already known for sure, and each step settles one bar for good.
Complexity
Time O(n): each step settles one bar and moves one pointer, so there are n steps. Memory O(1): two pointers, two maxes and the sum, with no arrays of maxes for every bar.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗