42. Trapping Rain Water
hardAsked at DoorDashGiven an elevation map, compute how much rainwater would be trapped. DoorDash uses this as a hard-end array problem — they want the two-pointer O(1) space optimization, not just the precomputed-max arrays version.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in DoorDash loops.
- Glassdoor (2026-Q1)— DoorDash SWE onsite reports cite Trapping Rain Water as a recurring hard array question.
- Blind (2025-12)— DoorDash new-grad reports list this for the two-pointer optimization probe.
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]6Explanation: In this case, 6 units of rain water are being trapped.
Example 2
height = [4,2,0,3,2,5]9Approaches
1. Precomputed max-left + max-right
For each index i, water = min(maxLeft[i], maxRight[i]) - height[i]. Precompute both arrays.
- Time
- O(n)
- Space
- O(n)
function trapPrecomputed(height) {
const n = height.length;
if (n === 0) return 0;
const maxLeft = new Array(n);
const maxRight = new Array(n);
maxLeft[0] = height[0];
for (let i = 1; i < n; i++) maxLeft[i] = Math.max(maxLeft[i - 1], height[i]);
maxRight[n - 1] = height[n - 1];
for (let i = n - 2; i >= 0; i--) maxRight[i] = Math.max(maxRight[i + 1], height[i]);
let total = 0;
for (let i = 0; i < n; i++) total += Math.min(maxLeft[i], maxRight[i]) - height[i];
return total;
}Tradeoff: Easy to derive on the board. O(n) time but uses O(n) extra. Bloomberg interviewers want this as the stepping-stone to the optimal.
2. Two-pointer (optimal O(1) space)
Move from both ends. The side with the smaller max-so-far is the bound for that side's water.
- 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: DoorDash's preferred answer. The insight: water at i is bounded by min(maxLeft, maxRight). Whichever side has the smaller max can be processed without knowing the other side's exact max.
DoorDash-specific tips
DoorDash interviewers specifically grade on whether you derive the TWO-POINTER. Lead with the precomputed-arrays version, then say 'I can drop space to O(1) — if height[l] < height[r], leftMax is the binding constraint on the left.' That insight is the signal.
Common mistakes
- Forgetting that water at i requires BOTH a left and right wall taller than height[i].
- Using current-position max instead of max-so-far from the moving side.
- Off-by-one on the < vs <= choice in the pointer compare.
Follow-up questions
An interviewer at DoorDash may pivot to one of these next:
- Container With Most Water (LC 11) — similar two-pointer, different objective.
- Trapping Rain Water II (LC 407) — 2D version with min-heap.
- Largest Rectangle in Histogram (LC 84) — stack-based, different shape.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why does the two-pointer work?
If height[l] < height[r], the right side has at least one bar >= height[l] (namely height[r]). So leftMax is the binding constraint at l. We can safely process l without knowing rightMax exactly.
Is the stack-based monotonic version useful?
Yes for breadth, but two-pointer is the canonical answer. Mention stacks if probed.
Free learning resources
Curated free links for this problem.