Trapping rain between the bars

Question

Bars of given heights sit shoulder to shoulder. After rain, water pools in every dip that is walled in on both sides.

heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
-> 6          # total units of trapped water

Return the total trapped water. The naive "for each bar, scan for its tallest wall on each side" is $O(n^2)$ ; aim for $O(n)$ .

Accepted Answer

Keep a stack of indices with decreasing heights (the left walls waiting for a right wall). When a taller bar arrives, it is a right wall: pop the dip below it, and the water sitting on that dip is bounded above by the shorter of the two walls, times the gap between them. Each popped bottom is a floor; the water layer over it has height \min(	ext{left wall}, 	ext{right wall}) - 	ext{floor} and width equal to the span between the two walls. Summing these layers counts every trapped unit exactly once. On the example the pockets around the 0s between the height-2 and height-3 bars accumulate t…

Trapping rain between the bars

Your answer

More Coding questions