Trapping Rain Water

heights describes a row of bars of width 1, heights[i] tall. After it rains, water collects in the dips between bars. Return how many units of water the row holds.

Constraints

  • 1 ≤ length of heights ≤ 100,000
  • 0 ≤ heights[i] ≤ 10,000

Example 1

Input
heights = [0,1,0,2,1,0,1,3,2,1,2,1]
Output
6
Why:

1 unit at position 2, 4 between positions 3 and 7, and 1 at position 9.

Example 2

Input
heights = [4,2,0,3,2,5]
Output
9
Why:

Everything between the 4 and the 5 fills to height 4: 2 + 4 + 1 + 2.

Hints

    Was this a good challenge?

    Solved by
    0
    Submissions
    0
    Accepted
    –