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
Trapping Rain Water ProblemInput: Elevation Map01021013After Rain: Water Trapped💧💧Process: Find trapped waterOutput: 2 units of water trapped
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
Asked in
Amazon 85 Google 72 Facebook 68 Microsoft 58 Apple 45
1.9M Views
Very High Frequency
~25 min Avg. Time
25.8K Likes
Ln 1, Col 1
Smart Actions
💡 Explanation
AI Ready
💡 Suggestion Tab to accept Esc to dismiss
// Output will appear here after running code
Code Editor Closed
Click the red button to reopen