Skip to main content

42. Trapping Rain Water

hardAsked at AMD

Calculate how much water can be trapped between elevation bars. AMD uses this to test two-pointer reasoning under asymmetric constraints — the same left/right boundary propagation appears in memory range overlap analysis, voltage droop modeling, and signal amplitude clipping detection in hardware bring-up tooling.

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

Source citations

Public interview reports confirming this problem appears in AMD loops.

  • Glassdoor (2026-Q1)— AMD SWE candidates report Trapping Rain Water appearing in hard coding rounds, valued for its two-pointer space optimization.
  • Blind (2025-11)— AMD interview threads flag this as a hard problem that AMD uses specifically to test two-pointer depth and space-complexity awareness.

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: The elevation map traps 6 units of water.

Example 2

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

Explanation: 9 units trapped between the bars.

Approaches

1. Precompute left-max and right-max arrays

For each index, water trapped = min(maxLeft[i], maxRight[i]) - height[i]. Precompute both max arrays in two linear passes, then compute the total.

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: O(n) time, O(n) space. Clear and easy to reason about. The three-pass structure makes it easy to verify correctness.

2. Two Pointers (O(1) space)

Maintain left and right pointers and running left/right maximums. The side with the smaller max can be computed confidently — water at that position is maxSide - height[side]. Advance the pointer with the smaller max.

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

Tradeoff: O(1) space — the best approach. The key insight: if leftMax < rightMax, the water at the left pointer is bounded by leftMax regardless of what's between left and right (because we know there's something >= leftMax on the right). AMD expects this version.

AMD-specific tips

AMD values the O(1) space two-pointer version specifically because it demonstrates the ability to reason under asymmetric information: 'I know the right side is at least rightMax — so whatever is between left and right doesn't matter for the left pointer's water calculation.' This type of argument appears in hardware boundary analysis: if you know one side of a voltage rail can sustain a certain level, you can compute droops on the other side without full system knowledge. State the invariant before coding it.

Common mistakes

  • Confusing which pointer to advance — advance the one with the smaller max (not height), because that side's water is deterministic.
  • Using height[left] < height[right] for the condition instead of <= — either works for correctness, but be consistent.
  • Not initializing leftMax and rightMax to 0 — they track the maximum height seen so far from each side.
  • Computing water as max-height without checking that max > height — negative water is nonsensical; use Math.max(0, level - height[i]) or an explicit if.

Follow-up questions

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

  • Container With Most Water (LC 11) — two-pointer to maximize the rectangle area, not trapped water.
  • Largest Rectangle in Histogram (LC 84) — extends the boundary-sweep technique.
  • How would you model voltage droop across a power delivery network using this pattern?

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 can we advance the smaller-max pointer safely?

If leftMax <= rightMax, then the water at left is capped by leftMax — even if the right side has a very high bar somewhere, leftMax is the binding constraint. We don't need to know what's in between. The right side guarantees at least rightMax >= leftMax, so water won't spill right.

What if all heights are equal?

No water is trapped — every position's water level equals its height, resulting in 0 contribution. The algorithm handles this: leftMax == height[left] so no water is added, and left increments.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →