Trapping Rain Water
Hard · Two Pointers · Array · Two Pointers · Stack · Dynamic Programming
Problem
height[i] is the height of a bar of width 1. After rain, return how much water is trapped between the bars.
Examples
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6
Water settles in the dips between taller bars.
Input: height = [4,2,0,3,2,5] Output: 9
The deep gap between 4 and 5 holds most of it.
Constraints
- 1 <= len(height) <= 2 * 10^4
- 0 <= height[i] <= 10^5
Approaches
- Precomputed left and right maxima — time O(n), space O(n)
Related problems
Start free on Cariara · Coding problems · System design studio
