Skip to main content

24. Trapping Rain Water

hardAsked at Swiggy

Compute how much water is trapped between bars of given 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 rainwater the structure can trap.

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. Precompute max arrays

Build leftMax and rightMax arrays and sum min(left, right) - height at each index.

Time
O(n)
Space
O(n)
const n=height.length; const L=Array(n),R=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 sum=0; for (let i=0;i<n;i++) sum+=Math.min(L[i],R[i])-height[i];
return sum;

Tradeoff:

2. Two pointers with running maxes

Walk from both ends. Move the pointer pointing at the shorter side inward and accumulate water based on its running max. The taller side guarantees the water level on the shorter side.

Time
O(n)
Space
O(1)
function trap(height) {
  let l = 0, r = height.length - 1;
  let 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:

Swiggy-specific tips

Swiggy interviewers like the two-pointer solution because it mirrors how their batching engine reasons from both ends of a route window simultaneously.

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

Practice these live with InterviewChamp.AI →