Trapping Rain Water

TWO POINTERS · HARD

Builds on Day 4: Two-Pointer Pattern

The optimal solution below is a direct application of “walk two pointers toward each other, always advancing whichever side is provably safe to resolve” — read that lesson first if the idea of narrowing a window from both ends at once still feels unfamiliar.

The problem

You’re given an array of non-negative integers representing an elevation map: each index is a bar of width 1, and its value is the bar’s height. After it rains, water pools in the low spots between taller bars — picture the whole array as a bumpy skyline, then flood it until no more water can be added without spilling off one of the two open ends. Compute the total volume of water trapped, in unit squares (one bar-width × one unit of height). A bar only holds water above it if there’s a bar at least as tall somewhere to its left and somewhere to its right — a bar with nothing but shorter bars on one side (the tallest bar in the whole array, or either end bar) holds nothing, because water would just run off that open side. Example: height = [0,1,0,2,1,0,1,3,2,1,2,1] → 6 units trapped. height = [4,2,0,3,2,5] → 9 units trapped.

Solution 1: Brute force — rescan left and right from scratch for every index

The most literal reading of the problem: for every single bar, ask “what’s the tallest bar to my left, and what’s the tallest bar to my right?” and answer that by actually looking — scanning outward from the current index in both directions, every time, throwing away whatever the previous index’s scan already found. The water above index i is min(maxLeft, maxRight) - height[i], clamped to 0 when that comes out negative (a bar taller than at least one of its walls holds nothing). This is correct — it directly implements the problem’s own definition — but it’s wasteful: index 5’s left-scan and index 6’s left-scan overlap almost entirely, and neither one remembers what the other found.

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] — total water trapped: 6 units

Press play to run the brute force solution.

Step 0 / 38

▶ Play — O(n²)↺ Reset

The code

function trapBrute(height) {
  const n = height.length;
  let total = 0;

  for (let i = 0; i < n; i++) {
    let maxLeft = 0;
    for (let l = i; l >= 0; l--) {
      maxLeft = Math.max(maxLeft, height[l]);
    }

    let maxRight = 0;
    for (let r = i; r < n; r++) {
      maxRight = Math.max(maxRight, height[r]);
    }

    const water = Math.min(maxLeft, maxRight) - height[i];
    if (water > 0) {
      total += water;
    }
  }

  return total;
}

Line by line:

• The outer loop visits every index i exactly once — that part alone is O(n).
• The first inner loop walks from i down to 0, tracking the tallest bar seen — this is maxLeft, starting fresh at 0 for every i, with no memory of any previous index’s scan.
• The second inner loop walks from i up to n - 1 the same way for maxRight. Both inner loops include height[i] itself, which is harmless — a bar can never be taller than itself, so including it never changes the max.
• Math.min(maxLeft, maxRight) - height[i] is the water level above i: water can only rise as high as the shorter of the two walls, since anything higher would spill over that shorter side.
• The if (water > 0) guard clamps negative results to nothing added — a bar taller than at least one of its walls (including the tallest bar in the whole array, which is taller than everything) holds zero water above it.
• Each of the two inner loops is O(n) in the worst case, run inside an O(n) outer loop — that’s the O(n²) this solution’s name implies.

Complexity

Time	Space	Approach
O(n²)	O(1)	Fresh left/right scan from every index

Solution 2: Optimal — two pointers, resolve whichever side has the smaller max

Maintain left/right pointers starting at the two ends of the array, and leftMax/rightMax tracking the tallest bar seen so far from each side. At each step, fold the current pointer’s own height into its max (leftMax = Math.max(leftMax, height[left]), symmetrically for the right), then compare the two running maxima — always leftMax against rightMax, never height[left] against height[right]. Whichever side has the smaller max gets resolved and its pointer moves inward:

• If leftMax <= rightMax, index left is safe to resolve. Its true left wall is exactly leftMax (every bar from 0 to left has already been folded in), and its true right wall is at least rightMax — because rightMax is only the max of the portion the right pointer has already visited, a subset of everything actually to the right of left, so the real right wall can only be taller. Since leftMax <= rightMax <= (true right wall), the smaller wall is provably leftMax — water above left is exactly leftMax - height[left], no matter what the unvisited middle of the array looks like.
• Symmetrically, if rightMax < leftMax, index right is safe to resolve the same way, using rightMax - height[right].

Each index gets folded into a max and resolved exactly once, by whichever pointer reaches it first — the loop runs until left === right, at which point every index has been accounted for.

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] — watch the pointers close in from both ends

Press play to run the optimal two-pointer solution.

Step 0 / 35

▶ Play — O(n)↺ Reset

The code

function trapOptimal(height) {
  let left = 0;
  let right = height.length - 1;
  let leftMax = 0;
  let rightMax = 0;
  let total = 0;

  while (left < right) {
    leftMax = Math.max(leftMax, height[left]);
    rightMax = Math.max(rightMax, height[right]);

    if (leftMax <= rightMax) {
      total += leftMax - height[left];
      left++;
    } else {
      total += rightMax - height[right];
      right--;
    }
  }

  return total;
}

Line by line:

• left = 0, right = height.length - 1 — the pointers start at the two open ends, since either end could turn out to be the array’s tallest bar.
• leftMax/rightMax start at 0 — bar heights are never negative in this problem, so 0 is a safe floor that never accidentally beats a real height (see the Interview Corner trick question below for why this specific choice of seed value matters more than it looks).
• while (left < right) — the moment the pointers meet, every index has already been resolved by whichever side reached it; there’s nothing left to compare.
• Folding height[left] into leftMax (and height[right] into rightMax) happens before the comparison, every iteration — this is the detail that makes the “compare the maxes” rule actually correct. Deciding based on stale maxima that haven’t yet accounted for the current pointer’s own height is a real bug; see the Interview Corner below for a concrete case where it silently returns the wrong answer.
• leftMax <= rightMax is the entire routing decision: the side with the provably-smaller wall gets resolved and its water added, then that pointer moves one step inward. The <= (not strict <) means ties resolve left — it doesn’t matter which side wins a tie, since leftMax === rightMax gives the same water contribution either way.
• When the loop exits, total already holds the full answer — there’s no separate finishing step, because the pointers meeting means the last remaining index was already folded into both maxima on a previous iteration.

Complexity

Time	Space	Approach
O(n)	O(1)	Two pointers, always resolving the side with the smaller max

Complexity comparison

Solution	Time	Space
Brute force (rescan from every index)	O(n²)	O(1)
Optimal (two pointers)	O(n)	O(1)

The real story here is purely about time, not space. Both solutions use only a constant handful of scalar variables — the brute force never allocates an array proportional to n, and neither does the two-pointer version, so both are honestly O(1) auxiliary space. The win going from brute force to optimal is a genuine asymptotic time improvement: O(n²) because every index triggers two fresh full-array scans, down to O(n) because the two-pointer version folds each bar into a running max and resolves it exactly once, never revisiting work it already did. (A middle-ground solution — precomputing leftMax[] and rightMax[] arrays in one forward and one backward pass — would also reach O(n) time, but at the cost of O(n) space for those two arrays; the two-pointer approach gets the same O(n) time and keeps the O(1) space the brute force already had, which is what actually makes it strictly better rather than just “different.”)

Interview corner

Q: Why is it always safe to resolve the side with the smaller max, rather than the side with the smaller current height?

• Say leftMax <= rightMax at some step. The true wall on the left of left is exactly leftMax — every bar from index 0 to left has already been folded into it, so there’s nothing left unseen on that side.
• The true wall on the right of left might be taller than the tracked rightMax, because rightMax only reflects the portion the right pointer has visited so far — the unvisited middle of the array could still hide a taller bar. But it can never be shorter than rightMax, since rightMax is itself a real bar that’s part of that same right-hand region.
• So the true right wall is at least rightMax, which is at least leftMax in this branch — meaning the true right wall is guaranteed >= the true left wall. The shorter of the two walls is therefore provably leftMax, regardless of what’s hiding in the unscanned middle, so leftMax - height[left] is exactly correct without ever looking further.

Q: What actually breaks if you decide which side to resolve using the maxima before folding in the current pointer’s own height, instead of after?

