How Do You Solve the Trapping Rain Water Problem?
Learn the O(n) two-pointer solution to the Trapping Rain Water problem and how to explain it in a coding interview.
Expected Interview Answer
The Trapping Rain Water problem, given an array of bar heights, is solved optimally with a two-pointer approach in O(n) time and O(1) space: water trapped above any bar equals min(max height to its left, max height to its right) minus its own height, and two pointers moving inward from both ends track the running left-max and right-max without needing precomputed arrays.
The brute-force approach computes, for every index, the maximum height to its left and the maximum height to its right by scanning outward each time, giving O(n squared) time. A better approach precomputes left-max and right-max arrays in two passes, giving O(n) time but O(n) extra space. The optimal two-pointer approach eliminates the extra arrays: start pointers at both ends with left_max and right_max initialized to zero, and at each step move whichever pointer has the smaller current height inward, because that side's water level is bounded by the smaller of the two maxes seen so far — you can safely resolve the water trapped at that pointer using only the max on its own side. If the current bar exceeds the running max on its side, update the max instead of trapping any water there; otherwise add (max - height) to the total trapped water. This works because whichever side is shorter, its water level is always capped by its own side's max, since the taller side guarantees at least that much wall on the other end. The same core insight — water level equals the min of two bounding maxes — also underlies the 2D variant of this problem, solved with a priority queue instead of two pointers.
- O(n) time, single pass with two pointers
- O(1) extra space, no precomputed arrays needed
- Elegant use of the "shorter side is always safely resolvable" insight
- Improves on the O(n) time / O(n) space precomputed-array approach
AI Mentor Explanation
A groundskeeper looks at a row of uneven boundary rope posts of different heights after a storm and wants to know how much rainwater pooled between them. Water sitting above any post is trapped only up to the shorter of the tallest post to its left and the tallest post to its right, since water spills over the lower wall. Walking two survey markers inward from each end of the row, whichever side currently has the shorter tallest-post-so-far gets resolved first, because that side's water level is already capped and cannot be affected by anything still unexamined on the other side. This lets the groundskeeper total up the trapped water in a single walk down the row from both ends, without re-measuring every post against every other post.
Step-by-Step Explanation
Step 1
Set up two pointers and two running maxes
left = 0, right = len(height) - 1, left_max = right_max = 0.
Step 2
Move the pointer on the shorter side
If height[left] < height[right], process left; otherwise process right, since that side is safely resolvable.
Step 3
Update the max or trap water
If the current bar exceeds its side's running max, update the max; otherwise add (max - height) to the total trapped water.
Step 4
Continue until pointers meet
Repeat, moving the processed pointer inward, until left and right cross.
What Interviewer Expects
- Explain the core insight: trapped water = min(left max, right max) - own height
- Justify why the two-pointer approach is correct (the shorter side is always safely resolvable)
- State the O(n) time, O(1) space complexity and contrast with brute force and precomputed-array approaches
- Walk through a small example correctly by hand
Common Mistakes
- Moving the wrong pointer (the taller side instead of the shorter side)
- Forgetting to update left_max/right_max before deciding whether water is trapped at that index
- Reaching for the O(n) space precomputed-array solution as if it were optimal, without mentioning the O(1) space two-pointer improvement
- Not handling arrays shorter than 3 elements, which trap no water
Best Answer (HR Friendly)
“Trapping Rain Water asks how much water would sit on top of a row of bars of different heights after rain. I solve it by walking inward from both ends of the row at once, always resolving the side that is currently shorter, because that side's water level is fully determined by the tallest bar seen so far on just that side — this lets me compute the total trapped water in a single pass without extra memory.”
Code Example
def trap(height):
if not height:
return 0
left, right = 0, len(height) - 1
left_max, right_max = 0, 0
total = 0
while left < right:
if height[left] < height[right]:
left_max = max(left_max, height[left])
total += left_max - height[left]
left += 1
else:
right_max = max(right_max, height[right])
total += right_max - height[right]
right -= 1
return total
print(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])) # 6Follow-up Questions
- How would you solve the 2D version of this problem (Trapping Rain Water II)?
- How does the precomputed left-max/right-max array approach compare in tradeoffs to the two-pointer approach?
- Why is it always safe to resolve the shorter side first with the two-pointer method?
- How would you solve this using a monotonic stack instead?
MCQ Practice
1. What is the optimal time and space complexity for Trapping Rain Water using two pointers?
The two-pointer approach achieves O(n) time with O(1) extra space by tracking only running left-max and right-max.
2. How much water is trapped above a bar of height h, given left max L and right max R of the array?
Water is bounded by the shorter of the two surrounding maxes, so trapped water is min(L, R) minus the bar's own height.
3. In the two-pointer approach, which pointer should be moved inward at each step?
The side with the smaller current height is safely resolvable because its water level is capped by its own side's max.
Flash Cards
What formula gives trapped water above a single bar? — min(left max, right max) minus the bar's own height.
What is the optimal time and space complexity for this problem? — O(n) time, O(1) space, using two pointers.
Why is it safe to resolve the shorter side first in the two-pointer method? — Because its water level is already capped by its own side's max, independent of the unexamined far side.
What is a simpler but less space-efficient alternative to two pointers? — Precomputing left-max and right-max arrays in two passes: O(n) time but O(n) space.