Skip to main content

42. Trapping Rain Water

hardAsked at Amazon

Given heights, compute water trapped after rain. Amazon asks this to test whether you reach for the two-pointer invariant 'water at i = min(maxLeft, maxRight) - height[i]' and can articulate why two-pointer beats prefix-max arrays on space.

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

Source citations

Public interview reports confirming this problem appears in Amazon loops.

  • Glassdoor (2026-Q1)— Amazon SDE II/III onsite reports cite this as a recurring two-pointer hard.
  • Blind (2025-10)— Recurring Amazon interview 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. Prefix max + suffix max

Precompute maxLeft[i] and maxRight[i]. Sum min(maxLeft[i], maxRight[i]) - height[i].

Time
O(n)
Space
O(n)
function trapDP(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: Linear time at O(n) extra space. Most candidates reach this; the two-pointer is the senior IC signal.

2. Two-pointer (optimal)

Track maxLeft and maxRight as two pointers walk inward. The smaller side 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], maxLeft constrains the water at l — we don't need exact maxRight, just that it's at least height[l].

Amazon-specific tips

Amazon interviewers want the two-pointer invariant articulated. State out loud: 'At each step, the smaller side fully constrains that index\'s water. So I advance the smaller side, updating its running max.' Skipping this articulation costs the senior-IC signal even when the code is right.

Common mistakes

  • Treating it as 'subtract global max from sum' — wrong, water depends on local min of maxes.
  • Forgetting water[i] = min(maxLeft, maxRight) - height[i].
  • Off-by-one in two-pointer termination (l < r is correct; l <= r would double-count the middle).

Follow-up questions

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

  • Trapping Rain Water II (LC 407) — 2D grid version.
  • Could you solve it with a monotonic stack?
  • What if water evaporated over time?

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 two-pointer over prefix-max?

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

What's the intuition for two-pointer correctness?

If height[l] < height[r], we know maxRight >= height[l] (the right pointer's bar is at least that tall). So water at l depends only on maxLeft.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →