42. Trapping Rain Water

Given an elevation map, compute how much rainwater is trapped between the bars after it rains. The key insight: water above any bar equals the minimum of the tallest bars to its left and right minus its own height. Two inward-moving pointers track running maxima so you can compute this in O(n) time and O(1) space.

● HardTwo PointersRunning MaximumArrayTypeScript

PROBLEM What we're solving

You receive an array height of non-negative integers. Each element is the height of a vertical bar of width 1. After rain, how many units of water are trapped between the bars?

Worked example: height = [0,1,0,2,1,0,1,3,2,1,2,1] → the answer is 6. The tall bar at index 7 (height 3) acts as the right wall for several shallow pits on its left; the bars at indices 2, 4, and 5 each trap 1–2 units.

KEY IDEA Water level = min(leftMax, rightMax) − height[i]

Insight → Water above bar i is determined by the shorter of the two tallest walls on either side: water[i] = min(leftMax[i], rightMax[i]) − height[i]. You don't need to know both walls simultaneously — two inward-moving pointers let you process whichever side has the shorter known wall, because that side's water level is already fully determined by its own running max.

When height[l] <= height[r], we know leftMax <= rightMax (since height[r] is at least as tall), so the water at l is exactly leftMax − height[l] — the right wall is guaranteed to be taller. We can safely add water and advance l.

RECIPE Advance the shorter pointer, accumulate water

0 · Initialise. Place l=0, r=n−1, leftMax=rightMax=water=0. Two pointers squeeze inward.
1 · Compare heights. At each step, look at height[l] vs height[r]. The shorter side is the bottleneck — its water level is capped by its own running max, not the far side.
2 · Process the shorter side. Update that side's running max, then add runningMax − height[ptr] to water. (If the bar is taller than the max, the difference is 0 — no water, just a new max.)
3 · Advance the pointer. Move the shorter-side pointer one step inward and repeat. Equal heights: process either (left is conventional).
4 · Done. Loop ends when l == r. Return water.

Classic confusion → Beginners think you need the full leftMax and rightMax arrays (O(n) space) before you can start. The two-pointer version computes the water on the fly by relying on the invariant that whichever pointer points to the shorter current height, the opposite side is guaranteed to be at least as tall — so the running max on the shorter side is the true limiting wall.

COST Complexity & alternatives

Precompute leftMax/rightMax arrays

O(n) space

Correct, simple, but wastes an extra O(n) array.

Two pointers (running max)

O(n) · O(1)

Single pass, constant space — the interviewer target.

Both approaches run in O(n) time. The stack-based approach (monotonic stack, LeetCode's official editorial) is also O(n) / O(n) and computes water horizontallyby layer rather than column-by-column; it's correct but harder to explain in an interview.

Pattern transfer → The running-max two-pointer idea recurs in Container With Most Water (LC 11 — same inward-squeeze, different formula), Largest Rectangle in Histogram (LC 84 — monotonic stack on heights), and Product of Array Except Self (two running products from both ends).

RUN IT Advance the shorter wall, trap water on that side

height =

step 0 / 12

STARTTwo pointers: l=0, r=11. We'll advance whichever side has the shorter boundary.

1function trap(height: number[]): number {
2▶  let l = 0, r = height.length - 1;
3▶  let leftMax = 0, rightMax = 0;
4▶  let water = 0;
5 
6  while (l < r) {
7    if (height[l] <= height[r]) {
8      leftMax = Math.max(leftMax, height[l]);
9      water += leftMax - height[l]; // left side guaranteed safe
10      l++;
11    } else {
12      rightMax = Math.max(rightMax, height[r]);
13      water += rightMax - height[r]; // right side guaranteed safe
14      r--;
15    }
16  }
17  return water;
18}

pointers

L=0

R=11

running max

leftMax=0

rightMax=0

water

total=0

left pointer (L)right pointer (R)processed / merged

slowfast

TYPESCRIPT The solution, annotated

trap.ts
function trap(height: number[]): number {
  let l = 0, r = height.length - 1;
  let leftMax = 0, rightMax = 0;
  let water = 0;

  while (l < r) {
    if (height[l] <= height[r]) {
      leftMax = Math.max(leftMax, height[l]);
      water += leftMax - height[l]; // left side guaranteed safe
      l++;
    } else {
      rightMax = Math.max(rightMax, height[r]);
      water += rightMax - height[r]; // right side guaranteed safe
      r--;
    }
  }
  return water;
}

Reading it block by block

Lines 2–4 — initialise two pointers and running maxima. l starts at the left edge, r at the right. leftMax and rightMax track the tallest bar seen so far from each side as the pointers squeeze inward. water accumulates the answer.

Lines 6–8 — choose the shorter side. If height[l] <= height[r], the left boundary is the bottleneck. We know the right wall is at least as tall as height[r], and since height[r] >= height[l], the right wall is at least leftMax. So the water at l is exactly leftMax − height[l].

Lines 9–10 — update leftMax and add water. We first extend leftMax — if height[l] is a new peak, the difference is 0 (no water, just a taller wall). Otherwise we add the trapped units and advance l.

Lines 12–14 — mirror logic for the right side. Symmetric: when the right bar is strictly shorter, process r with rightMax and step r inward.

Line 17 — return. When l == r the loop ends; every column has been accounted for. The single variable water holds the total — no auxiliary array needed.

Complexity → O(n) time — each index is visited exactly once by either l or r. O(1) space — only four scalar variables beyond the input.

INTERVIEWFollow-ups they'll ask

"Can you reconstruct which cells hold water, not just the total?" Build a parallel waterAt[i] array during the same pass (or use the precomputed-max approach for clarity).
"What if heights can be negative?"The formula still works mathematically (water > 0 only where both sides exceed the current height), but the physical interpretation breaks — clarify the constraint.
"How does this relate to Container With Most Water (LC 11)?" Both use inward-squeezing two pointers. LC 11 maximises min(l,r) * width; LC 42 accumulates min(leftMax,rightMax) − height[i] per column.
"What's the brute force?" For each index, scan left and right to find the true max — O(n²) time, O(1) space. The precomputed-max approach brings it to O(n) / O(n). Two pointers reaches O(n) / O(1).
"What if it's a 2D elevation map?"That's LC 407 (Trapping Rain Water II) — use a min-heap (priority queue) that processes boundary cells outward, same height-limiting logic but in 2D.

OPTIMAL Two Pointers

trap.ts
function trap(height: number[]): number {
  let l = 0, r = height.length - 1;
  let leftMax = 0, rightMax = 0;
  let water = 0;

  while (l < r) {
    if (height[l] <= height[r]) {
      leftMax = Math.max(leftMax, height[l]);
      water += leftMax - height[l]; // left side guaranteed safe
      l++;
    } else {
      rightMax = Math.max(rightMax, height[r]);
      water += rightMax - height[r]; // right side guaranteed safe
      r--;
    }
  }
  return water;
}

Complexity → O(n) time — each index is visited exactly once by either l or r. O(1) space — only four scalar variables beyond the input.

ALT 1 Prefix-max / suffix-max arrays

O(n) time · O(n) space

The clearest way to show your work: precompute both walls explicitly, then read off min(leftMax, rightMax) − height[i] per column.

approach-2.ts
function trap(height: number[]): number {
  const n = height.length;
  if (n === 0) return 0;

  const leftMax: number[] = new Array(n);
  const rightMax: number[] = new Array(n);

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

  rightMax[n - 1] = height[n - 1];
  for (let i = n - 2; i >= 0; i--) {
    rightMax[i] = Math.max(rightMax[i + 1], height[i]);
  }

  let water = 0;
  for (let i = 0; i < n; i++) {
    water += Math.min(leftMax[i], rightMax[i]) - height[i];
  }
  return water;
}

Note → Two extra O(n) arrays are the price of clarity. The two-pointer version collapses both into running scalars for O(1) space — reach for this one when you want the formula to be self-evident.

ALT 2 Monotonic decreasing stack

O(n) time · O(n) space

Fills water in horizontal layers: each time a taller bar appears, pop the dip it spans and add a flat slab of water on top.

approach-3.ts
function trap(height: number[]): number {
  const stack: number[] = []; // indices of bars, heights decreasing
  let water = 0;

  for (let i = 0; i < height.length; i++) {
    // While the current bar is taller than the bar at the stack top,
    // it forms the right wall of a trapped horizontal layer.
    while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
      const bottom = stack.pop()!; // floor of the basin
      if (stack.length === 0) break; // no left wall, water spills out

      const left = stack[stack.length - 1];
      const width = i - left - 1;
      const boundedHeight = Math.min(height[i], height[left]) - height[bottom];
      water += width * boundedHeight;
    }
    stack.push(i);
  }
  return water;
}

