Rain water trapped between walls
height[i] is the height of a wall of width 1 at position i. After rain, water collects
between the walls. Return the total amount of water held, in units of area.
Examples
| Input | Output | Why |
|---|---|---|
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] | 6 | |
height = [4, 2, 0, 3, 2, 5] | 9 | Water levels 4, 4, 4, 4 over the four inner columns: 2 + 4 + 1 + 2. |
Constraints
- 1 ≤ n ≤ 2 × 10⁴
- 0 ≤ height[i] ≤ 10⁵
Hints
Hint 1
Think one column at a time. How high does the water stand above column i?
Hint 2
It stands at min(tallest wall to the left, tallest wall to the right), including column i itself. Two arrays of prefix and suffix maxima give O(n) time and O(n) memory.
Hint 3
With pointers at both ends, keep the highest wall seen from the left and from the right. Whichever side has the lower maximum: that maximum is the water level at that pointer, whatever lies between.
Where people lose marks
- Moving the pointer on the side with the taller wall: the level there is not yet known, because the other side's maximum is the limit.
- Updating the running maximum after adding water instead of before, which can add a negative amount at a new tallest wall.
- Summing in a 32-bit integer: n × max height reaches 2 × 10⁹ at these limits, close to overflow.
Dry run on [3,0,2,0,4,1,2]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 9height30i012203441526jleftMax0rightMax0water0
i at the left, j at the right; no walls seen yet.
-
Step 2 / 9height30i012203441526jleftMax3rightMax2water0
rightMax 2 < leftMax 3, so the level at j = 6 is 2: water 2 − 2 = 0. j moves left.
-
Step 3 / 9height30i0122034415j26leftMax3rightMax2water1
rightMax 2 < leftMax 3, so the level at j = 5 is 2: water 2 − 1 = 1. j moves left.
-
Step 4 / 9height30i01220344j1526leftMax3rightMax4water1
leftMax 3 ≤ rightMax 4, so the level at i = 0 is 3: water 3 − 3 = 0. i moves right.
-
Step 5 / 9height3001i220344j1526leftMax3rightMax4water4
leftMax 3 ≤ rightMax 4, so the level at i = 1 is 3: water 3 − 0 = 3. i moves right.
-
Step 6 / 9height300122i0344j1526leftMax3rightMax4water5
leftMax 3 ≤ rightMax 4, so the level at i = 2 is 3: water 3 − 2 = 1. i moves right.
-
Step 7 / 9height30012203i44j1526leftMax3rightMax4water8
leftMax 3 ≤ rightMax 4, so the level at i = 3 is 3: water 3 − 0 = 3. i moves right.
-
Step 8 / 9height3001220344i/j1526leftMax4rightMax4water8
leftMax 4 ≤ rightMax 4, so the level at i = 4 is 4: water 4 − 4 = 0. i moves right.
-
Step 9 / 9height30012203441526water8
Every column is done: 8 units of water.
How to think about it
Over column i the water level is min(L(i), R(i)), where L(i) is the tallest wall
from the left end to i and R(i) the tallest from i to the right end. The water there is that level
minus height[i].
Keep i at the left and j at the right, with leftMax the tallest wall in
[0, i] and rightMax the tallest in [j, n − 1]. Suppose
leftMax ≤ rightMax. Then for column i, L(i) = leftMax exactly, and
R(i) ≥ rightMax ≥ leftMax, because the walls between i and j can only raise R(i). So the level at i is
leftMax, known now, without looking at the middle. Add leftMax − height[i] and advance
i. Otherwise the same holds for j from the other side.
Complexity. Time O(n) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def trapped_water(height):
i, j = 0, len(height) - 1
left_max = right_max = total = 0
while i <= j:
left_max = max(left_max, height[i])
right_max = max(right_max, height[j])
if left_max <= right_max: # the level at i is left_max, whatever is between
total += left_max - height[i]
i += 1
else: # the level at j is right_max
total += right_max - height[j]
j -= 1
return total#include <vector>
#include <algorithm>
long long solve(const std::vector<int>& h) {
int i = 0, j = (int)h.size() - 1, leftMax = 0, rightMax = 0;
long long total = 0;
while (i <= j) {
leftMax = std::max(leftMax, h[i]);
rightMax = std::max(rightMax, h[j]);
if (leftMax <= rightMax) { total += leftMax - h[i]; ++i; } // level at i is leftMax
else { total += rightMax - h[j]; --j; } // level at j is rightMax
}
return total;
}class Solution {
public long trappedWater(int[] height) {
int i = 0, j = height.length - 1, leftMax = 0, rightMax = 0;
long total = 0;
while (i <= j) {
leftMax = Math.max(leftMax, height[i]);
rightMax = Math.max(rightMax, height[j]);
if (leftMax <= rightMax) { total += leftMax - height[i]; i++; } // level at i is leftMax
else { total += rightMax - height[j]; j--; } // level at j is rightMax
}
return total;
}
}function trappedWater(height) {
let i = 0, j = height.length - 1, leftMax = 0, rightMax = 0, total = 0;
while (i <= j) {
leftMax = Math.max(leftMax, height[i]);
rightMax = Math.max(rightMax, height[j]);
if (leftMax <= rightMax) { total += leftMax - height[i]; i++; } // level at i is leftMax
else { total += rightMax - height[j]; j--; } // level at j is rightMax
}
return total;
}fn solve(h: &[i64]) -> i64 {
// [i, j) is still to do; the half-open window keeps j from going below zero
let (mut i, mut j) = (0usize, h.len());
let (mut left_max, mut right_max, mut total) = (0i64, 0i64, 0i64);
while i < j {
left_max = left_max.max(h[i]);
right_max = right_max.max(h[j - 1]);
if left_max <= right_max { total += left_max - h[i]; i += 1; } // level at i is left_max
else { total += right_max - h[j - 1]; j -= 1; } // level at j - 1 is right_max
}
total
}import Data.Array
solve :: [Int] -> Int
solve hs = go 0 (n - 1) 0 0 0
where
n = length hs
h = listArray (0, n - 1) hs
go i j lm rm total
| i > j = total
| lm' <= rm' = go (i + 1) j lm' rm' (total + lm' - h ! i) -- level at i is lm'
| otherwise = go i (j - 1) lm' rm' (total + rm' - h ! j) -- level at j is rm'
where lm' = max lm (h ! i)
rm' = max rm (h ! j)Variants to try
- A monotonic stack gives another O(n) solution that adds water layer by layer as each enclosing wall appears.
- The two-dimensional version (water on a height map) needs a priority queue grown from the border inward.
Next problems
A palindrome, ignoring punctuation and case
Compare from both ends inward, stepping over anything that is not a letter or a digit. No cleaned copy of the string is needed.
Open the problem → Easy10 minMerge two sorted arrays
The step at the heart of merge sort: one pointer per array, and the smaller front value goes next.
Open the problem → Easy10 minMove the zeros to the end
One pointer reads every element, the other marks where the next non-zero belongs. The order of the non-zero values is kept.
Open the problem →Write a solution and run it against the real test table.
Keep going
A palindrome, ignoring punctuation and case
Compare from both ends inward, stepping over anything that is not a letter or a digit. No cleaned copy of the string is needed.
Open the problem → Easy10 minMerge two sorted arrays
The step at the heart of merge sort: one pointer per array, and the smaller front value goes next.
Open the problem → Easy10 minMove the zeros to the end
One pointer reads every element, the other marks where the next non-zero belongs. The order of the non-zero values is kept.
Open the problem → Two pointersThe pattern behind it
Two indices walking a sorted or paired structure, each step ruling out one candidate for good.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.