Given an array of non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
The trapping rain water problem (LeetCode 42) is famous in the modern coding canon because it is the cleanest example of an optimization journey in any commonly-asked interview question. The naive solution is O(n²) and obvious. The clean solution is O(n) and almost magical. Walking from one to the other in 30 minutes is exactly what the interview is testing — not whether you can pull the optimal answer out of memory, but whether you can refine your approach as you find better invariants.
The setup
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Visualize the input as a histogram. After it rains, water pools where there are walls on both sides. Each unit of trapped water sits above a column whose height is less than the minimum of the tallest bar to its left and the tallest bar to its right. The total trapped water is the sum, over all columns, of max(0, min(left_max, right_max) - height).
Solution 1: brute force, O(n²)
def trap_brute(height):
n = len(height)
total = 0
for i in range(n):
left_max = max(height[:i+1])
right_max = max(height[i:])
total += max(0, min(left_max, right_max) - height[i])
return total
This is the direct translation of the formula. For each column, compute the max to its left and the max to its right, take the minimum, subtract the current height. The slice-based max calls make each iteration O(n), so the total is O(n²) time and O(1) extra space (ignoring the slices, which are themselves O(n) memory).
This is the answer most candidates produce within the first five minutes. If the interview ends here, the candidate has demonstrated comprehension of the problem but not algorithmic depth. The signal is weak.
Solution 2: prefix arrays, O(n) time, O(n) space
The key observation: left_max[i] only depends on left_max[i-1] and height[i]. Same for right_max[i]. We can precompute both in linear time.
def trap_prefix(height):
n = len(height)
if n < 3:
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])
total = 0
for i in range(n):
total += max(0, min(left_max[i], right_max[i]) - height[i])
return total
Three passes, each O(n). Total O(n) time, O(n) space. This is the answer most candidates eventually arrive at after the first hint. It demonstrates that the candidate sees the redundancy in the brute force and knows how to factor it out.
Solution 3: two pointers, O(n) time, O(1) space
Now the magical version. The insight: we do not need both left_max and right_max arrays in full. At each step, we know which side has a smaller running max, and that side determines the trapped water at the current column.
def trap_two_pointer(height):
if len(height) < 3:
return 0
left, right = 0, len(height) - 1
left_max, right_max = 0, 0
total = 0
while left < right:
if height[left] < height[right]:
if height[left] >= left_max:
left_max = height[left]
else:
total += left_max - height[left]
left += 1
else:
if height[right] >= right_max:
right_max = height[right]
else:
total += right_max - height[right]
right -= 1
return total
The argument: at any point, if height[left] < height[right], then we know right_max >= height[right] > height[left], so min(left_max, right_max) = left_max at the current left position. We can compute the water trapped at left without knowing the full right_max, because the right side is guaranteed to dominate. Symmetrically when height[right] <= height[left].
This is the O(n) time, O(1) space solution. Each pointer moves at most n positions, so the total work is linear.
The journey is the interview
Trapping rain water is famous because of the journey, not the destination. A polished interview goes like this:
- 0–2 minutes. Candidate restates the problem, draws the histogram, asks clarifying questions about negative heights, edge cases (empty array, single bar), and whether the input is mutable.
- 2–7 minutes. Brute force solution, explained as “for each column, find the bounding walls and compute the water”. Candidate states the complexity correctly: O(n²) time, O(1) space.
- 7–15 minutes. Candidate notices the redundancy in recomputing left_max and right_max for each column. Proposes prefix arrays. States complexity: O(n) time, O(n) space. Discusses memory trade-off.
- 15–25 minutes. Candidate is asked “can we do better than O(n) space?” or thinks of it themselves. Walks through the two-pointer insight, possibly with a hint. Codes it up. Verifies on the example.
- 25–30 minutes. Edge cases, off-by-one bug check, dry-run of the algorithm on a small example.
What the interviewer is watching is not whether the candidate produces the two-pointer solution from memory. The candidates who go straight to the optimal solution often signal that they have memorized it from LeetCode prep, and the interviewer’s follow-up is “explain why this works”, at which point a memorized candidate stumbles. The candidates who walk the full journey demonstrate that they can refine an approach as they find better invariants — which is the actual job.
Common pitfalls
- Confusing trapping rain water with largest rectangle in histogram. The two problems use different techniques. Largest rectangle uses a monotonic stack; trapping rain water uses two pointers or prefix arrays. Candidates sometimes start with the wrong tool.
- Off-by-one in the prefix arrays.
left_max[i]should be the max from index 0 to i inclusive. Get the inclusion wrong and the answer is off. - Two-pointer direction confusion. The pointer that points to the smaller side advances. A candidate who advances the larger side gets a wrong answer because the bounding wall guarantee no longer holds.
- Forgetting the “if no bounding wall” case. If
height = [3, 0, 0, 0], no water is trapped because there is no wall on the right. A candidate who treats the right edge as having infinite walls gets a wrong answer.
Variations interviewers ask
- 2D trapping rain water (LeetCode 407). Now the input is a 2D matrix and water can flow in all four directions. The clean solution uses a min-heap (priority queue) and is genuinely difficult — usually a senior-level interview question.
- “How would you visualize this?” A non-coding follow-up that tests whether the candidate can describe the algorithm in plain English.
- “What if the bars are non-integer?” Tests whether the candidate notices that the algorithm is type-agnostic and works for floats.
- “Can you do it in one pass instead of two?” The two-pointer is technically one pass; this is the question pushing toward the O(1) space solution if the candidate has not already proposed it.
Is it still asked in 2026?
Yes, frequently. Trapping rain water remains in the LeetCode top-50 most-asked at FAANG and tier-2 companies. The 2D variation is a senior/staff-level question that shows up at AI labs, fintech, and data infrastructure roles. The 1D version has been around since at least 2010 and shows no signs of being retired — unlike the brainteasers, this question still works as a filter because the optimization journey reveals real engineering ability that LeetCode prep alone cannot fake.
The cultural status of trapping rain water in the coding canon is roughly equivalent to FizzBuzz at the bottom of the difficulty range — except trapping rain water sits in the medium tier and tests something genuinely meaningful. It has earned its place in the canon by being the cleanest example of how a deceptively simple problem can have multiple solutions of increasing elegance, and how the path between them is itself the signal.
Frequently Asked Questions
What is the time complexity of the optimal solution?
O(n) time and O(1) extra space, using two pointers. Each pointer moves at most n positions, so total work is linear, and only a constant number of variables are stored.
Should I write the brute force first or jump to the optimal solution?
Generally, walk the journey: state the brute force, then improve. Jumping to the optimal solution from memory often triggers a “now explain why this works” follow-up that catches memorized candidates. The journey is the actual signal.
Is this problem still asked at FAANG in 2026?
Yes. It remains in the LeetCode top-50 most-asked. The 1D version is medium-tier; the 2D extension is a senior+ question.
What is the relationship between this and “largest rectangle in histogram”?
Both involve histograms but use different techniques. Largest rectangle uses a monotonic stack; trapping rain water uses two pointers. The problems are siblings in the canon and are sometimes asked back-to-back to test whether the candidate can choose the right tool.
Can I solve this with dynamic programming?
Yes — the prefix-array solution is essentially DP. left_max[i] = max(left_max[i-1], height[i]) is a one-state recurrence. The two-pointer solution is the space-optimized version of the same DP.