Trapping rain water
DSA, Hard
Which structure or algorithm, and what does it cost.
You get a list h of non-negative integers. Each number is the height of a bar one unit wide, and the bars stand side by side. After heavy rain, water sits in the dips between taller bars. Return the total units of water held. Water above a bar is held only if there is a taller or equal bar somewhere on both sides.
Examples
Input [0,1,0,2,1,0,1,3,2,1,2,1]
Output 6
Why For example the dip at index 2 holds 1 unit (bounded by 1 on the left and 2 on the right).
Input [4,2,0,3,2,5]
Output 9
Why The bars of height 2, 0, 3, 2 fill up to level 4 (the left wall).
Input [1,2,3]
Output 0
Why because nothing is on both sides of a rising run.
Constraints
- 0 <= length of
h<= 200,000. - 0 <= each height <= 100,000.
Your answer must contain
- The rule for the water above one bar; a first solution with its cost; an improvement to O(1) extra memory and why it is correct; code for one of them; a hand trace of example 2.