Problem overview
The function trap receives a vector height of non-negative integers. Each value is the height of a bar of width 1 in an elevation map. After rain, water collects in the gaps between bars. The function returns how many units of water the map holds.
For height = [4, 2, 0, 3, 2, 5] the answer is 9. Over the bar of height 2 at index 1 the water is 2 units deep, over the 0 it is 4, over the 3 it is 1 and over the 2 at index 4 it is 2. That sums to 9. The outer bars, 4 and 5, hold nothing. For [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] the answer is 6.
Approach: water above a bar depends on the walls on both sides
Look at one bar at a time. Water above bar i can rise only as high as the lower of two walls: the tallest bar at or to the left of i, and the tallest bar at or to the right of i. If it rose higher than the lower wall, it would spill over that side. The bar itself takes up the bottom of the column, so the depth over bar i is:
min(tallest to the left, tallest to the right) - height[i]Both "tallest" values include bar i, so the difference is never negative. At the tallest bar of the whole map, both walls are the bar itself, and the depth is 0.
Computing the two maxima for every bar by scanning outward would be O(n²). But the maxima build on each other. The tallest bar up to i is the larger of the tallest bar up to i - 1 and height[i]. This is the dynamic programming: each entry reuses the one before it. Two arrays, left_max filled from the left and right_max filled from the right, give every bar's walls in O(n) total. A last pass adds up the depths.
For [4, 2, 0, 3, 2, 5] the arrays are:
left_max = [4, 4, 4, 4, 4, 5]
right_max = [5, 5, 5, 5, 5, 5]The minimum at each index is [4, 4, 4, 4, 4, 5]. Subtracting the heights gives [0, 2, 4, 1, 2, 0], which sums to 9.
Step by step
- Store the length as
n.len()returns ausize, the type of indexes. - Return 0 for an empty vector. The next lines read
height[0], which needs at least one bar. - Create
left_maxasnzeros and set the first entry toheight[0], because nothing comes before the first bar. - Loop
iover1..n. Index 0 is already set. - Extend the maximum:
left_max[i]is the larger ofleft_max[i - 1]andheight[i]. - Create
right_maxthe same way and set its last entry toheight[n - 1]. - Loop
iover(0..n - 1).rev(), fromn - 2down to 0. - Extend the maximum from the right:
right_max[i]is the larger ofright_max[i + 1]andheight[i]. - Start the total as a mutable
resultof typei32. - Loop over every bar with
0..n. - Add the water over bar
i: the smaller of the two maxima minusheight[i]. - Return
result.
The solution in Rust
impl Solution {
fn trap(height: Vec<i32>) -> i32 {
let n = height.len();
if n == 0 {
return 0;
}
let mut left_max = vec![0i32; n];
left_max[0] = height[0];
for i in 1..n {
left_max[i] = left_max[i - 1].max(height[i]);
}
let mut right_max = vec![0i32; n];
right_max[n - 1] = height[n - 1];
for i in (0..n - 1).rev() {
right_max[i] = right_max[i + 1].max(height[i]);
}
let mut result = 0i32;
for i in 0..n {
result += left_max[i].min(right_max[i]) - height[i];
}
result
}
}
The Rust details worth a look:
vec![0i32; n]builds a vector ofncopies of 0. Thei32suffix fixes the element type so it matches the heights.maxandminare methods on integers:a.max(b)returns the larger value.(0..n - 1).rev()counts down. A hand-written countdown on ausizeindex with the testi >= 0is always true, because ausizecan't go below 0, so it would run past index 0. Reversing a range avoids that. The range is empty whennis 1, so the loop is skipped.- The empty check protects
n - 1. Forn = 0,n - 1on ausizewould wrap in an optimized build or panic in a debug build. Returning early keeps both paths safe. The constraints saynis at least 1, but the guard costs nothing. - Indexing is checked. An out-of-range index such as
left_max[n]panics. All the indexes here stay in0..n. - No overflow. The water over a bar is at most 10,000, and there are at most 30,000 bars, so the total is below 300,000,000, which fits in
i32. resultas the last line has no semicolon, so it is the value the function returns.
Complexity
Time: O(n). There are three loops over the bars, each doing constant work per bar.
Space: O(n). left_max and right_max each hold one integer per bar. A two-pointer version can cut this to O(1), but this lesson keeps the two arrays because they make the idea easy to see.
Edge cases and common mistakes
- A single bar.
[5]holds no water: both maxima are 5, and the depth is 0. - Rising or falling maps.
[1, 2, 3, 4]gives 0, because the tallest bar up to each bar is the bar itself, so every depth is 0. - A single pit.
[3, 0, 3]gives 3: the walls are 3 and 3 and the pit bar is 0. - Using only one side. Subtracting
height[i]from the left maximum alone counts water that would run off the right side. - Forgetting to take the minimum. The water level is set by the lower wall. Using the higher one overcounts.
- Excluding the bar from the maxima. If a maximum didn't include bar
i, a tall bar could produce a negative depth. Including it keeps every term at 0 or more.
Testing
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]gives 6.height = [4, 2, 0, 3, 2, 5]gives 9.height = [3, 0, 3]gives 3.height = [1, 2, 3, 4]gives 0.height = [5]gives 0.
