Trapping Rain Water
Asked at Google, Meta, Amazon, Oracle, Salesforce, OpenAI, Walmart
Problem
Given n non-negative integers representing an elevation map, compute how much water it can trap after raining. This is a classic hard problem that tests your ability to reason about left and right maximums.
Asked At
| Company | Difficulty | |
|---|---|---|
| Hard | View all Google questions → | |
| Meta | Hard | View all Meta questions → |
| Amazon | Hard | View all Amazon questions → |
| Oracle | Hard | View all Oracle questions → |
| Salesforce | Hard | View all Salesforce questions → |
| OpenAI | Hard | View all OpenAI questions → |
| Walmart | Hard | View all Walmart questions → |
How to Think About It
Brute force: for each position i, scan left to find max_left and scan right to find max_right. Water at i = min(max_left, max_right) - height[i]. O(n²) time because each position requires two scans.
Better: precompute two arrays. left_max[i] = max height from 0 to i. right_max[i] = max height from i to n-1. Water at i = min(left_max[i], right_max[i]) - height[i]. O(n) time, O(n) space.
Optimal: two pointers from both ends. Track left_max and right_max as you go. At each step, move the pointer with the smaller max. The key insight: if left_max < right_max, everything to the right of left is at least right_max tall — so left_max is the bottleneck. Water at left = left_max - height[left].
Why the two-pointer invariant works: when height[lo] < height[hi], we know right_max >= height[hi] > height[lo]. So left_max is guaranteed to be the minimum of the two maximums. We can safely calculate water at lo without scanning the right side.
Visual walkthrough for [0,1,0,2,1,0,1,3,2,1,2,1]:
Index: 0 1 2 3 4 5 6 7 8 9 10 11
Height: 0 1 0 2 1 0 1 3 2 1 2 1
- lo=0, hi=11. height[0]=0 < height[11]=1. left_max=0, water=0. lo=1.
- lo=1, hi=11. height[1]=1 < height[11]=1. left_max=1, water=0. lo=2.
- lo=2, hi=11. height[2]=0 < height[11]=1. water += 1-0=1. lo=3.
- lo=3, hi=11. height[3]=2 > height[11]=1. right_max=1, water=1. hi=10.
- lo=3, hi=10. height[3]=2 > height[10]=2. right_max=2, water=1. hi=9.
- lo=3, hi=9. height[3]=2 > height[9]=1. water += 2-1=1. total=2. hi=8.
- lo=3, hi=8. height[3]=2 > height[8]=2. right_max=2, water=2. hi=7.
- lo=3, hi=7. height[3]=2 < height[7]=3. left_max=2, water=2. lo=4.
- lo=4, hi=7. height[4]=1 < height[7]=3. water += 2-1=1. total=3. lo=5.
- lo=5, hi=7. height[5]=0 < height[7]=3. water += 2-0=2. total=5. lo=6.
- lo=6, hi=7. height[6]=1 < height[7]=3. water += 2-1=1. total=6. lo=7.
- lo=7, hi=7. Stop. Result: 6.
Optimal Approach
Two pointers from both ends. Track left_max and right_max.
At each step:
- If
height[lo]<height[hi]:- If height[lo] >= left_max: update left_max- Else: water += left_max - height[lo]- Move lo right
- Else:
- If height[hi] >= right_max: update right_max- Else: water += right_max - height[hi]- Move hi left
The invariant: left_max is always the max height from 0 to lo. right_max is always the max height from hi to n-1. When height[lo] < height[hi], we know right_max >= height[hi] > height[lo], so left_max is the bottleneck for water at lo.
Time: O(n) — single pass. Space: O(1).
What Trips People Up in Real Interviews
Confusing this with "container with most water." This problem asks for total water trapped across the entire array, not the maximum single container.
Trying to calculate water at each position without knowing the max height to the left and right. Pre-compute leftMax and rightMax arrays, or use two pointers.
Forgetting that water at position i = min(leftMax[i], rightMax[i]) - height[i]. If this is negative (height[i] is taller than both maxes), water is 0.
Not handling edge cases: empty array (return 0), single element (return 0), array with no dips (return 0).
Subtracting the bar's height from only one of the two maximums. The correct formula is min(leftMax, rightMax) - height[i]. Using just leftMax or just rightMax overestimates the trapped water.
Solution Code
def trap(height):
lo, hi = 0, len(height) - 1
left_max = right_max = water = 0
while lo < hi:
if height[lo] < height[hi]:
if height[lo] >= left_max:
left_max = height[lo]
else:
water += left_max - height[lo]
lo += 1
else:
if height[hi] >= right_max:
right_max = height[hi]
else:
water += right_max - height[hi]
hi -= 1
return waterFrequently Asked Questions
What is the Trapping Rain Water problem?
Given n non-negative integers representing an elevation map, compute how much water it can trap after raining. This is a classic hard problem that tests your ability to reason about left and right maximums.
How do you solve Trapping Rain Water?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Trapping Rain Water?
Trapping Rain Water is asked at Google, Meta, Amazon, Oracle, Salesforce, OpenAI, Walmart. It is a hard difficulty problem.
What are common mistakes on Trapping Rain Water?
- Confusing this with "container with most water." This problem asks for total water trapped across the entire array, not the maximum single container.
- Trying to calculate water at each position without knowing the max height to the left and right. Pre-compute leftMax and rightMax arrays, or use two pointers.
- Forgetting that water at position i = min(`leftMax[i]`, `rightMax[i]`) - `height[i]`. If this is negative (`height[i]` is taller than both maxes), water is 0.
- Not handling edge cases: empty array (return 0), single element (return 0), array with no dips (return 0).
- Subtracting the bar's height from only one of the two maximums. The correct formula is min(leftMax, rightMax) - `height[i]`. Using just leftMax or just rightMax overestimates the trapped water.