Trapping Rain Water

Two Pointers, problem 7 of 7

Trapping Rain Water

Hard

LC #42

opposite endsprefix max

Not attempted yet

height is an elevation map: bar i has width 1 and height height[i]. After it rains, water collects in the dips between bars. Return the total units of trapped water.

Example 1

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

       #
   #~~~##~#
 #~##~######
~ is water: 6 units

Example 2

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

Example 3

Input: height = [3, 0, 3]
Output: 3

Constraints

  • 0 ≤ len(height) ≤ 10⁵
  • 0 ≤ height[i] ≤ 10⁵

Python

Loading draft…

Test results

10 tests available

No results yet

Run tests your code against the examples; Submit runs the hidden tests too.

3 examples, 7 hidden

Run examples, then submit all tests.