Skip to main content

94. Trapping Rain Water

hardAsked at Workday

Compute how much water can be trapped after raining on a histogram. Workday uses this for two-pointer mastery — same shape as 'how much pay-period overflow is held by the maximum-flexible-spending walls'.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE3 onsite.

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

Example 2

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

Approaches

1. Prefix max + suffix max arrays

For each index, water = min(maxLeft, maxRight) - height[i].

Time
O(n)
Space
O(n)
// build leftMax[] and rightMax[]; sum min(left[i], right[i]) - h[i]

Tradeoff: O(n) extra space.

2. Two pointers

lo, hi from ends. Move the side with the smaller max. Water at each step is maxOfThatSide - height[pointer].

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

Tradeoff: O(1) space. The trick: water at lo is bounded by the smaller of (leftMax, rightMax). If height[lo] < height[hi], we know rightMax >= height[hi] > height[lo], so the limiter is leftMax.

Workday-specific tips

Workday wants the two-pointer version. The proof: if h[lo] < h[hi], then rightMax (whatever it is) is at least h[hi] > h[lo], so leftMax is the binding constraint at lo. Articulate this before coding.

Common mistakes

  • Tracking only one max — misses the constraint from the other side.
  • Adding water from the side that's the BIGGER max — wrong direction.
  • Off-by-one — should stop when lo == hi (already counted).

Follow-up questions

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

  • Trapping Rain Water II (LC 407) — 2D version with priority queue.
  • Container With Most Water (LC 11) — similar two-pointer.
  • What if heights are negative?

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 move the smaller side?

If h[lo] < h[hi], then rightMax is at least h[hi] > h[lo]. So at lo, the limiting factor is leftMax, which we already know. We can safely compute water at lo and advance.

Stack-based alternative?

Yes — monotonic decreasing stack of indices. Pop when current is taller; compute water above the popped bar. O(n) time.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →