Trapping rain water
Given non-negative bar heights, treat them as an elevation map (each bar has width 1) and compute how much rain water is trapped between the bars after a storm.
height = [0,1,0,2,1,0,1,3,2,1,2,1] -> 6
Return the total trapped water. Aim for time and space.
Show a hint
The water sitting above index i is min(highest bar to its left, highest bar to its right) - height[i]. You could precompute both prefix maxima, but can two pointers moving inward compute the same thing with no extra array?
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.