Skip to main content

24. Trapping Rain Water

hardAsked at PayPal

Compute the total volume of water trapped between bars of varying heights. PayPal asks this problem to gauge candidates' ability to reason about prefix/suffix aggregations — a pattern that underlies cumulative transaction balance calculations and risk exposure windows.

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

Source citations

Public interview reports confirming this problem appears in PayPal loops.

  • Glassdoor (2025)— PayPal SWE L4 reported trapping rain water as the hard problem in their onsite coding round
  • LeetCode Discuss (2026)— Thread on PayPal hard problems lists LC 42 as a recurring onsite question

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 <= 20000
  • 0 <= height[i] <= 100000

Examples

Example 1

Input
height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output
6

Explanation: 6 units of water are trapped between the bars

Example 2

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

Approaches

1. Prefix/suffix max arrays

Precompute leftMax[i] (max height from 0..i) and rightMax[i] (max height from i..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), 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: Clear O(n) time, O(n) space. A good starting answer — then ask if you can reduce to O(1) space.

2. Two-pointer O(1) space

Use two pointers starting at both ends. The side with the smaller max determines water at that position: if leftMax ≤ rightMax, water at left = leftMax - height[left]; advance left. Otherwise process right symmetrically. No extra arrays needed.

Time
O(n)
Space
O(1)
function trap(height) {
  let left = 0, right = height.length - 1;
  let leftMax = 0, rightMax = 0;
  let water = 0;

  while (left < right) {
    if (height[left] <= height[right]) {
      // Left side is the bottleneck
      if (height[left] >= leftMax) {
        leftMax = height[left]; // new left max, no water here
      } else {
        water += leftMax - height[left]; // water fills to leftMax
      }
      left++;
    } else {
      // Right side is the bottleneck
      if (height[right] >= rightMax) {
        rightMax = height[right];
      } else {
        water += rightMax - height[right];
      }
      right--;
    }
  }
  return water;
}

Tradeoff: O(1) space — the insight is that whichever side has the smaller running max is the binding constraint for water level. At PayPal, describe this as computing rolling exposure limits from both ends of a transaction window simultaneously.

PayPal-specific tips

PayPal interviews focus on payment processing, fraud detection logic, financial reconciliation algorithms, and distributed transaction design. Hash maps, sliding windows, and two-pointer techniques appear frequently.

Common mistakes

  • Computing water as height[i] - min(leftMax, rightMax) instead of the reverse — water fills UP to the min wall, not DOWN
  • In the two-pointer approach, updating leftMax/rightMax after computing water instead of before — causes negative water at new maximums
  • Not handling the edge case n=1 or n=2 where no water can be trapped

Follow-up questions

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

  • Trapping Rainwater II — 3D grid version, solved with a min-heap (LC 407)
  • What is the maximum amount of water if you can remove one bar?
  • Given a stream of elevation updates, maintain the trapped water count incrementally

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 without knowing both maxes upfront?

At each step, we only care about the minimum of the two wall maxes. If leftMax ≤ rightMax, the right side is guaranteed to provide at least leftMax height (we've seen it already), so leftMax is the binding constraint — we can safely process the left pointer.

Can there be negative water values in intermediate calculations?

No — we only add water when height[i] < the running max on that side. When we update the running max (height[i] >= max), we add 0 implicitly by not computing water. The subtraction is always non-negative.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →