Trapping Rain Water

Problem

An elevation map is given as an array height of non-negative integers, where each value is the height of a bar of width 1. After heavy rain, water settles in the dips between taller bars. Compute the total number of unit cells of water that remain trapped.

• height has at most 20,000 bars; an empty map is allowed and traps nothing.
• Each bar height is an integer from 0 to 30,000.

Examples

• height = [2, 0, 1, 3, 0, 1, 2] → 6. Between the bars of height 2 and 3, indices 1 and 2 hold 2 + 1; between the 3 and the final 2, indices 4 and 5 hold 2 + 1.
• height = [5, 1, 3, 0, 4, 2, 6] → 15. The left wall of 5 and right wall of 6 cap the level at 5 everywhere, so the columns hold 4 + 2 + 5 + 1 + 3 = 15.
• height = [1, 2, 3, 4] → 0. Strictly rising terrain has no dip to fill.

Hints

1. Look at a single column. How high can the water sit there, and what two quantities decide that?
2. The water level above column i is min(tallest bar to its left, tallest bar to its right); precomputing those two arrays gives an O(n) answer.
3. To drop the extra arrays, walk two pointers inward and notice that the side with the smaller running maximum is the one whose water level is already known for certain.