Skip to main content

42. Trapping Rain Water

hardAsked at Anduril

Compute how much water can be trapped between elevation bars after a rainfall. Anduril frequently asks this hard problem because it has three distinct approaches at different space tradeoffs — they want to see you enumerate them, pick the O(n)/O(1) two-pointer solution, and explain the invariant rigorously.

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

Source citations

Public interview reports confirming this problem appears in Anduril loops.

  • Glassdoor (2026-Q1)— Cited as a hard problem in Anduril SWE onsite reports, often used for senior engineering evaluation.
  • Blind (2025-12)— Multiple Anduril threads list Trapping Rain Water as a high-frequency hard problem across both generalist and systems-focused roles.

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: Water trapped between the bars totals 9 units.

Approaches

1. Prefix/suffix max arrays

For each index, water trapped = min(maxLeft[i], maxRight[i]) - height[i]. Precompute left and right max arrays in O(n).

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 total = 0;
  for (let i = 0; i < n; i++) {
    const water = Math.min(maxLeft[i], maxRight[i]) - height[i];
    if (water > 0) total += water;
  }
  return total;
}

Tradeoff: O(n) time and O(n) space. Clear and correct. The two extra arrays make the logic easy to verify. Present this first to establish correctness, then optimize.

2. Two pointers (O(1) space)

Use left and right pointers. Advance the side with the smaller max-height. Water at each position is determined by the limiting side's max.

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

Tradeoff: O(n) time, O(1) space. The key invariant: when height[left] < height[right], the bottleneck for position left is maxLeft (the right side is guaranteed to be at least as tall). This eliminates the need to precompute maxRight for the current position.

Anduril-specific tips

Anduril expects you to present all three approaches: O(n^2) brute force, O(n) prefix/suffix arrays, and O(n)/O(1) two pointers. The two-pointer solution's invariant is the hardest to state precisely — practice it: 'When height[left] < height[right], water at left is bounded by maxLeft, not maxRight, because the right side is guaranteed to be at least height[right] which is already taller than maxLeft.' This level of rigor distinguishes Anduril candidates who pass from those who don't.

Common mistakes

  • In the two-pointer approach, confusing which pointer to advance — always advance the side with the smaller current max-height.
  • Subtracting height before checking if water > 0 — negative water (bars taller than their neighbors' max) should contribute 0.
  • In the prefix array approach, off-by-one: maxLeft[i] should be the max of height[0..i-1], not height[0..i].
  • Not handling the single-element or two-element edge cases — both return 0 trivially.

Follow-up questions

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

  • Trapping Rain Water II (LC 407) — 3D version using a min-heap BFS from the boundary.
  • How would you count the volume of water trapped in a grid with arbitrary terrain?
  • Container With Most Water (LC 11) — a simpler related problem with the same two-pointer 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 does the two-pointer invariant work?

When height[left] < height[right], we know there exists some bar to the right of left that is at least height[right] tall. So the water at left is capped by maxLeft, not maxRight — we can safely accumulate without knowing the exact right maximum.

What is the brute-force O(n^2) approach?

For each bar, scan left to find maxLeft and scan right to find maxRight, then compute water. O(n) per bar, O(n^2) total.

Does the stack-based approach also give O(n)?

Yes — a monotonic stack approach also gives O(n) time and O(n) space, but two pointers is cleaner. Mention the stack approach if asked for a third method.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →