12. Trapping Rain Water

Hard · Array

Given an elevation map represented by an array of heights, compute how much water can be trapped after it rains. Water is trapped between elevations and cannot flow off the sides.

Assume the width of each bar is 1 unit. Water trapped above a position is determined by the minimum of the maximum height to its left and the maximum height to its right, minus the height at that position.

Examples

Example 1
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: Water is trapped in the valleys. At index 2, water level is min(1,3)=1, so 1 unit trapped. At index 4, water level is min(2,3)=2, so 1 unit trapped. At index 5, water level is min(2,3)=2, so 2 units trapped. Total: 1+1+2+2=6.
Example 2
Input: [4,2,0,3,2,5]
Output: 9
Explanation: Water fills the depression between the left peak (4) and right peak (5). At indices 1-4, water is trapped: 2+2+3+3=10 units minus the bar heights 2+0+3+2=7 gives 3 units... Actually: at index 1: min(4,5)-2=2, at index 2: min(4,5)-0=4, at index 3: min(4,5)-3=1, at index 4: min(4,5)-2=2. Total: 2+4+1+2=9.

Constraints