Skip to main content

42. Trapping Rain Water

hardAsked at Google

Given heights, compute how much water trapped between bars after rain. Google asks this to see whether you reach for the two-pointer invariant (water at i depends only on min(maxLeft, maxRight)) without falling into the O(n^2) trap of recomputing maxes per index.

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

Source citations

Public interview reports confirming this problem appears in Google loops.

  • Glassdoor (2026-Q1)— Frequent in Google L4/L5 onsite reports as the algorithmic-thinking round.
  • Blind (2025-09)— Recurring in Google staff-IC interview reports.

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 between the bars.

Example 2

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

Approaches

1. Brute-force per index

For each index i, scan left and right to find maxLeft and maxRight; add min(maxLeft, maxRight) - height[i].

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

Tradeoff: Captures the right invariant (water at i = min(maxLeft, maxRight) - height[i]) but recomputes maxes from scratch each iteration.

2. Prefix max + suffix max arrays

Precompute maxLeft[i] and maxRight[i] in two linear scans, then sum min(left, right) - height[i] across i.

Time
O(n)
Space
O(n)
function trapDP(height) {
  const n = height.length;
  if (n === 0) return 0;
  const maxLeft = new Array(n).fill(0);
  const maxRight = new Array(n).fill(0);
  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: Linear time at O(n) extra space — a clear improvement over brute-force and the version most candidates reach. Mention this before going to two-pointer.

3. Two-pointer (optimal)

Track maxLeft and maxRight while two pointers walk inward. Whichever side has the smaller max defines that index's water.

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

Tradeoff: O(1) extra space. The key insight: if height[l] < height[r], then maxLeft fully constrains what water can rest at l — we don't need to know the exact maxRight, only that some bar to the right is at least height[l].

Google-specific tips

Google interviewers want the two-pointer invariant articulated before the code. Say: 'At each step, the smaller side limits the water height — so we can safely advance that pointer.' If you jump to code without that, you'll get correctness but lose the communication score. Always start with brute-force, then prefix-max, then two-pointer.

Common mistakes

  • Treating the problem as 'find the global max and subtract' — wrong, water depends on the local min of maxes, not the global max.
  • Forgetting that water[i] = min(maxLeft, maxRight) - height[i], not just maxLeft - height[i].
  • Off-by-one errors in the two-pointer version, especially around the termination condition l < r vs l <= r.

Follow-up questions

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

  • What if it's a 2D grid (Trapping Rain Water II)?
  • Could you do it with a monotonic stack? (Yes — different framing, same O(n) complexity.)
  • What if the elevation changed over time (online problem)?

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 is two-pointer better than prefix-max arrays?

Same time complexity but O(1) space instead of O(n). For very large arrays, that's the difference between fitting in cache and not.

What's the intuition for why two-pointer works?

If height[l] < height[r], we know there's at least one bar of height ≥ height[l] somewhere on the right (specifically at r). So the water at l can be safely computed using only maxLeft — we don't need maxRight's exact value.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →