Skip to main content

42. Trapping Rain Water

hardAsked at Gusto

Calculate how much rain water can be trapped between elevation bars. Gusto uses this as a harder two-pointer showcase — they want the O(1)-space two-pointer solution and to hear the invariant explained: 'water level at any position is determined by the shorter of the two tallest walls seen so far from each side.'

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

Source citations

Public interview reports confirming this problem appears in Gusto loops.

  • Glassdoor (2026-Q1)— Reported in Gusto senior SWE onsite reports as a hard two-pointer or DP problem with an emphasis on the O(1) space solution.
  • Blind (2025-12)— Gusto threads cite Trapping Rain Water as a recurring hard that tests both prefix/suffix DP and two-pointer reasoning.

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: Six units of water are trapped in the valleys.

Example 2

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

Explanation: 9 units are trapped.

Approaches

1. Prefix/suffix max arrays (O(n) space)

Precompute maxLeft[i] (max height to the left of i) and maxRight[i] (max height to the right of i). Water at i = max(0, min(maxLeft[i], maxRight[i]) − height[i]).

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

Tradeoff: Clear and easy to verify. Three passes. Good starting point to establish correctness before optimising space.

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

Maintain left and right pointers with their running max heights. Move the pointer on the side with the shorter max — the water at that pointer is fully determined by the shorter wall.

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

Tradeoff: O(n) time, O(1) space. Single pass. The invariant: when height[left] ≤ height[right], the water at left is determined by maxLeft (the right wall is guaranteed to be at least as tall). This is the optimal solution Gusto expects.

Gusto-specific tips

Articulate the invariant before coding the two-pointer approach: 'If the left max is smaller than the right max, the water level at the left pointer is fully determined by the left max — the right wall will never be the bottleneck, regardless of what's between left and right.' This is the key insight Gusto wants to hear. Start with the prefix/suffix arrays to demonstrate correctness, then narrate the space optimisation.

Common mistakes

  • Computing water as min(height[left], height[right]) - height[i] using raw heights instead of running maxes — misses the actual container walls.
  • Moving both pointers simultaneously — only advance the pointer on the shorter-max side.
  • Not initialising maxLeft and maxRight to 0 — they must start at 0 so the first element correctly updates them.
  • Using the two-pointer approach but doubting the invariant mid-solve — commit to the logic and verify with the example.

Follow-up questions

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

  • Container With Most Water (LC 11) — similar two-pointer but simpler (no bars between walls).
  • Trapping Rain Water II (LC 407) — 3D variant requiring a min-heap BFS.
  • How would you compute the maximum width of trapped water rather than the volume?

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 do we move the pointer with the smaller max height?

The water level at any position is min(maxLeft, maxRight). If maxLeft ≤ maxRight, then water at the left pointer is maxLeft − height[left]. We know the right side won't be the bottleneck, so we can safely process and advance left.

What if all heights are equal?

No water is trapped — every position's water level equals its height. The algorithm correctly accumulates 0.

Is this the same as Container With Most Water?

Related but different. Container With Most Water asks for the rectangle with maximum area between two bars (ignoring middle bars). Trapping Rain Water fills all the space between bars including intermediate valleys.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →