Skip to main content

24. Trapping Rain Water

hardAsked at SoFi

Given heights of bars, compute how much rain water can be trapped — SoFi uses this to test prefix-max reasoning that mirrors high-water-mark logic in portfolio drawdown calculations.

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
[0,1,0,2,1,0,1,3,2,1,2,1]
Output
6

Example 2

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

Approaches

1. Brute force per-column scan

For each index, scan left and right to find max heights, then water[i] = min(leftMax, rightMax) - height[i].

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.min(lMax, rMax) - height[i];
  }
  return total;
}

Tradeoff:

2. Two pointers

Use left and right pointers tracking leftMax and rightMax. Always advance the side with the smaller max, because that side bounds the water at the current index.

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

Tradeoff:

SoFi-specific tips

SoFi grades on whether you can articulate the two-pointer invariant — drawdown calculations in portfolio NAV time-series use the same running-max bookkeeping, and explaining the parallel earns bonus signal.

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

Practice these live with InterviewChamp.AI →