Skip to main content

26. Trapping Rain Water

hardAsked at GitHub

Compute water trapped between bars using two-pointer or stack techniques — a classic hard problem GitHub includes in senior engineer interviews to test array reasoning under constraints.

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

Problem

Given n non-negative integers representing an elevation map where each bar has width 1, compute the total amount of water that can be trapped 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. Precompute left/right max arrays

Build leftMax[i] and rightMax[i] arrays, then water[i] = min(leftMax[i], rightMax[i]) - height[i].

Time
O(n)
Space
O(n)
// leftMax[i] = max(height[0..i])
// rightMax[i] = max(height[i..n-1])
// water = sum of min(leftMax[i], rightMax[i]) - height[i]
// Correct but O(n) extra space

Tradeoff:

2. Two-pointer O(1) space

Maintain l/r pointers and leftMax/rightMax variables. The shorter side determines water level: if leftMax < rightMax, water at l = leftMax - height[l]; advance l; else advance r symmetrically.

Time
O(n)
Space
O(1)
function trap(height) {
  let l = 0, r = height.length - 1;
  let leftMax = 0, rightMax = 0, water = 0;
  while (l < r) {
    if (height[l] <= height[r]) {
      leftMax = Math.max(leftMax, height[l]);
      water += leftMax - height[l];
      l++;
    } else {
      rightMax = Math.max(rightMax, height[r]);
      water += rightMax - height[r];
      r--;
    }
  }
  return water;
}

Tradeoff:

GitHub-specific tips

GitHub hard interviews expect you to arrive at O(1) space without prompting — start by explaining the two-array solution, then proactively optimize to two pointers to demonstrate algorithm intuition GitHub values.

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

Practice these live with InterviewChamp.AI →