• Take height = [1, 3, 2, 6]. The correct answer is 1 (index 2 holds one unit, bounded by the wall of 3 on its left and 6 on its right).
• The buggy version compares leftMax/rightMax first, then only updates whichever side it already decided to move — so on the very first comparison, both are still 0, and a tie (0 <= 0) always routes left without that decision ever having accounted for height[0] = 1 or height[3] = 6 at all.
• Tracing it through: the buggy version ends up returning 0 for this array — silently wrong, with no error or crash. The correct version, which folds height[left]/height[right] into the maxima before comparing, correctly returns 1.
• The rule to remember: the comparison that decides direction has to reflect the current pointer’s own bar, not last iteration’s leftover state — otherwise you’re routing based on information that’s already out of date.
  • ↳ Common follow-up: “Could you catch this bug with a single test case?” Yes — any array where the very first comparison is a tie (both maxima at their starting value of 0) exposes it immediately, which is exactly why [1, 3, 2, 6] works as a minimal counterexample: it’s tiny, and the bug shows up on iteration one.

Q: The algorithm processes all n bars — why is it still described as O(1) space instead of O(n)?

• Big-O space complexity conventionally measures extra (auxiliary) memory the algorithm allocates beyond the input it was already given — not the size of the input itself, which the caller already paid for before the function was ever called.
• This solution only ever holds five scalar variables — left, right, leftMax, rightMax, total — no matter how large height is. Doubling the input size doesn’t add a sixth variable.
• Contrast that with an approach that precomputes leftMax[]/rightMax[] arrays: those genuinely grow with n, so that version is honestly O(n) space, even though it also reaches O(n) time. The two-pointer version is the one that keeps both dimensions minimal at once.

Q: Trick question — what does this log?

console.log(Math.max());
console.log(Math.max(...[]));
console.log(Math.min(...[]));

• Answer: all three log -Infinity, -Infinity, and Infinity respectively — not 0, and not an error.
• Math.max with zero arguments (including spreading an empty array into it) returns -Infinity — the mathematical identity element for “maximum,” since any real number is >= -Infinity. Math.min() mirrors it with +Infinity.
• This page’s leftMax/rightMax/maxLeft/maxRight all deliberately start at the literal 0, not at Math.max()’s built-in “empty” value — a safe choice here because bar heights in this problem are guaranteed non-negative, so 0 is a true floor no real height can go below.
• The trap: it’s tempting to rewrite a running-max loop as a one-liner like Math.max(...height.slice(0, i + 1)). That’s fine for every actual index in this problem (the slice always has at least the bar at i itself, so it’s never empty) — but the moment that same “just spread it into Math.max” habit gets reused somewhere the collection genuinely can be empty, it silently produces -Infinity instead of throwing or returning a sane default, and that -Infinity can propagate through arithmetic for a long time before anything visibly breaks.

Quiz

Note

The running max is what the correctness proof actually depends on — the smaller max side has a wall that’s provably exact, which the smaller-height comparison doesn’t guarantee

The side with the smaller running max is safe to resolve because its own wall is exact, while the other side’s true wall is only guaranteed to be at least as tall as its tracked max. Comparing heights directly wouldn’t give that guarantee.

Quiz: 2. What is the honest complexity story between the brute force and the two-pointer optimal?

A genuine time win only — O(n²) down to O(n) — while space stays O(1) on both sides

Both solutions use only a constant handful of scalar variables, so both are honestly O(1) space — there is no space improvement here. The real win is purely time: O(n²) rescanning from every index down to O(n), where each bar is folded into a max and resolved exactly once.

Quiz: 3. In the brute force solution, which indices need their maxLeft/maxRight computed by scanning outward?

Every index — the outer loop reruns both inner scans from scratch for each one, with no result ever reused between indices

Every bar always has an unambiguous left-max and right-max (even if one of them is the bar itself, at either array end). Brute force’s fresh outward scans compute this from scratch for every index no matter where it sits; the two-pointer version resolves every index exactly once by whichever pointer reaches it.

Note

0 — every bar only ever has a taller (or equal) wall on its left, never on its right, so nothing is ever trapped

A strictly decreasing array like [5,4,3,2,1] traps nothing: every bar’s tallest wall is on its left (itself, for the first bar), and there’s never a taller bar anywhere to the right to hold water in. Both solutions correctly return 0 with no special-casing.

Note

Comparing before folding in the current pointer’s own height uses stale maxima and can silently undercount the total — it’s a real, verifiable bug, not just a style choice

leftMax and rightMax must be updated to include the current pointer’s own height before the comparison that decides which side to resolve. Deciding first and updating only the chosen side afterward uses stale information and can silently return a wrong (too-low) total — verified against height = [1, 3, 2, 6], where the buggy ordering returns 0 instead of the correct 1.