Skip to main content

99. Trapping Rain Water

hardAsked at Vercel

Compute how much rain water can be trapped after raining on an elevation map. Vercel asks this for the two-pointer 'water = min(maxLeft, maxRight) - height' insight — same shape as their bandwidth utilization calculation across uneven edge capacities.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel platform onsite; two-pointer expected.
  • Blind (2026-Q1)— Listed as a Vercel signature hard.

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. Precompute leftMax and rightMax arrays

leftMax[i] = max height in [0..i]; rightMax[i] = max in [i..n). Water at i = min(left, right) - height[i].

Time
O(n)
Space
O(n)
function trap(height) {
  const n = height.length;
  const leftMax = new Array(n), 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. The two-pointer version is O(1) space.

2. Two-pointer (optimal)

Pointers at both ends. Move whichever side is lower. Maintain leftMax and rightMax as scalars. Water at the moved pointer = leftMax/rightMax - height.

Time
O(n)
Space
O(1)
function trap(height) {
  let l = 0, r = height.length - 1;
  let leftMax = 0, rightMax = 0;
  let 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: O(1) space. The two-pointer 'move the lower side' invariant works because the water level at a position is bounded by the SHORTER of the two max-walls. The taller side guarantees its bound; the shorter is the question mark we resolve by moving inward.

Vercel-specific tips

Vercel grades the two-pointer technique and the invariant articulation. Bonus signal: explaining WHY moving the lower side is safe — the water at position i is min(leftMax, rightMax) - height[i], and the side we DON'T move has a confirmed max bound. The shorter side's max is the limiting factor.

Common mistakes

  • Looking only at the immediate neighbor — water depends on the GLOBAL max on each side.
  • Computing per-column max without the running variable — extra space.
  • Confusing which pointer to move — always the lower side.

Follow-up questions

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

  • Trapping Rain Water II (LC 407) — 2D grid, priority queue.
  • Largest Rectangle in Histogram (LC 84) — different problem, same vibe.
  • Stack-based approach to LC 42.

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

Water at position i is bounded by min(leftMax, rightMax) - height[i]. If height[l] < height[r], then rightMax >= height[r] > height[l] >= some threshold — the binding constraint is leftMax, which we know. Safe to compute water at l and move.

Why is the two-pointer O(1) version equivalent?

The leftMax/rightMax scalars track the max seen so far from each side. Each iteration moves one pointer and updates one scalar. Provably correct because we always move the side whose max is the binding constraint.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →