Skip to main content

42. Trapping Rain Water

hardAsked at Robinhood

Given heights representing an elevation map, compute how much water it can trap after raining. Robinhood asks this as a hard-tier classical problem to see whether you reach for two-pointer over DP-of-max-arrays, and whether you can articulate the invariant cleanly.

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

Source citations

Public interview reports confirming this problem appears in Robinhood loops.

  • Glassdoor (2026-Q1)— Robinhood SWE-II onsite reports include Trapping Rain Water as a recurring hard round.
  • Blind (2025-11)— Robinhood backend trip reports cite this and Largest Rectangle in Histogram as the two-pointer / stack hard pair.

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. Brute-force per index

For each index i, scan left and right for the max heights. Water at i is min(leftMax, rightMax) - height[i].

Time
O(n^2)
Space
O(1)
function trapBrute(height) {
  let total = 0;
  for (let i = 0; i < height.length; i++) {
    let leftMax = 0, rightMax = 0;
    for (let l = 0; l <= i; l++) leftMax = Math.max(leftMax, height[l]);
    for (let r = i; r < height.length; r++) rightMax = Math.max(rightMax, height[r]);
    total += Math.min(leftMax, rightMax) - height[i];
  }
  return total;
}

Tradeoff: Quadratic. The natural starting point — name it, then move to precomputed-max arrays.

2. DP — prefix/suffix max arrays

Precompute leftMax[i] and rightMax[i]. Then sum min(leftMax[i], rightMax[i]) - height[i].

Time
O(n)
Space
O(n)
function trapDP(height) {
  const n = height.length;
  if (!n) return 0;
  const leftMax = new Array(n);
  const rightMax = new Array(n);
  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 total = 0;
  for (let i = 0; i < n; i++) total += Math.min(leftMax[i], rightMax[i]) - height[i];
  return total;
}

Tradeoff: O(n) time and space. Easy to argue correctness. Strong intermediate answer before two-pointer.

3. Two-pointer (optimal)

Walk left and right pointers inward. Track leftMax and rightMax. The lower side determines the water level at that pointer.

Time
O(n)
Space
O(1)
function trap(height) {
  let left = 0, right = height.length - 1;
  let leftMax = 0, rightMax = 0;
  let 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: O(n) time, O(1) space. The optimal. Invariant: 'the lower side's max is bounded by the higher side, so we can safely compute its water without knowing the other side's exact future max.'

Robinhood-specific tips

Robinhood interviewers want all three approaches walked through verbally. Lead with brute-force, name 'this recomputes max scans — I'll memoize into prefix/suffix arrays.' Then say 'I can collapse the two arrays into two pointers because the lower side determines the water at that index, regardless of the higher side's exact future.' Be ready for the 2D variant follow-up (LC 407).

Common mistakes

  • Computing height[i] - min(leftMax, rightMax) — wrong direction; should be min(maxes) - height[i].
  • In two-pointer, comparing leftMax and rightMax instead of height[left] and height[right] — wrong invariant.
  • Off-by-one on the boundary — water above bar 0 or bar n-1 is always 0 because there's no wall on the outside.

Follow-up questions

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

  • Trapping Rain Water II (LC 407) — 2D grid; BFS from boundary + min-heap.
  • Largest Rectangle in Histogram (LC 84) — same elevation-map shape, different question; stack of indices.
  • Container With Most Water (LC 11) — pick two bars; greedy two-pointer.

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?

At any step, the lower side's water level is bounded by min(leftMax, rightMax). Since the lower side's running max is also <= the other side's running max (because the other side has at least one bar of higher height), we can safely fill water on the lower side using only its own running max.

Should I default to DP or two-pointer?

Code both if asked. Start with DP — it's easier to argue correctness. Two-pointer is the optimal answer; walk through the invariant carefully.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →