Skip to main content

28. Trapping Rain Water

hardAsked at Mercury

Given an elevation map, compute how much rain water is trapped between the bars.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an array of non-negative integers representing an elevation map where each bar has unit width, compute how much water it can trap after raining. Water above each index equals min(maxLeft, maxRight) minus the index height.

Constraints

  • 1 <= height.length <= 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 / maxRight arrays

Build two arrays of left/right running maxima, then sum min(L[i], R[i]) - h[i].

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

Tradeoff:

2. Two-pointer running max

Walk inward from both ends, tracking maxLeft and maxRight; the smaller side's max bounds the water above its pointer, so contribute and advance.

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

Tradeoff:

Mercury-specific tips

Mercury frames this as cash-runway visualization — each month's burn bar traps available reserve relative to the highest historical balance left and right of the gap, mapping rainwater directly to multi-account aggregation reserves.

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

Practice these live with InterviewChamp.AI →