Skip to main content

26. Trapping Rain Water

hardAsked at Ramp

Compute the total water trapped between bars of varying heights.

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

For each index, scan left and right to find the max heights, then add the difference between the smaller max and the current 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 j = 0; j <= i; j++) lMax = Math.max(lMax, height[j]);
    for (let j = i; j < height.length; j++) rMax = Math.max(rMax, height[j]);
    total += Math.min(lMax, rMax) - height[i];
  }
  return total;
}

Tradeoff:

2. Two pointers driven by the lower wall

Maintain leftMax and rightMax while two pointers converge; always advance the side whose current max is smaller, accumulating water above it.

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]) {
      if (height[l] >= lMax) lMax = height[l];
      else total += lMax - height[l];
      l++;
    } else {
      if (height[r] >= rMax) rMax = height[r];
      else total += rMax - height[r];
      r--;
    }
  }
  return total;
}

Tradeoff:

Ramp-specific tips

Ramp pulls this problem out for senior loops; they grade for being able to justify why the lower-wall side bounds the trapped volume — the same reasoning shows up in their ledger reconciliation when a partial-match window is bounded by the smaller of two sums.

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 Ramp interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →