Skip to main content

24. Trapping Rain Water

hardAsked at Figma

Compute how much water is trapped between bars of varying height. Figma poses this as a stress-test of two-pointer thinking and disciplined invariant tracking.

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

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. The water at each index is bounded by the minimum of the maximum heights to its left and right.

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 arrays

Precompute the max height seen to the left and right of every index, then sum min(leftMax, rightMax) - height[i].

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

Tradeoff:

2. Two pointers with running maxes

Move whichever pointer has the smaller running-max inward; the smaller max guarantees a known water level at that index. Single pass, constant space.

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

Tradeoff:

Figma-specific tips

Figma's senior bar wants the invariant said aloud: 'the side with the smaller running max bounds the water at that index' — that single sentence is the whole interview signal.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →