Problem overview
The method trap receives height, an array of non-negative integers describing an elevation map. Each number is the height of a bar, and every bar is 1 unit wide. After rain, water collects in the dips between taller bars. The method returns how many units of water stay trapped.
For [4, 2, 0, 3, 2, 5] the answer is 9. The two outer bars, 4 and 5, are walls. Between them, the bars 2, 0, 3 and 2 hold water up to level 4, the lower of the walls 4 and 5, as the next section explains. That is 2 + 4 + 1 + 2 = 9 units. The bars have at least one element and at most 30,000, each up to 10,000 high.
Approach: each bar holds its own column of water
Instead of thinking about whole pools, ask how much water sits directly above one bar. Water above bar i rises to the lower of two heights: the tallest bar anywhere to its left (including itself) and the tallest bar anywhere to its right (including itself). Water at a higher level would spill over the lower wall. The bar itself takes up the bottom of the column, so the water above it is
min(tallest on the left, tallest on the right) - height[i]The total is the sum of this value over all bars. Because both maximums include bar i, the minimum is at least height[i], so the difference is never negative.
The straightforward way scans left and right from every bar to find the two maximums, which takes O(n) per bar and O(n²) overall. This lesson precomputes them instead. Two arrays do it:
leftMax[i]is the tallest bar among positions 0 toi.rightMax[i]is the tallest bar among positionsiton - 1.
Each entry builds on its neighbour: leftMax[i] is the larger of leftMax[i - 1] and height[i]. Reusing earlier answers like that is dynamic programming.
For [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] the arrays are:
height 0 1 0 2 1 0 1 3 2 1 2 1
leftMax 0 1 1 2 2 2 2 3 3 3 3 3
rightMax 3 3 3 3 3 3 3 3 2 2 2 1
water 0 0 1 0 1 2 1 0 0 1 0 0 (total 6)Step by step
- Store the length in a
constnamedn, since every loop uses it. - Return 0 for no bars. The next lines read
height[0], which needs at least one bar. - Create
leftMaxwithnzeros and setleftMax[0]toheight[0], since nothing is to the left of the first bar. - Loop from index 1 up to
n - 1. Index 0 is already set. - Take the larger of
leftMax[i - 1]andheight[i]withMath.max. - Create
rightMaxthe same way, and set its last element to the last bar. - Loop backwards from
n - 2down to 0. - Take the larger of
rightMax[i + 1]andheight[i]. - Create
resultwithlet, starting at 0. - Loop over every bar.
- Add the column's water: the smaller of
leftMax[i]andrightMax[i], minusheight[i]. - Return
result.
The solution in TypeScript
class Solution {
trap(height: number[]): number {
const n = height.length;
if (n === 0) return 0;
const leftMax: number[] = new Array(n).fill(0);
leftMax[0] = height[0];
for (let i = 1; i < n; i++) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
const rightMax: number[] = new Array(n).fill(0);
rightMax[n - 1] = height[n - 1];
for (let i = n - 2; i >= 0; i--) {
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}
let result = 0;
for (let i = 0; i < n; i++) {
result += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return result;
}
}
The TypeScript details worth knowing:
new Array(n).fill(0).new Array(n)creates an array of lengthnwith empty slots, andfill(0)writes a 0 into each. Without thefill, the slots would be empty instead of 0. Here every slot is overwritten anyway, but a filled array is the safe habit, and it keeps the array a plain list of numbers.- The annotation
number[]is only for the compiler and is erased in the JavaScript.new Array(n)is typedany[], and the annotation gives the variable its precise type. Math.maxandMath.mintake any number of arguments and return a plainnumber. Here each call has two.- No overflow worry. A
numberis a double and holds integers exactly up to 2^53. The most water possible is about 30,000 × 10,000 = 300 million, far below that. constarrays can still change.leftMax[i] = ...changes the contents, whichconstallows. Only reassigning the variable itself is forbidden.
Complexity
Time: O(n). There are three passes over the bars, and each does a constant amount of work per bar.
Space: O(n). leftMax and rightMax each hold n numbers. A two-pointer version needs only O(1) extra space, but it takes more care to see why it is correct. The arrays make the idea easy to see.
Edge cases and common mistakes
- One or two bars.
[3]gives 0, and so does any array with fewer than three bars, since water needs a wall on each side. - Monotonic bars.
[1, 2, 3]gives 0: each bar is its own left maximum, so its column has nothing above it. - A single pit.
[3, 0, 3]gives 3. The middle bar has both maximums equal to 3. - Uneven walls.
[2, 0, 2, 0, 1]gives 3: the pit between the 2s holds 2 units, and the pit between 2 and 1 holds 1 unit, since the lower wall, 1, sets that level. - Using only one maximum. Subtracting
height[i]fromleftMax[i]alone ignores the right wall and counts water that would run off. - Using
maxinstead ofmin. Water can't rise above the lower wall, so using the taller one overcounts. - Starting the right loop at
n - 1. That would readrightMax[n], which isundefined, andMath.max(undefined, x)isNaN. The whole array after it would be corrupted.
Testing
[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]gives6.[4, 2, 0, 3, 2, 5]gives9.[3, 0, 3]gives3.[1, 2, 3]gives0.[3]gives0.
