Trapping rain water
Asked at Two Sigma
An array height gives the heights of a row of unit-width bars. After it rains, water pools in the dips.
height = [3, 0, 2, 0, 4] -> 7 units trapped
Return the total units of water trapped. Aim for time.
Show a hint
Water sitting on top of bar i rises to the level of the shorter of the two tallest walls flanking it, minus the bar's own height. How do you get those two walls for every i cheaply?
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.