Skip to main content

24. Trapping Rain Water

hardAsked at Squarespace

Compute how much water an elevation map traps after raining; Squarespace uses it to test whether you can reduce O(n) prefix arrays to a constant-space two-pointer pass.

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. Prefix-max and suffix-max arrays

Precompute the tallest bar to the left and right of every index, then sum min(L, R) - h.

Time
O(n)
Space
O(n)
const L=[],R=[],n=height.length;
let m=0; for(let i=0;i<n;i++){ m=Math.max(m,height[i]); L[i]=m; }
m=0; for(let i=n-1;i>=0;i--){ m=Math.max(m,height[i]); R[i]=m; }
let ans=0; for(let i=0;i<n;i++) ans+=Math.min(L[i],R[i])-height[i];
return ans;

Tradeoff:

2. Two pointers tracking running max

Move inward from both ends, always advancing the smaller side and crediting water against the running max on that side. Constant space.

Time
O(n)
Space
O(1)
function trap(height) {
  let l = 0, r = height.length - 1, lm = 0, rm = 0, ans = 0;
  while (l < r) {
    if (height[l] < height[r]) {
      if (height[l] >= lm) lm = height[l]; else ans += lm - height[l];
      l++;
    } else {
      if (height[r] >= rm) rm = height[r]; else ans += rm - height[r];
      r--;
    }
  }
  return ans;
}

Tradeoff:

Squarespace-specific tips

Squarespace likes when you justify why moving the shorter side first is always safe, and tie the streaming-max idea back to their analytics ingestion rolling-max counters.

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

Practice these live with InterviewChamp.AI →