Skip to main content

24. Trapping Rain Water

hardAsked at Revolut

Compute the total water trapped between bars of varying height, a Revolut hard-screen that mirrors computing total locked-up reserves between peaks in a time-series of balance snapshots.

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. Target O(n) time and O(1) space.

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. Prefix-max + suffix-max arrays

Precompute max-left and max-right at every index; trapped = min(left,right) - h.

Time
O(n)
Space
O(n)
// build L[i]=max(h[0..i]), R[i]=max(h[i..n-1]); sum max(0, min(L[i],R[i])-h[i])

Tradeoff:

2. Two pointers

Track leftMax and rightMax pointers; whichever side is lower is bounded by its max, so accumulate water from that side and advance. O(1) extra space.

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:

Revolut-specific tips

Revolut interviewers want you to prove the two-pointer invariant explicitly — they care that you can articulate why the shorter side is bounded by its own running max, the same proof you'd write for a locked-reserves bound in a treasury system.

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

Practice these live with InterviewChamp.AI →