Skip to main content

42. Trapping Rain Water

hardAsked at Akamai

Calculate how much water can be trapped between elevation bars. Akamai uses this as a two-pointer mastery test — the same left-and-right boundary tracking logic appears in buffer capacity analysis for edge server memory pools where headroom must be calculated between high-water marks.

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

Source citations

Public interview reports confirming this problem appears in Akamai loops.

  • Glassdoor (2026-Q1)— Akamai SWE interview reports cite Trapping Rain Water as a high-signal hard problem in senior-level coding rounds.
  • Blind (2025-11)— Multiple Akamai threads confirm this appears in onsite rounds with explicit follow-ups on the O(1) space optimization.

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: The elevation map traps 6 units of water total.

Example 2

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

Explanation: 9 units of water trapped in the valleys.

Approaches

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

Maintain left and right pointers. Track maxLeft and maxRight. At each step, process the side with the smaller max — the water at that position is bounded by its side's max. Move the pointer inward.

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

Tradeoff: O(n) time, O(1) space. This is the optimal solution. The key insight: we don't need to know the actual maximum on both sides simultaneously — if height[left] < height[right], the left side's water is bounded by maxLeft regardless of what's on the right.

2. Prefix/suffix max arrays

Pre-compute leftMax[i] = max height to the left of i, rightMax[i] = max to the right. 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);
  const rightMax = new Array(n);
  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. Easier to derive intuitively — good as a first explanation. Then optimize to the two-pointer approach to eliminate the extra arrays.

Akamai-specific tips

Lead with the intuition for the prefix/suffix approach first: 'Water at position i is min(tallest bar to the left, tallest bar to the right) minus height[i].' Then explain the two-pointer optimization: 'We can compute both maxes simultaneously because we only need to process the constrained side — if maxLeft < maxRight, the left bar's water is determined regardless of the right side's specifics.' Akamai interviewers value the progression from O(n)-space to O(1)-space explicitly stated.

Common mistakes

  • Computing water as max - height instead of min(leftMax, rightMax) - height — the bottleneck is the shorter wall, not the taller one.
  • Not handling the two-pointer update correctly — always advance the pointer on the side with the smaller height, not the smaller max.
  • Forgetting negative water is impossible — Math.max(0, min(leftMax, rightMax) - height[i]) is a safety net, though if leftMax/rightMax are computed correctly, the difference is always >= 0.

Follow-up questions

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

  • Container With Most Water (LC 11) — a simpler two-pointer variant (no bars between the walls).
  • Trapping Rain Water II (LC 407) — extend to a 3D elevation map; requires a min-heap.
  • How would you compute the water trapped in a circular elevation map?

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 process the smaller-height side in the two-pointer approach?

The water at any position is bounded by the minimum of the two side maxima. If height[left] < height[right], then leftMax < rightMax is guaranteed (or maxLeft is the binding constraint). Processing the left side now is safe — we know its water contribution is determined by maxLeft.

What if all bars are the same height?

No water is trapped — min(leftMax, rightMax) - height[i] = 0 everywhere. The algorithm correctly returns 0.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →