42. Trapping Rain Water

Q: Why does the two-pointer approach work without knowing the exact right boundary?

When height[lo] = height[lo] is sufficient. We don't need to know exactly how tall the right wall is.

hardAsked at Citadel

Trapping Rain Water is a high-signal hard problem at Citadel — it has three fundamentally different O(n) solutions (prefix/suffix max arrays, two-pointer, monotonic stack), and the interviewer will ask for all of them. It also tests mathematical reasoning: the water at position i is determined by min(leftMax, rightMax) − height[i].

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-22

Source citations

Public interview reports confirming this problem appears in Citadel loops.

Glassdoor (2026-Q1)— Citadel SWE hard-round candidates list Trapping Rain Water as a top-3 most common hard problem, with all three approaches expected.
Blind (2025-11)— Citadel SWE threads specifically note interviewers ask for the two-pointer approach after the prefix-max approach, then sometimes the monotonic stack.

Problem

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Constraints

n == height.length
1 <= n <= 2 * 10^4
0 <= height[i] <= 10^5

Examples

Example 1

Input

height = [0,1,0,2,1,0,1,3,1,0,1,2]

Output

Explanation: The elevation map traps 6 units of water.

Example 2

Input

height = [4,2,0,3,2,5]

Output

Explanation: Water fills the valleys — 9 units total.

Approaches

1. Prefix/suffix max arrays

Precompute leftMax[i] and rightMax[i]. Water at position i = max(0, min(leftMax[i], rightMax[i]) - height[i]). Sum over all positions.

Time: O(n)
Space: O(n)

function trap(height) {
  const n = height.length;
  const leftMax = new Array(n);
  const rightMax = 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.max(0, Math.min(leftMax[i], rightMax[i]) - height[i]);
  }
  return water;
}

Tradeoff: O(n) time, O(n) space for two precomputed arrays. The cleanest approach for understanding — state the formula first, then the arrays fall out naturally.

2. Two pointers (O(1) space)

Two pointers from both ends. At each step, process the side with the smaller max-height. The water at that position is determined by the shorter wall — the other side guarantees at least that much height.

Time: O(n)
Space: O(1)

function trap(height) {
  let lo = 0, hi = height.length - 1;
  let leftMax = 0, rightMax = 0;
  let water = 0;
  while (lo < hi) {
    if (height[lo] <= height[hi]) {
      // Left side is shorter — water level bounded by leftMax
      if (height[lo] >= leftMax) leftMax = height[lo];
      else water += leftMax - height[lo];
      lo++;
    } else {
      // Right side is shorter — water level bounded by rightMax
      if (height[hi] >= rightMax) rightMax = height[hi];
      else water += rightMax - height[hi];
      hi--;
    }
  }
  return water;
}

Tradeoff: O(n) time, O(1) space. The key insight: if height[lo] <= height[hi], the right wall is at least as tall, so the water at lo is determined solely by leftMax. No need to know the exact right boundary. This is the optimal answer Citadel expects.

3. Monotonic stack

Use a decreasing stack. When a taller bar is encountered, pop bars shorter than the current bar and compute the trapped water in the horizontal layer between them.

Time: O(n)
Space: O(n)

function trap(height) {
  const stack = []; // indices of bars in decreasing height order
  let water = 0;
  for (let i = 0; i < height.length; i++) {
    while (stack.length && height[i] > height[stack[stack.length - 1]]) {
      const bottom = stack.pop();
      if (!stack.length) break;
      const left = stack[stack.length - 1];
      const width = i - left - 1;
      const boundedHeight = Math.min(height[left], height[i]) - height[bottom];
      water += width * boundedHeight;
    }
    stack.push(i);
  }
  return water;
}

Tradeoff: O(n) time, O(n) stack. Computes water layer-by-layer horizontally instead of column-by-column vertically. More complex to reason about but generalizes to Largest Rectangle in Histogram (LC 84). Citadel may ask for it as a third approach.

Citadel-specific tips

Present all three approaches in order: (1) prefix/suffix — O(n) space, clearest intuition. (2) Two-pointer — O(1) space, optimal. (3) Monotonic stack — different framing, links to LC 84. State the core formula first: 'water[i] = max(0, min(maxHeightLeft, maxHeightRight) − height[i]).' Citadel will ask: 'At what point in a trading system would you see this pattern?' — answer: computing the maximum drawdown recovery window, or finding the minimum liquidity between two high-volume periods.

Common mistakes

Using Math.max instead of Math.min in the water formula — water level is bounded by the shorter wall, not the taller one.
In the two-pointer approach, processing both sides in the same iteration — only advance the shorter side; advancing both is incorrect.
In the monotonic stack, breaking out of the while loop when the stack is empty — the remaining unmatched bar has no left boundary and contributes zero water.
Forgetting Math.max(0, ...) wrapper — when leftMax[i] = rightMax[i] = height[i], the subtraction is 0, but negative values shouldn't be added.

Follow-up questions

An interviewer at Citadel may pivot to one of these next:

Trapping Rain Water II (LC 407) — 3D grid version; requires a min-heap (Dijkstra-like).
Largest Rectangle in Histogram (LC 84) — monotonic stack applied to area instead of water.
How would you compute this on a streaming elevation map as bars arrive left-to-right?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does the two-pointer approach work without knowing the exact right boundary?

When height[lo] <= height[hi], the right side is at least as tall as the left. The water at lo is bounded by leftMax — any right wall of height >= height[lo] is sufficient. We don't need to know exactly how tall the right wall is.

When does the monotonic stack give more information than the two-pointer approach?

The stack computes water per trapped 'pool' (horizontal layer), while two-pointer computes per column. The stack approach naturally outputs the set of distinct trapped pools — useful if you need to enumerate traps, not just the total.

What is the water at the first and last bar?

Always 0 — the first bar has no left wall and the last has no right wall. The loop bounds in all three approaches implicitly handle this.

Practice these live with InterviewChamp.AI

Drill Trapping Rain Water and other Citadel interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →