89. Trapping Rain Water
hardAsked at SnowflakeCompute 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 Sam K., 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.length1 <= n <= 2 * 10^40 <= height[i] <= 10^5
Examples
Example 1
height = [0,1,0,2,1,0,1,3,2,1,2,1]6Example 2
height = [4,2,0,3,2,5]9Approaches
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.
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.