Skip to main content

42. Trapping Rain Water

hardAsked at eBay

eBay's data visualization team renders capacity charts for warehouse storage — thinking of elevation bars as bin capacities and water as overflow volume. Trapping Rain Water is a classic two-pointer problem that eBay uses at the hard level to test whether candidates can optimize from O(n) space (prefix/suffix arrays) to O(1) space (two-pointer) through clear reasoning.

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

Source citations

Public interview reports confirming this problem appears in eBay loops.

  • Glassdoor (2025-12)— Cited in eBay senior SWE onsite reports as a hard two-pointer problem for testing space-optimization reasoning.
  • Blind (2025-10)— eBay SWE threads mention Trapping Rain Water as an occasional hard problem that appears in the algorithm-focused onsite round.

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 (visualize the spaces between bars filled with water up to the min of their left and right max boundaries).

Example 2

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

Explanation: Water trapped above positions 1-4, bounded by max bars on each side.

Approaches

1. Prefix and suffix max arrays

Precompute leftMax[i] (max height from 0 to i) and rightMax[i] (max height from i to n-1). Water at position 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. Clear and easy to verify. Good starting point. Then optimize to O(1) space with two pointers.

2. Two Pointers (O(1) space)

Use left and right pointers converging from both ends. Track maxLeft and maxRight. The pointer with the smaller boundary moves inward — water at that position is min(maxLeft, maxRight) - height[pointer].

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]; // new max; no water trapped here
      } else {
        water += maxLeft - height[left]; // water above this position
      }
      left++;
    } else {
      if (height[right] >= maxRight) {
        maxRight = height[right];
      } else {
        water += maxRight - height[right];
      }
      right--;
    }
  }
  return water;
}

Tradeoff: O(1) space — the optimal solution. The key insight: if height[left] <= height[right], the left side is the bottleneck; water at left is determined by maxLeft (since maxRight >= height[right] >= height[left] ensures the right side is taller). Mirror for right.

eBay-specific tips

eBay interviewers expect you to progress from the O(n) space prefix/suffix solution to the O(1) two-pointer solution. Explain the two-pointer insight clearly: 'When height[left] <= height[right], the left boundary determines water capacity because the right wall is guaranteed to be at least as tall. So I can safely compute water at left using only maxLeft.' Draw a 4-bar example ([3,0,0,2]) on a whiteboard to show both approaches before coding.

Common mistakes

  • Computing water as min(leftMax, rightMax) - height[i] when leftMax or rightMax could be less than height[i] — impossible since leftMax and rightMax are maximums including height[i] itself.
  • In the two-pointer approach, moving the pointer with the larger height instead of the smaller — inverts the bottleneck logic.
  • Not updating maxLeft/maxRight before computing water — the max must include the current position.
  • Off-by-one: using left < right instead of left <= right — with left == right there's only one bar; water there is 0 so including or excluding doesn't matter, but using strict < is cleaner.

Follow-up questions

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

  • Container With Most Water (LC 11) — similar two-pointer pattern but maximize area, not total water.
  • Largest Rectangle in Histogram (LC 84) — complementary bar-based problem also testing stack or two-pointer reasoning.
  • How would you compute the trapped water if the elevation map is 3D (LC 407 — Trapping Rain Water II)?

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 is the two-pointer approach correct?

When height[left] <= height[right], maxRight >= height[right] >= height[left], so the water at left is bounded by maxLeft, not maxRight. We can safely compute water at left without knowing the full rightMax array.

What if all bars are the same height?

No water is trapped — every position has maxLeft = maxRight = height, so min(maxLeft, maxRight) - height = 0 everywhere.

Can this be solved with a stack?

Yes — a monotonic decreasing stack approach processes bars in O(n) by computing water horizontally layer by layer. The two-pointer approach is simpler; the stack approach generalizes to 2D rain water problems.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →