Trapping Rain Water
HardTwo Pointers · NVIDIA
You are given an integer array height, where height[i] is the height of a bar of width 1 at position i. After it rains, water collects between the bars.
The water level above position i is the smaller of (the tallest bar at or to the left of i) and (the tallest bar at or to the right of i). Position i holds level - height[i] units of water, which is 0 when the bar reaches the level.
Return the total units of water trapped across all positions.
Example 1
- Input:
- height = [0,3,0,2,0,4]
- Output:
- 7
- Explanation
- Position 2 is bounded by height 3 on the left and height 4 on the right, so it fills to level 3 and holds 3 units. Position 3 has height 2 under the same level 3, so it holds 1. Position 4 holds another 3. Total 3 + 1 + 3 = 7.
Example 2
- Input:
- height = [2,0,2,1,0,1,3]
- Output:
- 6
- Explanation
- The tallest bar to the left of every middle position is 2 and the tallest to the right is 3, so the level is 2. Positions 1, 3, 4 and 5 hold 2 + 1 + 2 + 1 = 6.
Example 3
- Input:
- height = [6,1,4]
- Output:
- 3
- Explanation
- The middle bar sits between walls of 6 and 4, so water only rises to the shorter wall, 4, and holds 4 - 1 = 3.
Constraints
1 <= height.length <= 2 * 10^40 <= height[i] <= 10^5