Skip to main content

23. Trapping Rain Water

hardAsked at Chegg

Compute total water trapped between histogram bars — a classic two-pointer hard that Chegg uses to assess whether candidates can reduce a prefix/suffix problem to O(1) space.

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

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 prefix/suffix max arrays

For each position store left-max and right-max; water[i] = min(leftMax[i], rightMax[i]) - height[i]. O(n) time and O(n) space.

Time
O(n)
Space
O(n)
function trap(height) {
  const n = height.length;
  const lMax = new Array(n), rMax = new Array(n);
  lMax[0] = height[0];
  for (let i = 1; i < n; i++) lMax[i] = Math.max(lMax[i-1], height[i]);
  rMax[n-1] = height[n-1];
  for (let i = n-2; i >= 0; i--) rMax[i] = Math.max(rMax[i+1], height[i]);
  let water = 0;
  for (let i = 0; i < n; i++) water += Math.min(lMax[i], rMax[i]) - height[i];
  return water;
}

Tradeoff:

2. Two-pointer O(1) space

Move the pointer on the shorter side inward; that side's water is determined by its own max, not the other side — reducing space to O(1) without losing O(n) time.

Time
O(n)
Space
O(1)
function trap(height) {
  let lo = 0, hi = height.length - 1;
  let lMax = 0, rMax = 0, water = 0;
  while (lo < hi) {
    if (height[lo] < height[hi]) {
      height[lo] >= lMax ? (lMax = height[lo]) : (water += lMax - height[lo]);
      lo++;
    } else {
      height[hi] >= rMax ? (rMax = height[hi]) : (water += rMax - height[hi]);
      hi--;
    }
  }
  return water;
}

Tradeoff:

Chegg-specific tips

Chegg expects the two-pointer O(1) space solution for this classic hard — walk through the pointer-movement invariant carefully; interviewers mark down candidates who can't justify why moving the shorter-side pointer is safe.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →