Skip to main content

95. Trapping Rain Water

hardAsked at Reddit

Compute how much rain water is trapped between elevation bars. Reddit uses this to test two-pointer + min/max tracking — the same shape used to identify dips between vote-volume peaks in their popularity-decay analysis.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit on-site classic hard.
  • Blind (2025-11)— Reported in Reddit infra 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

Example 2

Input
height = [4,2,0,3,2,5]
Output
9

Approaches

1. Per-position max scan

For each index, find max on the left and right. Trapped = min(maxL, maxR) - height.

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

Tradeoff: Quadratic. TLE for large n.

2. Two-pointer with running max (optimal)

Pointers from both ends. Whichever side is lower determines trapped water at that index.

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

Tradeoff: Linear time, O(1) space. The proof: water at index i depends on min(maxL, maxR), and we always advance the side that's bounded by the smaller running max.

Reddit-specific tips

Reddit interviewers want the two-pointer proof. State the invariant: 'water at l is bounded by lMax because we know there's something at least height[r] >= height[l] on the right'. Bonus signal: walk through with a small example before coding.

Common mistakes

  • Updating lMax/rMax after computing trapped water (must come first).
  • Comparing height[l] > height[r] but updating both pointers.
  • Forgetting the strict < in the loop (l < r, not <=).

Follow-up questions

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

  • Trapping Rain Water II (LC 407) — 2D matrix.
  • Container with most water (LC 11).
  • Largest rectangle in histogram (LC 84).

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 lower side determine the water?

Water at i is bounded by min(maxL, maxR). If height[l] < height[r], lMax bounds the trap at l because there's a higher bar on the right.

Could DP work?

Yes — precompute left-max and right-max arrays. O(n) time, O(n) space. Two-pointer wins on memory.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →