Skip to main content

42. Trapping Rain Water

hardAsked at Glean

Glean asks this hard-tier problem to test whether candidates can derive an O(1)-space two-pointer solution from an O(n)-space prefix/suffix scan — the same optimization mindset that matters in large-scale index traversal where memory allocation is expensive.

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

Source citations

Public interview reports confirming this problem appears in Glean loops.

  • Glassdoor (2025-11)— Reported in Glean hard-round coding feedback as a problem used to distinguish senior candidates who can optimize space.
  • Blind (2025-09)— Glean threads list Trapping Rain Water as an occasional hard used to test two-pointer mastery beyond obvious sliding-window applications.

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: Water accumulates in the valley between heights 4 and 5.

Approaches

1. Prefix/suffix max arrays

Compute leftMax[i] (maximum height to the left of i inclusive) and rightMax[i] (maximum to the right inclusive). 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), 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 and space. Intuitive — presents the logic clearly. Good first answer; then optimize to O(1) space.

2. Two pointers (O(1) space)

Use two pointers from both ends. The side with the smaller max height is the limiting factor for water trapping. Process that side and advance its pointer inward.

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

Tradeoff: O(n) time, O(1) space. The key insight: when height[left] <= height[right], the right boundary is tall enough that the left side's water is fully determined by leftMax — you don't need to know the exact right boundary to make this decision.

Glean-specific tips

Walk through a small example (height = [4,2,0,3]) before coding. Glean values methodical reasoning. Present the prefix/suffix array solution first to demonstrate you understand the invariant, then say 'I can reduce this to O(1) space by noting that the shorter side determines how much water that position holds — two pointers let me process one side at a time.' That progression shows engineering maturity.

Common mistakes

  • Subtracting height[i] from the wrong side — always subtract the actual height at position i from the effective water level.
  • Not advancing the pointer after processing — must increment left (or decrement right) after each step.
  • Using height[left] < height[right] instead of <= — both are correct; the loop terminates regardless of tie-breaking because both pointers converge.
  • Starting both pointers at 0 — right must start at n-1 for two-pointer approach.

Follow-up questions

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

  • Container With Most Water (LC 11) — related two-pointer problem; find the maximum area of a container.
  • Trapping Rain Water II (LC 407) — 3D version where water is trapped in an elevation matrix.
  • How would you compute the total water volume in a stream where the elevation array is too large to fit in memory?

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 can we process the left side when height[left] <= height[right]?

Because the right side has a bar at least as tall as the current leftMax. The water at position left is therefore exactly max(0, leftMax - height[left]) — the right wall is guaranteed to be tall enough to hold it.

What does water += leftMax - height[left] calculate?

The trapped water at the current left position. leftMax is the highest bar seen from the left so far. If height[left] < leftMax, water pools to height leftMax at this position; the difference is trapped volume.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →