Sliding Window — Trapping Rain Water
↗ LeetCode: Trapping Rain Water · Hard · pattern chapter →
Given n non-negative integers representing an elevation map, compute how much water it traps after raining.
Example 1 — height=[0,1,0,2,1,0,1,3,2,1,2,1] → 6Example 2 — height=[4,2,0,3,2,5] → 9
Constraints — 1 ≤ n ≤ 2·10⁴. Brute computes per-column max-left/max-right in O(n²) = 10⁸ ops at n=10⁴ (borderline). Two-pointer with running max is O(n) = ~10⁶ ops on hot service.
Interview timer00:00
Approach 1 — Precompute leftMax, rightMax
For each i, water = min(leftMax[i], rightMax[i]) - h[i]. O(n) time, O(n) space.
Approach 2 — Opposing two-pointer (canonical)
Insight. Move whichever pointer has the smaller wall — the water level there is bounded by the smaller known max.
int trap(int[] h) {
int l = 0, r = h.length - 1, lMax = 0, rMax = 0, water = 0;
while (l < r) {
if (h[l] < h[r]) {
lMax = Math.max(lMax, h[l]);
water += lMax - h[l];
l++;
} else {
rMax = Math.max(rMax, h[r]);
water += rMax - h[r];
r--;
}
}
return water;
}Approach 3 — Monotonic decreasing stack
Push indices while heights decrease; on rise, pop the "bottom" and compute water in the pocket. Same O(n).
Complexity — Time O(n); Space O(1) for 2p, O(n) for arrays/stack.
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| leftMax + rightMax arrays | O(n) | O(n) | first-pass answer |
| Opposing 2p | O(n) | O(1) | canonical |
| Monotonic stack | O(n) | O(n) | teaching link |
When to use which
- Standard → opposing 2p (elegant, O(1) space).
- Interviewer wants explicit reasoning → precompute arrays.
- 2D grid → Trapping Rain Water II — min-heap.