Skip to main content

23. Trapping Rain Water

hardAsked at Monzo

Given daily savings-pot heights, compute the total amount of unused capacity trapped between peaks.

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. Return the total trapped water as an integer.

Constraints

  • 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. Precomputed maxLeft and maxRight

Compute maxLeft[i] and maxRight[i] in two passes; water at i is min(maxLeft[i], maxRight[i]) - height[i].

Time
O(n)
Space
O(n)
const n = height.length, L = new Array(n), R = new Array(n);
L[0] = height[0]; for (let i = 1; i < n; i++) L[i] = Math.max(L[i-1], height[i]);
R[n-1] = height[n-1]; for (let i = n-2; i >= 0; i--) R[i] = Math.max(R[i+1], height[i]);
let total = 0;
for (let i = 0; i < n; i++) total += Math.min(L[i], R[i]) - height[i];
return total;

Tradeoff:

2. Two-pointer constant space

Move left and right pointers inward; the lower side determines the trapped water at that pointer because the higher side already bounds it.

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

Tradeoff:

Monzo-specific tips

Monzo asks you to defend the two-pointer invariant in plain English because the ledger team values explanations a junior engineer could follow on call.

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

Practice these live with InterviewChamp.AI →