noodleProblems/
Trapping Rain Water
#51

Trapping Rain Water

AlgorithmhardArrayTwo PointersDynamic ProgrammingStackMonotonic Stack

You are given an array height where height[i] is the height of a vertical bar of unit width at position i. Together the bars form an elevation map.

After it rains, water collects in the dips between taller bars. Return the **total units of water** that can be trapped.

Water sits above position i only up to the lower of the tallest bar to its left and the tallest bar to its right; the amount at i is min(maxLeft, maxRight) - height[i] when positive, else 0.

Example cases

  • classic
    in height = [0,1,0,2,1,0,1,3,2,1,2,1]
    out 6
    The dips between the bars hold 6 units of water in total.
  • wider basin
    in height = [4,2,0,3,2,5]
    out 9
  • no water
    in height = [1,2,3,4,5]
    out 0
    A strictly increasing profile traps nothing.

Constraints

  • 1 <= height.length <= 2 * 10^4
  • 0 <= height[i] <= 10^5
Saved
height =
[0,1,0,2,1,0,1,3,2,1,2,1]