hardTwo PointersPure DSA~35 min
Trapped Capacity Between Peaks
A row of server racks each has a height. After a coolant flood, water pools in the dips between taller racks. Given the skyline of rack heights, compute how much coolant is trapped overall.
Problem
Given an array height where height[i] is the height of the i-th bar, compute how much water can be trapped after raining. Water above bar i equals min(maxLeft, maxRight) − height[i] when positive.
Input
An array height of n non-negative integers (0 ≤ n ≤ 2·10^4, 0 ≤ height[i] ≤ 10^5).
Output
A single integer: the total trapped water.
Constraints
- 0 ≤ n ≤ 2·10^4
- 0 ≤ height[i] ≤ 10^5
- Target O(n) time and O(1) extra space
Examples
Example 1
Input
height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output
6
Six units pool in the valleys between the taller bars.
Example 2
Input
height = [4,2,0,3,2,5]
Output
9
The big dip between the 4 and the 5 holds the bulk of the water.