Trapping Rain Water is the #7 most asked LeetCode problem globally — and the most well-known HARD problem that every serious candidate must own.
Our analysis of 10,385 verified interview questions across 259 companies shows this appeared 100 times across 42 companies — including Google, Amazon, Meta, Microsoft, Goldman Sachs, Citadel, Jane Street, Bloomberg, and Airbnb.
Most candidates know the O(n) DP approach with prefix/suffix arrays. But the optimal solution — O(n) time, O(1) space using two pointers — is what separates good answers from great ones. This guide walks through all three approaches so you can explain the progression clearly in an interview.
| Metric | Value |
|---|---|
| Total Interview Appearances | 100 verified mentions |
| Companies That Ask It | 42 companies |
| Global Rank | #7 out of 10,385 questions |
| Difficulty | Hard |
| Core Patterns | Two Pointers, DP, Stack, Monotonic Stack |
Google, Amazon, Meta, Microsoft, Goldman Sachs, Citadel, Jane Street, Bloomberg, Airbnb, Adobe, Atlassian, BitGo, ByteDance, Cisco, DE Shaw, CrowdStrike, Expedia, Flipkart, Grammarly, IBM, Intel, Intuit, MakeMyTrip, Media.net, Myntra, and 17 more.
LeetCode #42 — Trapping Rain Water
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.
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Input: height = [4,2,0,3,2,5]
Output: 9Water trapped at position i = min(max_left[i], max_right[i]) - height[i].
The water level at any position is determined by the shorter of the two surrounding walls. If the left max is 3 and the right max is 5, water fills up to height 3 at that position (limited by the shorter wall). Then subtract the bar's own height.
water[i] = max(0, min(left_max[i], right_max[i]) - height[i])
The max(0, ...) ensures we never count negative water (when the bar is taller than both walls).
Precompute left_max[i] (max height from index 0 to i) and right_max[i] (max height from i to end). Then apply the formula.
def trap(height):
n = len(height)
if n == 0:
return 0
left_max = [0] * n
right_max = [0] * n
left_max[0] = height[0]
for i in range(1, n):
left_max[i] = max(left_max[i-1], height[i])
right_max[n-1] = height[n-1]
for i in range(n-2, -1, -1):
right_max[i] = max(right_max[i+1], height[i])
water = 0
for i in range(n):
water += min(left_max[i], right_max[i]) - height[i]
return waterThe DP approach uses O(n) space for the two arrays. Can we do O(1)? Yes — because we only need the minimum of left_max and right_max at each position. Two pointers let us process whichever side has the smaller max first.
Key observation: If left_max < right_max, then the water at the left pointer is determined by left_max (regardless of what's on the right, since right_max ≥ left_max). Move left pointer inward. Otherwise, process right pointer.
def trap(height: list[int]) -> int:
left, right = 0, len(height) - 1
left_max = right_max = 0
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= left_max:
left_max = height[left]
else:
water += left_max - height[left]
left += 1
else:
if height[right] >= right_max:
right_max = height[right]
else:
water += right_max - height[right]
right -= 1
return waterclass Solution {
public int trap(int[] height) {
int left = 0, right = height.length - 1;
int 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;
}
}var trap = function(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;
};| Approach | Time | Space |
|---|---|---|
| DP (prefix/suffix arrays) | O(n) | O(n) |
| Two Pointers | O(n) | O(1) |
| Monotonic Stack | O(n) | O(n) |
Tag this on DSAPrep.dev under Two Pointers and Dynamic Programming.