Note → Correct but harder to narrate live — the layered, "pop until the wall is shorter than the incoming bar" logic is easy to get subtly wrong under pressure. It is LeetCode's official editorial approach and pairs naturally with histogram problems.

ALT 3 Brute force (scan both sides)

O(n²) time · O(1) space

The literal definition: for every column, walk left and right to find its two walls. Good as a correctness baseline before you optimise.

approach-4.ts
function trap(height: number[]): number {
  const n = height.length;
  let water = 0;

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

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

    water += Math.min(leftMax, rightMax) - height[i];
  }
  return water;
}

Note → The inner scans include index i itself, so min(leftMax, rightMax) >= height[i]and the per-column contribution is never negative. Quadratic time makes this impractical for large inputs — state it, then improve it.

MNEMONIC The one-liner

"Squeeze from both ends — the shorter wall tells you how much water its side holds; update the max, add the gap, step in."

TRIGGERS When you see _ → reach for _

"trapped water" or "elevation map"	two pointers with leftMax/rightMax
process the side with the shorter current bar	advance the shorter pointer
need min of two running maxima without precomputing both arrays	inward two-pointer squeeze
"Container With Most Water" variant	same inward-squeeze frame

SKELETON The reusable shape

skeleton.ts
let l = 0, r = height.length - 1;
let leftMax = 0, rightMax = 0, water = 0;

while (l < r) {
  if (height[l] <= height[r]) {
    leftMax = Math.max(leftMax, height[l]);
    water += leftMax - height[l];
    l++;
  } else {
    rightMax = Math.max(rightMax, height[r]);
    water += rightMax - height[r];
    r--;
  }
}
return water;

FLASHCARDS Tap to flip

How much water sits above bar i?

min(leftMax[i], rightMax[i]) − height[i] — capped by the shorter wall.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What is the time and space complexity of the two-pointer solution to Trapping Rain Water?

QUESTION 02

For height = [0,1,0,2,1,0,1,3,2,1,2,1], what is the total trapped water?

QUESTION 03

Why do we process the side with the shorter current bar?

QUESTION 04

What value does leftMax − height[l] equal when height[l] is a new peak?

QUESTION 05

Which approach also solves Trapping Rain Water but uses O(n) extra space?

QUESTION 06

If height[l] == height[r], which pointer should move?

QUESTION 07

What's the relationship between Trapping Rain Water (LC 42) and Container With Most Water (LC 11)?

QUESTION 08

#42 · Trapping Rain WaterAt each bar, trapped water equals min(leftMax, rightMax) − height. Two pointers maintain running maxima and always process the shorter side first, giving O(n) time and O(1) space.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Water level = min(leftMax, rightMax) − height[i]

RECIPE Advance the shorter pointer, accumulate water

COST Complexity & alternatives

RUN IT Advance the shorter wall, trap water on that side

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Two Pointers

ALT 1 Prefix-max / suffix-max arrays

ALT 2 Monotonic decreasing stack

ALT 3 Brute force (scan both sides)

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _