Skip to main content

25. Trapping Rain Water

hardAsked at Gojek

Given an elevation map, compute how much water can be trapped between the bars after raining.

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

Example 2

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

Approaches

1. Per-index left/right max

Precompute the max bar to the left and right of each index, then sum min(L, R) - h[i].

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

Tradeoff:

2. Two pointers

Move two pointers inward, tracking running leftMax and rightMax. The side with the smaller running max determines how much water is trapped at that index, in O(1) extra space.

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

Tradeoff:

Gojek-specific tips

Gojek hard rounds want a constant-space sweep when memory matters, the same shape they reach for on mobile-first telemetry buffers running across SEA networks.

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

Practice these live with InterviewChamp.AI →