Trapping Rain Water
Given n non-negative integers height representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. A precomputed-max approach stores a leftMax array and a rightMax array and needs O(n) extra space for both. Two pointers get the same answer in O(1) space by walking from both ends at once and only ever tracking the running max on each side. At every step, advance whichever side has the smaller current height , because that side's own running max is already the true bound on the water trapped there — the taller side could only raise the bound, never lower it.
Constraints
- n == height.length
- 1 ≤ n ≤ 2 × 104
- 0 ≤ heighti ≤ 105
Example
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]6Explanation Water pools above the low bars between the two tall walls at indices 7 and 10 (and the smaller wall at index 3), trapping 6 total units.
In plain terms
- Elevation map
- A row of numbers where each number is the height of a bar at that spot, like a bar chart of hills and valleys side by side — for example [0, 2, 0] is a short wall, a dip, then a tall wall.
Close in from both ends, tracking leftMax and rightMax
left=0 (0), right=11 (1), leftMax=0, rightMax=0, trapped=0. height[left] <= height[right], so advance left.
What happens in this step
left = 0 (height 0), right = 11 (height 1) height[left] 0 <= height[right] 1 -> work the left side height[left] 0 >= leftMax 0 -> leftMax stays 0 The left bar is the shorter side, and it is already its own new high, so nothing traps yet — left advances from index 0 to index 1.
Steps to visualize
- Place left at index 0 and right at the last index, with leftMax and rightMax both starting at 0.
- Compare heightleft and heightright; move the pointer on the shorter side.
- If that side is a new high for its running max, raise the max instead of trapping water.
- Otherwise, the running max on that side already bounds the water there — add max minus the current height.
- Keep closing the gap until left and right meet.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
left=0 (0), right=11 (1), leftMax=0, rightMax=0, trapped=0. height[left] <= height[right], so advance left.
What happens in this step
left = 0 (height 0), right = 11 (height 1) height[left] 0 <= height[right] 1 -> work the left side height[left] 0 >= leftMax 0 -> leftMax stays 0 The left bar is the shorter side, and it is already its own new high, so nothing traps yet — left advances from index 0 to index 1.
Solution
function trap(height) {
if (!height || height.length < 3) return 0;
let left = 0;
let right = height.length - 1;
let leftMax = 0;
let rightMax = 0;
let water = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
water += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
water += rightMax - height[right];
}
right--;
}
}
return water;
}- Time
- O(n)
- Space
- O(1)
Test cases
| Input | Expected | Covers |
|---|---|---|
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] | 6 | example from the docstring |
height = [4, 2, 0, 3, 2, 5] | 9 | second well-known LeetCode example |
height = [5, 0, 0, 0, 5] | 15 | symmetric bowl shape traps water evenly across the floor |
height = [3, 0, 3] | 3 | smallest non-trivial valley between two equal walls |
height = [3, 3, 3, 3] | 0 | flat/uniform heights trap no water |
height = [1, 2, 3, 4, 5] | 0 | monotonic increasing array has nothing to trap |
height = [5, 4, 3, 2, 1] | 0 | monotonic decreasing array has nothing to trap |
height = [] | 0 | empty array traps no water |
height = [5] | 0 | a single bar cannot trap water |
height = [3, 4] | 0 | two bars cannot form a basin |