Skip to main content

42. Trapping Rain Water

hardAsked at Uber

Given an elevation map of bar heights, compute how much water can be trapped after rain. Uber asks this to test whether you reach for the two-pointer O(1)-space solution after seeing the prefix-max O(n)-space one.

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

Source citations

Public interview reports confirming this problem appears in Uber loops.

  • Glassdoor (2026-Q1)— Uber L4/L5 onsite reports list this as a recurring two-pointer hard.
  • Blind (2025-12)— Recurring in Uber backend interview reports.

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-column

For each column i, water trapped = min(maxLeft, maxRight) - height[i], clamped at 0. Compute maxLeft/maxRight per column with a scan.

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

Tradeoff: Conceptually clear: water at column i is bounded by the tallest bar on each side. Quadratic because we re-scan for every i.

2. Precomputed prefix-max arrays

One left-to-right pass for maxLeft[], one right-to-left for maxRight[]. Sum per-column water in a final pass.

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

Tradeoff: Linear time at O(n) extra space. Always mention this version — it bridges brute-force to the two-pointer optimization.

3. Two pointers (optimal, O(1) space)

Maintain leftMax, rightMax. Advance whichever pointer is at the shorter side; that side is bounded by its own max.

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

Tradeoff: Cleanest answer: linear time, O(1) space. The key insight is that when height[l] < height[r], leftMax bounds the water at l (because somewhere to the right is taller than leftMax).

Uber-specific tips

Uber's bar on this is the two-pointer argument. Say: 'When the left bar is shorter than the right bar, we know there's at least one taller bar somewhere to the right, so leftMax bounds the water at the left position. We can safely move left forward.' Without that argument, the code looks magical and you'll lose signal.

Common mistakes

  • Confusing the per-column formula with the per-rectangle one (a different problem, LC 84).
  • Updating leftMax/rightMax on the wrong side (only update on the side you're advancing).
  • Off-by-one on the loop bound — use l < r, not l <= r.

Follow-up questions

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

  • Trapping Rain Water II (LC 407) — 2D version using a min-heap from the border inward.
  • Container with Most Water (LC 11) — same two-pointer template, different objective.
  • Histogram-style: largest rectangle in a histogram (LC 84) — monotonic stack.

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 argument work?

Invariant: leftMax and rightMax are the tallest bars seen so far on each side. When the current left bar is shorter than the current right bar, there's already a taller bar to the right than leftMax, so leftMax bounds the water at l — we can safely move forward.

What if all bars are the same height?

No water is trapped — every difference is zero. The two-pointer code handles this correctly because both leftMax and rightMax track exactly height[l] and height[r] respectively.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →