Skip to main content

42. Trapping Rain Water

hardAsked at Broadcom

Calculate total water trapped between bars of an elevation map. Broadcom asks this because the two-pointer technique and the min-of-max-prefix pattern directly generalise to buffer-fill calculations in streaming pipelines — a common problem in Broadcom's data-plane throughput analysis.

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

Source citations

Public interview reports confirming this problem appears in Broadcom loops.

  • Glassdoor (2026-Q1)— Reported in Broadcom SWE senior onsite rounds as a two-pointer hard problem testing boundary reasoning.
  • Blind (2025-12)— Broadcom threads list Trapping Rain Water as a high-signal hard problem that distinguishes strong algorithm candidates.

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: Six units of water are trapped between the bars.

Example 2

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

Explanation: Water is trapped in the two valleys between the outer walls.

Approaches

1. Prefix/suffix max arrays

Precompute leftMax[i] (max height from left to i) and rightMax[i] (max height from right to 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 verify correctness. Good starting point before presenting the two-pointer optimisation.

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

Use left and right pointers. The side with the smaller max determines how much water can be trapped. Move the smaller-side pointer inward, computing water as it goes.

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]) {
      leftMax = Math.max(leftMax, height[left]);
      water += leftMax - height[left];
      left++;
    } else {
      rightMax = Math.max(rightMax, height[right]);
      water += rightMax - height[right];
      right--;
    }
  }
  return water;
}

Tradeoff: O(n) time, O(1) space. The key insight: if height[left] <= height[right], the water at left is bounded by leftMax (not rightMax) — because rightMax is guaranteed to be at least height[right] >= height[left]. This is the answer Broadcom expects for a senior candidate.

Broadcom-specific tips

At Broadcom, present both approaches. Lead with prefix/suffix to establish correctness, then offer the two-pointer optimisation: 'I can avoid the extra arrays by maintaining left and right max in two variables — the invariant is that the smaller-side max is the binding constraint.' The two-pointer approach requires careful justification — explain why the smaller side is the bottleneck before writing any code. Broadcom interviewers for senior roles often ask: 'Why does the smaller-side pointer advance and not the larger-side?'

Common mistakes

  • Using height[i] - min(leftMax, rightMax) instead of min(leftMax, rightMax) - height[i] — water is always non-negative.
  • In the two-pointer approach, advancing the larger-side pointer — the invariant breaks because the smaller side is the constraint.
  • Not updating leftMax/rightMax before computing water in the two-pointer loop.
  • Forgetting edge cases: n < 3 always traps 0 water.

Follow-up questions

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

  • Trapping Rain Water II (LC 407) — 3D grid version using a min-heap.
  • Container With Most Water (LC 11) — simpler two-pointer variant (no height bars, just two walls).
  • How would you compute running water trapped as bars are added dynamically?

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 minimum of leftMax and rightMax the correct water level?

Water at position i is limited by the shorter of the two tallest walls on either side — it overflows through the shorter wall. min(leftMax[i], rightMax[i]) is that shorter wall's height.

Why does the two-pointer approach advance the smaller-side pointer?

The water at the smaller side is fully determined by the smaller-side max — the other side is already at least as tall. Advancing the smaller side maintains the invariant without needing the full prefix/suffix arrays.

What is the 3D variant (LC 407)?

In 3D, water flows to the lowest border cell. A min-heap (priority queue) processes border cells in height order, propagating water inward — same min-boundary principle but in two dimensions.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →