DSA problem
Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
The water trapped above any index is bounded by the tallest bars to its left and to its right: the water level at that index equals the smaller of those two maximums, minus the height of the bar itself (water cannot be negative).
Return the total units of trapped water across the whole elevation map.
Examples
Example 1
Input:
height = [0,1,0,2,1,0,1,3,2,1,2,1]Output:
6Explanation: The elevation map traps 6 units of rain water between its bars.
Example 2
Input:
height = [4,2,0,3,2,5]Output:
9Explanation: Water accumulates in the dips bounded by the bars of height 4 and 5.
Example 3
Input:
height = [1,1,1]Output:
0Explanation: A flat elevation map traps no water.
Constraints
- n == height.length
- 1 <= n <= 2 * 10^4
- 0 <= height[i] <= 10^5
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.