Back to ArraysTrapping Rain Water
Hard

Trapping Rain Water

HardMust DoTwo PointersPrefix Sum

Given an array representing an elevation map, compute how much water it can trap after raining, using each bar's width as 1 unit.

Examples

Example 1

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

Explanation: Several small basins between taller bars trap a total of 6 units of water.

Example 2

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

Explanation: A monotonically increasing skyline has nothing taller to its left to trap water against, so no basin forms.

Example 3

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

Explanation: A monotonically decreasing skyline traps nothing, for the mirrored reason.

Constraints

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

Follow-up

Could you compute the same answer using explicit left-max and right-max prefix arrays instead of two pointers, and what does that trade off in space?

Loading editor…

Code execution is coming soon.