You are given an array height where height[i] is the height of a vertical bar of unit width at position i. Together the bars form an elevation map.
After it rains, water collects in the dips between taller bars. Return the total units of water that can be trapped.
Water sits above position i only up to the lower of the tallest bar to its left and the tallest bar to its right; the amount at i is min(maxLeft, maxRight) - height[i] when positive, else 0.
Example
The dips between the bars hold 6 units of water in total.
Constraints
- 1 <= height.length <= 2 * 10^4
- 0 <= height[i] <= 10^5
Intuition
Water sitting above a bar is capped by min(tallestLeft, tallestRight) − height. A first pass just computes that directly: for every bar, scan all the way left for the tallest wall and all the way right for the tallest wall, then add whatever sits on top.
function trap(height) {
let water = 0;
// For each bar, find the walls that bound the water above it.
for (let i = 0; i < height.length; i++) {
let left = 0, right = 0;
// Tallest wall to the left of (and including) bar i.
for (let j = 0; j <= i; j++) left = Math.max(left, height[j]);
// Tallest wall to the right of (and including) bar i.
for (let j = i; j < height.length; j++) right = Math.max(right, height[j]);
// The shorter wall sets the water level; subtract the bar's own height.
water += Math.min(left, right) - height[i];
}
return water;
}This is O(n²) — every bar triggers two full rescans for maxima we keep recomputing. Can we do better?
The key observation: a bar's water level is set by the shorter of its two bounding walls. So if we watch from both ends with two pointers and compare the two current bars, the side with the shorter bar is the one whose answer we can already commit. Whatever taller wall waits beyond the far pointer can only raise the other side's max, never the shorter side's binding wall — so the shorter side's running max is already its true left-or-right wall.
That converge-from-both-ends move is the Two pointers pattern: advance whichever side is shorter, fold its bar into that side's running max, and bank runningMax − height as trapped water. One linear pass, no rescans, O(1) space.
Walking it through:
height = [3, 0, 1, 0, 5, 2] — move the shorter side
Right bar is the shorter side, so we settle it first. Its running max is just itself (2), so no water — move right inward.
Now the left bar (3) is the shorter side, so the move flips to the left. Lmax becomes 3; the bar fills its own wall, so +0.
A dip below Lmax 3. Add 3 − 0 = 3. Total 3.
Add 3 − 1 = 2. Total 5. Lmax is the safe wall — the 5 still parked at R guarantees the right wall is at least as tall.
Another dip. Add 3 − 0 = 3. Total 8 — the pointers now meet, so that's the answer.
Optimization
Two pointers
Walk inward from both ends, tracking the tallest bar seen so far on the left (leftMax) and right (rightMax). Advance whichever side currently has the shorter bar: for that position the smaller of the two running maxima is the controlling wall, so the water above it is runningMax - height. Because you only move the shorter side, the chosen running max is provably the true bounding wall.
O(n) time, O(1) space.
function trap(height) {
// Two pointers converging from both ends.
let left = 0;
let right = height.length - 1;
// Tallest bar seen so far on each side; these are the candidate walls.
let leftMax = 0;
let rightMax = 0;
let total = 0;
while (left < right) {
// Settle the side with the shorter bar: a taller bar beyond the far
// pointer can only raise the other side's wall, so this side's running
// max is already its true bounding wall.
if (height[left] < height[right]) {
leftMax = Math.max(leftMax, height[left]);
// Water above this bar is its left wall minus its own height.
total += leftMax - height[left];
left++;
} else {
rightMax = Math.max(rightMax, height[right]);
total += rightMax - height[right];
right--;
}
}
return total;
}Complexity analysis
Time complexity: O(n). Here's why:
- The two pointers start at opposite ends and only ever move toward each other.
- Each step compares the two current bars, updates one running max, and banks any water in O(1) before advancing exactly one pointer.
Together the pointers cover every bar once before they meet, so the whole pass is O(n) — no rescans, no nesting, where n is the number of bars.
Space complexity: O(1). Here's why:
- It keeps only the two pointers, the two running maxima, and a running
total. - The input is read in place; nothing is copied or accumulated into an auxiliary structure.
No storage grows with the input, so the extra space is constant — O(1). (The classic prefix-max / suffix-max solution computes the same answer but stores two O(n) arrays.)
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| height = [] | 0 | Empty elevation map — no bars, so nothing to trap. |
| height = [7] | 0 | Single bar — water needs a wall on both sides. |
| height = [1,2,3] | 0 | Strictly increasing — every bar's left wall is shorter than itself, so nothing collects. |
| height = [4,4,4] | 0 | Flat profile — equal walls leave no dip to fill. |
| height = [3,0,2,0,4] | 7 | A valley between rising walls — the two dips fill to the shorter bounding wall. |
| height = [6,1,1,1,6] | 15 | Tall equal ends over a flat trench — each of the three inner bars holds 6 − 1 = 5. |
Try it yourself
Write your solution against the real judge before checking the reference.