Trapping Rain Water
Work out how much rain a row of bars can hold. From the O(n²) brute force to prefix maximums and the O(1) space two pointers solution, with a proof.
Updated Medium read: 8 min read
Approaches at a glance
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²) | O(1) |
| Precomputed left and right maximums | O(n) | O(n) |
| Two pointers | O(n) | O(1) |
The problem
You are given an array of non-negative heights. Each is a solid bar one unit wide, and the bars stand side by side. After rain, water collects in the dips between taller bars. Return the total amount of water held.
[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] → 6
[4, 2, 0, 3, 2, 5] → 9
[1, 2, 3] → 0 (a staircase: everything runs off the left)The second example, drawn with # for bar and ~ for water:
#
# ~ ~ ~ ~ #
# ~ ~ # ~ #
# # ~ # # #
# # ~ # # #
4 2 0 3 2 5Nine ~ cells, so the answer is 9.
The key idea: think about one bar at a time
Trying to find the "pools" and measure each one is awkward. It is far easier to ask how much water sits directly above one bar, then add that up for every bar.
Water above a bar is held in by the tallest bar somewhere to its left and the tallest bar somewhere to its right. It rises to the lower of those two walls and no further, because it would spill over the lower one. So:
water above bar i = min(tallest on the left, tallest on the right) − height of bar iwhere "tallest on the left" and "tallest on the right" both include bar i itself, which stops the result going negative.
For the bar of height 0 at index 2 in [4, 2, 0, 3, 2, 5]: the tallest on the left is 4, the tallest on the right is 5, so the water level is 4 and the bar holds 4 − 0 = 4.
All three approaches use this formula. They differ only in how they find the two maximums.
Approach 1: brute force
For each bar, scan left and scan right to find the two maximums.
JavaScript
function trapRainWaterBruteForce(heights) {
let water = 0;
for (let i = 0; i < heights.length; i++) {
let leftMax = 0;
for (let j = 0; j <= i; j++) leftMax = Math.max(leftMax, heights[j]);
let rightMax = 0;
for (let j = i; j < heights.length; j++) rightMax = Math.max(rightMax, heights[j]);
water += Math.min(leftMax, rightMax) - heights[i];
}
return water;
}Python
def trap_rain_water_brute_force(heights):
water = 0
for i in range(len(heights)):
left_max = max(heights[: i + 1])
right_max = max(heights[i:])
water += min(left_max, right_max) - heights[i]
return waterTime O(n²): every bar triggers a scan of the whole array. Space O(1).
Approach 2: precomputed maximums
The scans repeat the same work. The tallest bar up to position i is either the tallest up to i − 1 or bar i itself, so all the left maximums can be filled in with one pass from the left, and all the right maximums with one pass from the right.
JavaScript
function trapRainWaterPrefix(heights) {
const n = heights.length;
const leftMax = new Array(n).fill(0);
const rightMax = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
leftMax[i] = Math.max(heights[i], i > 0 ? leftMax[i - 1] : 0);
}
for (let i = n - 1; i >= 0; i--) {
rightMax[i] = Math.max(heights[i], i < n - 1 ? rightMax[i + 1] : 0);
}
let water = 0;
for (let i = 0; i < n; i++) {
water += Math.min(leftMax[i], rightMax[i]) - heights[i];
}
return water;
}Python
def trap_rain_water_prefix(heights):
n = len(heights)
left_max = [0] * n
right_max = [0] * n
for i in range(n):
left_max[i] = max(heights[i], left_max[i - 1] if i > 0 else 0)
for i in range(n - 1, -1, -1):
right_max[i] = max(heights[i], right_max[i + 1] if i < n - 1 else 0)
water = 0
for i in range(n):
water += min(left_max[i], right_max[i]) - heights[i]
return waterFor [4, 2, 0, 3, 2, 5]:
| Index | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| Height | 4 | 2 | 0 | 3 | 2 | 5 |
| leftMax | 4 | 4 | 4 | 4 | 4 | 5 |
| rightMax | 5 | 5 | 5 | 5 | 5 | 5 |
| Water level (the lower) | 4 | 4 | 4 | 4 | 4 | 5 |
| Water held | 0 | 2 | 4 | 1 | 2 | 0 |
The bottom row adds up to 9.
Time O(n): three passes. Space O(n) for the two extra arrays.
Approach 3: two pointers
The two arrays can be replaced by two running values. Put a pointer at each end, with leftMax and rightMax holding the tallest bar each pointer has passed so far. At each step, look at the two bars under the pointers and process the lower one: update its side's maximum, add the water above it, and move that pointer inwards. This is the opposite-ends form of the two pointers pattern.
JavaScript
function trapRainWater(heights) {
let left = 0;
let right = heights.length - 1;
let leftMax = 0;
let rightMax = 0;
let water = 0;
while (left < right) {
if (heights[left] < heights[right]) {
leftMax = Math.max(leftMax, heights[left]);
water += leftMax - heights[left];
left++;
} else {
rightMax = Math.max(rightMax, heights[right]);
water += rightMax - heights[right];
right--;
}
}
return water;
}Python
def trap_rain_water(heights):
left = 0
right = len(heights) - 1
left_max = 0
right_max = 0
water = 0
while left < right:
if heights[left] < heights[right]:
left_max = max(left_max, heights[left])
water += left_max - heights[left]
left += 1
else:
right_max = max(right_max, heights[right])
water += right_max - heights[right]
right -= 1
return waterNotice that the formula has lost its min. On the left branch the code adds leftMax − height without ever looking at the right maximum. The next section explains why that is allowed.
Walkthrough
[4, 2, 0, 3, 2, 5]:
| left (height) | right (height) | Lower side | Its max | Water added | Total |
|---|---|---|---|---|---|
| 0 (4) | 5 (5) | left | 4 | 4 − 4 = 0 | 0 |
| 1 (2) | 5 (5) | left | 4 | 4 − 2 = 2 | 2 |
| 2 (0) | 5 (5) | left | 4 | 4 − 0 = 4 | 6 |
| 3 (3) | 5 (5) | left | 4 | 4 − 3 = 1 | 7 |
| 4 (2) | 5 (5) | left | 4 | 4 − 2 = 2 | 9 |
The pointers meet at index 5 and the loop ends with 9. The right pointer never moved, because the bar of height 5 was the taller side at every step.
Time O(n): one pass, each step moving one pointer. Space O(1).
Why the lower side can be settled straight away
The loop keeps one fact true at every step: the taller of the two bars under the pointers is at least as tall as every bar already passed, on either side.
It holds at the start, when nothing has been passed. And each step preserves it: the pointer that moves is always the one on the lower bar (or an equal one), so the tallest bar seen so far is never left behind. It stays under a pointer until something at least as tall turns up at the other one.
Now take a step where heights[left] < heights[right].
- By that fact,
heights[right]is at least as tall as everything passed on the left, so after updating,leftMax ≤ heights[right]. - The true tallest bar to the right of
leftis at leastheights[right], since that bar is one of them. - Putting those together, the left maximum is the lower of the two walls.
min(leftMax, true rightMax)is simplyleftMax.
So the water above left is leftMax − heights[left], and it is known for certain without having seen the bars between the pointers. The right branch is the same argument reflected.
This is the same reasoning as Container With Most Water: the lower side is the one that limits the water, so it is the one that can be dealt with and discarded.
Try it yourself
Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.
JavaScript
console.log(trapRainWater([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])); // 6
console.log(trapRainWater([4, 2, 0, 3, 2, 5])); // 9Python
print(trap_rain_water([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])) # 6
print(trap_rain_water([4, 2, 0, 3, 2, 5])) # 9The comment after each line is the result you should see.
Common mistakes
- Trying to measure pools. Detecting where each dip starts and ends leads to tangled code. Summing bar by bar avoids it.
- Leaving the bar itself out of the maximums. If
leftMaxexcludes bari, a bar taller than everything to its left produces negative water. Update the maximum first, then subtract. - Advancing the taller side in the two-pointer version. The proof only covers the lower side; moving the taller one adds water that may spill.
- Expecting the end bars to hold water. Nothing stands outside them, so the first and last bars always hold zero.
- Confusing this with Container With Most Water. There the bars between the chosen pair are ignored. Here they are solid and take up room.
Original problem: LeetCode 42: Trapping Rain Water