-
Notifications
You must be signed in to change notification settings - Fork 0
044 — Trapping Rain Water
LeetCode 42 · Hard. 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.
Picture a city skyline of buildings with different heights, right after a storm. Water pools on top of a short building only if there's something taller on both sides of it to hold the water in — like standing in a valley between two mountains. The water level sitting above any single building is capped by the shorter of its two "walls": the tallest building to its left, and the tallest building to its right. Whichever of those two walls is shorter is the one that determines how high the water can rise there — water always spills over the lower wall first, no matter how tall the other one is.
So for every building, the water above it is min(tallest building to the left, tallest building to the right) - its own height (and never less than zero, since a building can't hold negative water). The brute-force way to answer this is to look left and look right from every single building, all over again each time. The clever way notices you don't need to know the exact value of both walls at once — you only need to know which one is currently shorter, and that's enough to safely resolve one side at a time.
"Trapping rain water" / "water level determined by the tallest wall on both sides" signals that the answer at each position depends on the min of two independently-computed maximums — a left-max and a right-max. That shape supports two known approaches: precomputing both max arrays in O(n) extra space, or — the sharper move — two pointers converging from both ends, where at each step you only need to act on whichever side currently has the smaller running max, because you already know the other side has a wall at least that tall waiting somewhere within range.
For every position, scan left for the tallest wall and scan right for the tallest wall, then add whatever water fits above that position.
func trapBruteForce(_ height: [Int]) -> Int {
var totalWater = 0
let n = height.count
for i in 0..<n {
var leftMax = 0
for j in 0...i {
leftMax = max(leftMax, height[j])
}
var rightMax = 0
for j in i..<n {
rightMax = max(rightMax, height[j])
}
totalWater += max(0, min(leftMax, rightMax) - height[i])
}
return totalWater
}Big-O: O(n²) time — every one of the n positions triggers two fresh O(n) scans. O(1) extra space.
Two pointers start at both ends, each tracking the running max wall it has seen on its own side so far. Whichever pointer stands on the shorter of the two current heights is guaranteed to know its true water level already — resolve it, then step that pointer inward.
func trap(_ height: [Int]) -> Int {
guard height.count > 2 else { return 0 }
var left = 0
var right = height.count - 1
var leftMax = 0
var rightMax = 0
var totalWater = 0
while left < right {
if height[left] <= height[right] {
if height[left] >= leftMax {
leftMax = height[left]
} else {
totalWater += leftMax - height[left]
}
left += 1
} else {
if height[right] >= rightMax {
rightMax = height[right]
} else {
totalWater += rightMax - height[right]
}
right -= 1
}
}
return totalWater
}Big-O: O(n) time — each pointer moves inward once per step, covering the array in a single combined pass. O(1) extra space — just the two running maxes and a running total.
The brute force recomputes the exact left-max and right-max from scratch for every position, doing O(n) work n times. The optimal solution realizes you don't actually need both exact values at once — you only need to know which side is currently smaller. Whenever height[left] <= height[right], that comparison alone guarantees the true right-max for position left is at least height[right], even without having scanned the rest of the right side yet — there's a wall right there, at position right, that's tall enough. So the water above left is safely determined by leftMax alone, no right-side scan required. That single guarantee is what collapses the repeated O(n) rescans into one O(n) pass with two running maxes instead of two arrays. (There's also a well-known O(n) Monotonic Stack solution to this same problem, which resolves trapped water in horizontal layers as taller bars are found — a genuinely different lens on the same "shorter side determines the water" idea.)
- Two Pointers — the converging-pointer sweep, tracking a running max instead of hunting for a target sum.
- Arrays & Strings — the elevation array being scanned.
-
Monotonic Stack — an alternative
O(n)approach to this exact problem, resolving trapped water layer by layer as taller bars are encountered.
Trapping Rain Water is a skyline after a storm — the water above each building is capped by the shorter of its tallest left and right neighbors, and two pointers let you resolve whichever side you're already sure about.
The optimal solution never explicitly computes the full rightMax before using it to resolve water at the left pointer's position. Explain precisely why, whenever height[left] <= height[right], it's guaranteed that the true right-max for position left is at least height[right] — even though the algorithm hasn't finished scanning the right side yet.
⬅️ Previous: Container With Most Water · Next: Best Time to Buy and Sell Stock ➡️