Skip to main content

42. Trapping Rain Water

hardAsked at Hugging Face

Calculate total water trapped between elevation bars. Hugging Face uses this to test multi-approach fluency — brute force, prefix-max arrays, and two-pointer — the same progression used when optimizing a naive inference pass to a streaming one-shot scan for ML feature extraction pipelines.

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

Source citations

Public interview reports confirming this problem appears in Hugging Face loops.

  • Glassdoor (2026-Q1)— Cited in Hugging Face onsite reports as a hard two-pointer problem testing multi-approach reasoning.
  • Blind (2025-10)— Hugging Face threads identify Trapping Rain Water as a hard problem used in senior engineering rounds.

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: Water fills the valleys between the walls.

Approaches

1. Prefix max arrays

Precompute leftMax[i] = max height to the left of i, rightMax[i] = max height to the right of i. Water at i = max(0, min(leftMax[i], rightMax[i]) - height[i]).

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

Tradeoff: O(n) time, O(n) space. Clear and easy to verify. Use this to establish correctness before optimizing to O(1) space.

2. Two pointers (O(1) space)

Move left and right pointers inward. At each step, process the side with the smaller max height. Water at that position = max(0, localMax - height[pointer]).

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 optimal answer. The key insight: if height[left] <= height[right], the water at left is determined solely by leftMax (we know there's a wall >= leftMax on the right). Process the smaller side first.

Hugging Face-specific tips

Hugging Face values the ability to walk through multiple approaches and articulate why each is an improvement. Structure your answer: (1) brute force O(n²), (2) prefix arrays O(n) time + space, (3) two-pointer O(n) time + O(1) space. Explain the key invariant of the two-pointer approach: 'When height[left] <= height[right], the right wall is guaranteed to be at least as tall as leftMax, so the water at left is fully determined by leftMax alone.' This level of invariant reasoning is exactly what Hugging Face looks for in senior infrastructure engineers.

Common mistakes

  • Processing a position's water based on its local neighbors instead of the global left/right max.
  • In the two-pointer approach, not updating leftMax/rightMax correctly — update before computing water.
  • Using min(height[left], height[right]) instead of min(leftMax, rightMax) — water level is determined by the surrounding walls, not adjacent bars.
  • Forgetting Math.max(0, ...) — bars taller than the surrounding walls have 0 trapped water, not negative.

Follow-up questions

An interviewer at Hugging Face may pivot to one of these next:

  • Trapping Rain Water II (LC 407) — 3D version; use a min-heap for boundary processing.
  • Container With Most Water (LC 11) — two pointers for maximum area between two walls.
  • How would you compute trapped water in a streaming fashion as elevation values arrive one by one?

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 does the two-pointer approach process the smaller height side first?

If height[left] <= height[right], the right boundary is guaranteed to be >= leftMax (since we started from the rightmost max). So leftMax is the binding constraint for the water at position left.

Can I use a stack to solve this?

Yes — maintain a monotonic stack of indices. When a taller bar is encountered, pop and compute the water in the valley between the current bar and the new stack top. O(n) time, O(n) space.

What is the invariant of the prefix-max approach?

leftMax[i] = max(height[0..i]); rightMax[i] = max(height[i..n-1]). Water at i = max(0, min(leftMax[i], rightMax[i]) - height[i]) — the fill level is the shorter surrounding wall minus the bar's own height.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →