Skip to main content

89. Trapping Rain Water

hardAsked at Snowflake

Compute the volume of water trapped between bars after rain. Snowflake asks this for the two-pointer trick — relevant to computing memory-bound estimation in their planner where left and right side constraints both matter.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake compiler-team uses this for plan-cost intuition.
  • LeetCode Discuss (2025-11)— Reported at Snowflake SDE-II screens.

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. Precompute left-max and right-max arrays

leftMax[i] = max of height[0..i]; rightMax[i] = max of height[i..n-1]. Water at i = min(leftMax, rightMax) - 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 total = 0;
  for (let i = 0; i < n; i++) total += Math.min(leftMax[i], rightMax[i]) - height[i];
  return total;
}

Tradeoff: Linear time, O(n) extra. Clear but space-heavy.

2. Two-pointer (optimal)

l, r from both ends. Track leftMax and rightMax. If leftMax < rightMax: water at l = leftMax - height[l]; advance l. Else: water at r = rightMax - height[r]; retreat r.

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

Tradeoff: O(1) extra. The insight: the side with the smaller height is the bottleneck for water on that side.

Snowflake-specific tips

Snowflake interviewers want the two-pointer + 'shorter side is the bottleneck' argument. Bonus signal: connect to memory bounds in plan execution — when a join's hash side has capacity X and the probe side flows at rate Y, the slower side bottlenecks throughput, similar to the shorter wall bottlenecks water depth.

Common mistakes

  • Updating max AFTER computing water — leads to wrong values on a new max.
  • Comparing height[l] and height[r] but using the wrong-side max in the water formula.
  • Stopping at l <= r instead of l < r — extra iteration that doesn't add water.

Follow-up questions

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

  • Trapping Rain Water II (LC 407) — 2D variant.
  • Container With Most Water (LC 11) — related but different.
  • How does Snowflake estimate memory bounds for join operations?

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 shorter side the bottleneck?

Water at index l is min(leftMax, rightMax) - height[l]. If we know height[l] < height[r], the right side has a wall at least as tall as height[r], so leftMax is the binding constraint.

How does this connect to plan execution?

Both processes (left and right walls; producer and consumer) gate the outcome by the smaller capacity. Snowflake's plan cost model accounts for the slower side as the throughput limiter.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →