Trapping Rain Water
Compute the water trapped between bars using two converging pointers and running maximums
Problem Statement
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water can be trapped after it rains.
Input: height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6
Input: height = [4, 2, 0, 3, 2, 5]
Output: 9Intuition
The instinct is to look for "valleys" and measure each one. That works, but valleys nest inside larger valleys and the bookkeeping gets ugly fast.
The key insight — think per column, not per valley
Ask a much smaller question: how much water sits on top of a single bar i?
Water above bar i is held in by the tallest wall somewhere to its left and the tallest wall somewhere to its right. The level it settles at is the lower of those two walls — water spills over the shorter side. Then subtract the bar itself, since it occupies space:
water[i] = min(maxLeft[i], maxRight[i]) - height[i]
Sum that over every bar and you have the answer. No valley detection at all.
Try it on height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] at index 5 (height = 0):
- Tallest to the left:
2(index 3) - Tallest to the right:
3(index 7) - Water level:
min(2, 3) = 2, sowater = 2 - 0 = 2✓
Real-world analogy
A row of buildings of different heights after heavy rain. To know how deep the puddle on one rooftop is, you do not survey the whole skyline — you look for the tallest building on each side. The lower of those two is where the water overflows.
Three Solutions, One Formula
Every approach below computes the same min(maxLeft, maxRight) - height[i]. They differ only in how they obtain the two maximums.
1. Brute force — O(n²)
For each bar, scan left for its maximum and right for its maximum. Correct, but it re-scans the same bars over and over.
2. Precomputed arrays — O(n) time, O(n) space
Two passes fill maxLeft and maxRight, then a third pass sums the water. This is the Product of Array Except Self pattern with max in place of ×.
def trap_prefix_arrays(height: list[int]) -> int:
if not height:
return 0
n = len(height)
max_left = [0] * n
max_right = [0] * n
max_left[0] = height[0]
for i in range(1, n):
max_left[i] = max(max_left[i - 1], height[i])
max_right[n - 1] = height[n - 1]
for i in range(n - 2, -1, -1):
max_right[i] = max(max_right[i + 1], height[i])
return sum(min(max_left[i], max_right[i]) - height[i] for i in range(n))3. Two pointers — O(n) time, O(1) space
This is the version worth mastering, and its correctness argument is the heart of the problem.
Why two pointers can replace both arrays
Keep left and right closing in from the ends, along with maxLeft (tallest seen from the left so far) and maxRight (tallest seen from the right so far).
Suppose maxLeft < maxRight. Then for the bar at left, its true left maximum is exactly maxLeft, and its true right maximum — whatever it turns out to be — is at least maxRight, which is already bigger. So min(trueLeft, trueRight) = maxLeft, and the water above left is fully determined right now: maxLeft - height[left].
You never needed the exact right maximum. Knowing it is larger was enough.
That is why the algorithm always processes the side with the smaller running maximum: that is the side whose answer is already pinned down.
Watch it run
Solution
def trap(height: list[int]) -> int:
"""Total trapped water, in one pass with O(1) extra space."""
if not height:
return 0
left, right = 0, len(height) - 1
max_left, max_right = height[left], height[right]
total = 0
while left < right:
if max_left < max_right:
# The left column's water level is already fully determined.
left += 1
max_left = max(max_left, height[left])
total += max_left - height[left]
else:
right -= 1
max_right = max(max_right, height[right])
total += max_right - height[right]
return totalWhy the running max is updated before adding water
After moving the pointer, max_left = max(max_left, height[left]) guarantees max_left >= height[left], so max_left - height[left] is never negative. A bar taller than everything before it simply contributes 0 — no special case needed.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²) | O(1) |
| Prefix/suffix arrays | O(n) | O(n) |
| Two pointers | O(n) | O(1) |
| Monotonic stack | O(n) | O(n) |
The two-pointer version is optimal on both axes. The stack solution is worth knowing because it generalises to problems like Largest Rectangle in Histogram, where the per-column trick does not apply.
Edge Cases
Related Problems
- Container With Most Water — the same converging pointers, maximising one area instead of summing many
- Product of Array Except Self — prefix and suffix passes over the same array
- Min Stack — carrying a running extreme alongside the data