Skip to main content

42. Trapping Rain Water

hardAsked at Linear

Calculate the total water trapped between elevation bars. Linear asks this to see whether you progress through the intuitions — brute force → precomputed max arrays → two pointers — and can articulate why the two-pointer approach is O(1) space.

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

Source citations

Public interview reports confirming this problem appears in Linear loops.

  • Glassdoor (2026-Q1)— Cited in Linear SWE onsite reports as a hard two-pointer / prefix problem.
  • Blind (2025-11)— Multiple Linear interview threads list Trapping Rain Water as a stretch hard problem.

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

Example 2

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

Approaches

1. Brute force per column

For each position, find the max height to its left and right. Water at position i = min(maxLeft, maxRight) - height[i].

Time
O(n^2)
Space
O(1)
function trap(height) {
  let total = 0;
  for (let i = 1; i < height.length - 1; i++) {
    let maxL = 0, maxR = 0;
    for (let j = 0; j <= i; j++) maxL = Math.max(maxL, height[j]);
    for (let j = i; j < height.length; j++) maxR = Math.max(maxR, height[j]);
    total += Math.min(maxL, maxR) - height[i];
  }
  return total;
}

Tradeoff: O(n^2) due to the inner max-finding loops. Correct, but immediately note that both max scans can be precomputed.

2. Precomputed left/right max arrays

Precompute maxLeft[i] and maxRight[i] in two passes. Then compute water in a third pass.

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

Tradeoff: O(n) time, O(n) space. Three clean passes. Most Linear interviewers accept this as the primary solution.

3. Two pointers (optimal)

Maintain left and right pointers and running max heights. Advance the side with the smaller max — that side's water is determined solely by its own max.

Time
O(n)
Space
O(1)
function trap(height) {
  let left = 0, right = height.length - 1;
  let maxL = 0, maxR = 0;
  let total = 0;
  while (left < right) {
    if (height[left] < height[right]) {
      if (height[left] >= maxL) maxL = height[left];
      else total += maxL - height[left];
      left++;
    } else {
      if (height[right] >= maxR) maxR = height[right];
      else total += maxR - height[right];
      right--;
    }
  }
  return total;
}

Tradeoff: O(n) time, O(1) space. Key insight: if maxL < maxR, the water at the left position is guaranteed to be min(maxL, maxR) - height[left] = maxL - height[left], regardless of anything to the right. Advance the smaller-max side.

Linear-specific tips

Show the full progression to Linear interviewers: brute force (name it, don't code it), precomputed arrays (code this), then two pointers (explain and code). The two-pointer insight — 'I can process the side with the smaller max because its water is already determined' — is what distinguishes strong candidates. Narrate this before writing the two-pointer code.

Common mistakes

  • Skipping the precomputed-arrays solution and jumping straight to two pointers without explaining the intuition — interviewers can't follow the leap.
  • Not handling the case where height[i] is greater than the current running max — update the max, add zero water (the bar is a wall, not a bucket).
  • Using maxL[i-1] instead of maxL[i] in the precomputed pass — should include the current cell.

Follow-up questions

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

  • Container With Most Water (LC 11) — two-pointer approach but simpler (no filling logic).
  • What if the elevation map is 2D (a grid)?
  • How would you solve this if bars had varying widths?

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 advance the side with the smaller max?

If maxL < maxR, then regardless of what's between the right pointer and the left, the water at the left position is capped at maxL. Advancing left is safe because the limiting wall is already determined.

What does water[i] = min(maxL, maxR) - height[i] mean?

The water level above position i is the minimum of the tallest walls on either side. Subtract the bar's own height to get the depth of water on top of it.

Can water be negative?

No — if height[i] >= min(maxL, maxR), the formula gives 0 or negative, so the position holds no water. The precomputed approach naturally produces 0 or positive values for each position.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →