Skip to main content

26. Trapping Rain Water

hardAsked at MercadoLibre

Compute how much rainwater is trapped between bars of an elevation map.

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. Each column's water level is bounded by the shorter of the tallest bars on its left and its right.

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. Per-column scan

For each column, scan left and right to find the tallest bars, then add max(0, min(L,R) - height[i]).

Time
O(n^2)
Space
O(1)
let total = 0;
for (let i = 0; i < height.length; i++) {
  let L = 0, R = 0;
  for (let l = 0; l <= i; l++) L = Math.max(L, height[l]);
  for (let r = i; r < height.length; r++) R = Math.max(R, height[r]);
  total += Math.min(L, R) - height[i];
}
return total;

Tradeoff:

2. Two pointers

Walk left and right pointers inward; whichever side has the shorter running max determines that column's water and advances.

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

MercadoLibre-specific tips

MercadoLibre data engineers ask this to verify running-extremum thinking — the same pattern they use to size buffer capacity between courier dispatch waves so packages don't 'overflow' the regional depot.

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

Practice these live with InterviewChamp.AI →