Skip to main content

42. Trapping Rain Water

hardAsked at DoorDash

Given an elevation map, compute how much rainwater would be trapped. DoorDash uses this as a hard-end array problem — they want the two-pointer O(1) space optimization, not just the precomputed-max arrays version.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in DoorDash loops.

  • Glassdoor (2026-Q1)— DoorDash SWE onsite reports cite Trapping Rain Water as a recurring hard array question.
  • Blind (2025-12)— DoorDash new-grad reports list this for the two-pointer optimization probe.

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,2,1,2,1]
Output
6

Explanation: In this case, 6 units of rain water are being trapped.

Example 2

Input
height = [4,2,0,3,2,5]
Output
9

Approaches

1. Precomputed max-left + max-right

For each index i, water = min(maxLeft[i], maxRight[i]) - height[i]. Precompute both arrays.

Time
O(n)
Space
O(n)
function trapPrecomputed(height) {
  const n = height.length;
  if (n === 0) return 0;
  const maxLeft = new Array(n);
  const maxRight = new Array(n);
  maxLeft[0] = height[0];
  for (let i = 1; i < n; i++) maxLeft[i] = Math.max(maxLeft[i - 1], height[i]);
  maxRight[n - 1] = height[n - 1];
  for (let i = n - 2; i >= 0; i--) maxRight[i] = Math.max(maxRight[i + 1], height[i]);
  let total = 0;
  for (let i = 0; i < n; i++) total += Math.min(maxLeft[i], maxRight[i]) - height[i];
  return total;
}

Tradeoff: Easy to derive on the board. O(n) time but uses O(n) extra. Bloomberg interviewers want this as the stepping-stone to the optimal.

2. Two-pointer (optimal O(1) space)

Move from both ends. The side with the smaller max-so-far is the bound for that side's water.

Time
O(n)
Space
O(1)
function trap(height) {
  let l = 0, r = height.length - 1;
  let leftMax = 0, rightMax = 0;
  let total = 0;
  while (l < r) {
    if (height[l] < height[r]) {
      if (height[l] >= leftMax) leftMax = height[l];
      else total += leftMax - height[l];
      l++;
    } else {
      if (height[r] >= rightMax) rightMax = height[r];
      else total += rightMax - height[r];
      r--;
    }
  }
  return total;
}

Tradeoff: DoorDash's preferred answer. The insight: water at i is bounded by min(maxLeft, maxRight). Whichever side has the smaller max can be processed without knowing the other side's exact max.

DoorDash-specific tips

DoorDash interviewers specifically grade on whether you derive the TWO-POINTER. Lead with the precomputed-arrays version, then say 'I can drop space to O(1) — if height[l] < height[r], leftMax is the binding constraint on the left.' That insight is the signal.

Common mistakes

  • Forgetting that water at i requires BOTH a left and right wall taller than height[i].
  • Using current-position max instead of max-so-far from the moving side.
  • Off-by-one on the < vs <= choice in the pointer compare.

Follow-up questions

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

  • Container With Most Water (LC 11) — similar two-pointer, different objective.
  • Trapping Rain Water II (LC 407) — 2D version with min-heap.
  • Largest Rectangle in Histogram (LC 84) — stack-based, different shape.

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 work?

If height[l] < height[r], the right side has at least one bar >= height[l] (namely height[r]). So leftMax is the binding constraint at l. We can safely process l without knowing rightMax exactly.

Is the stack-based monotonic version useful?

Yes for breadth, but two-pointer is the canonical answer. Mention stacks if probed.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →