Skip to main content

42. Trapping Rain Water

hardAsked at DRW

DRW uses Trapping Rain Water as a signal-processing proxy: the 'trapped water' at each bar is analogous to the gap between realized P&L and the maximum achievable — a measure of strategy drag bounded by the maximum left and right extrema. Two-pointer O(n) is the expected answer; DRW wants to see the transition from O(n) space to O(1).

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

Source citations

Public interview reports confirming this problem appears in DRW loops.

  • Glassdoor (2026-Q1)— DRW SWE candidates report Trapping Rain Water as a hard-difficulty problem in onsite rounds, with interviewers specifically asking for the O(1) space two-pointer solution.
  • Blind (2025-11)— DRW interview threads note this problem is used to assess candidates' ability to reduce auxiliary space usage while maintaining O(n) time.

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

Explanation: Total trapped water = 6 units.

Example 2

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

Explanation: Trapped water = 9 units.

Approaches

1. Prefix/suffix max arrays

Precompute leftMax[i] and rightMax[i]. Water at i = min(leftMax[i], rightMax[i]) − height[i].

Time
O(n)
Space
O(n)
function trap(height) {
  const n = height.length;
  const leftMax = new Array(n).fill(0);
  const rightMax = new Array(n).fill(0);
  leftMax[0] = height[0];
  for (let i = 1; i < n; i++) leftMax[i] = Math.max(leftMax[i-1], height[i]);
  rightMax[n-1] = height[n-1];
  for (let i = n-2; i >= 0; i--) rightMax[i] = Math.max(rightMax[i+1], height[i]);
  let water = 0;
  for (let i = 0; i < n; i++) water += Math.min(leftMax[i], rightMax[i]) - height[i];
  return water;
}

Tradeoff: O(n) time, O(n) space. Easy to understand and verify. Present this first, then immediately offer the O(1) space two-pointer version.

2. Two-pointer (O(1) space)

Use two pointers from each end. The side with the smaller current max is the bottleneck — process it and move the pointer inward. The water at each position is bounded by the smaller of the two maxima seen so far.

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

Tradeoff: O(n) time, O(1) space. The two-pointer approach eliminates the auxiliary arrays by using the insight that the limiting factor at any position is the smaller of the two side maxima — and you can determine which side is limiting without seeing the full arrays.

DRW-specific tips

DRW interviewers will accept the prefix/suffix array approach but will ask: 'Can you reduce to O(1) space?' Walk through the two-pointer invariant carefully: 'The side with the smaller max is the bottleneck — water added here is exactly (smaller max − current height). The other side guarantees a wall at least as tall.' After coding, they may ask: 'How does this change if the elevation values are floats instead of integers?' — the algorithm is identical, only the numeric type changes.

Common mistakes

  • Using the height instead of the running maximum in the two-pointer approach — water is bounded by the maximum seen so far, not the current boundary height.
  • Not initializing leftMax and rightMax to 0 before the two-pointer loop.
  • Comparing height[left] < height[right] when they are equal — either side can be processed; handle with <= consistently.
  • In the prefix/suffix approach, not handling single-element arrays — leftMax[0] = rightMax[0] = height[0], water = 0.

Follow-up questions

An interviewer at DRW may pivot to one of these next:

  • Trapping Rain Water II (LC 407) — 3D version; requires a min-heap (priority queue) approach.
  • How would you compute the trapped water in a live stream where height values arrive one at a time?
  • What is the expected trapped water for a random height profile sampled from a uniform distribution?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does the two-pointer approach work?

If height[left] < height[right], the water at 'left' is determined by leftMax — regardless of what is to the right, there is at least a wall of height height[right] ≥ height[left] on the right. So the bottleneck is leftMax.

What if height is all zeros?

Water is 0. leftMax and rightMax stay at 0; water += 0 at every position.

How does this problem relate to DRW's analytics?

Strategy drag analysis: the 'trapped water' at each time step is the gap between the running maximum return and the current return — identical in structure to the elevation-minus-minimum-of-maxima formula.

Practice these live with InterviewChamp.AI

Drill Trapping Rain Water and other DRW interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →