Trapping Rain Water - Problem
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 elevation map is represented by an array height where height[i] is the height of the bar at position i.
Example: For heights [0,1,0,2,1,0,1,3,2,1,2,1], the trapped water would be 6 units.
Input & Output
Example 1 — Classic Case
$
Input:
height = [0,1,0,2,1,0,1,3,2,1,2,1]
›
Output:
6
💡 Note:
Water gets trapped in valleys: at indices 2 (1 unit), 5 (2 units), 6 (1 unit), 9 (1 unit), 10 (1 unit) for total of 6 units
Example 2 — Simple Valley
$
Input:
height = [3,0,2,0,4]
›
Output:
7
💡 Note:
Two water pockets: between 3 and 2 (2 units), and between 2 and 4 (5 units total). Water levels: [0,3,0,2,0] → 3+2=5 trapped
Example 3 — No Water
$
Input:
height = [3,2,1]
›
Output:
0
💡 Note:
Decreasing heights cannot trap any water - water would flow off the right side
Constraints
- n == height.length
- 1 ≤ n ≤ 2 × 104
- 0 ≤ height[i] ≤ 3 × 104
Visualization
Tap to expand
Understanding the Visualization
1
Input
Elevation map represented as array of bar heights
2
Process
Find water that gets trapped between the bars
3
Output
Total units of water trapped
Key Takeaway
🎯 Key Insight: Water level at any point is determined by the minimum of the maximum heights on both sides
💡
Explanation
AI Ready
💡 Suggestion
Tab
to accept
Esc
to dismiss
// Output will appear here after running code