Skip to main content

27. Trapping Rain Water

hardAsked at Square

Calculate the maximum funds that can accumulate between settlement barriers in a payout timeline — Square's Banking team models daily balance troughs between large outflows exactly this way: water trapped between elevation bars mirrors cash trapped between sequential large disbursements.

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

Explanation: 6 units of water are trapped between the elevation bars.

Example 2

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

Approaches

1. Precompute max-left and max-right arrays

For each bar, water trapped = min(maxLeft[i], maxRight[i]) - height[i]. Build both max arrays in two passes, then sum. O(n) time, O(n) space.

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

Tradeoff:

2. Two pointers (O(1) space)

Maintain left/right pointers and running maxLeft/maxRight. The side with the shorter current max is the bottleneck — process that side. Water at each step = currentMax - height[pointer]. O(n) time, O(1) space.

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

Tradeoff:

Square-specific tips

Square uses this as a systems-thinking proxy: can you explain the invariant without the code? Say: 'water at bar i is bounded by the minimum of the tallest wall to its left and tallest wall to its right.' The array-precompute approach is easiest to verify; the two-pointer approach is what they want to see at the senior bar. Start with the precompute version, implement it cleanly, then pivot to two pointers when asked to eliminate extra space — that sequencing shows both breadth and depth.

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

Practice these live with InterviewChamp.AI →