Trapping rain water
Filed under Amazon · Also reported at Accolite, Adobe, Brane Enterprises, CarTrade Tech Limited, CarWale, Celigo, Cloud Lending, Dell and 27 more
Free read 1 of 3Bars have width 1, heights are non-negative integers, and water above a bar equals min(left max, right max) minus its height when positive.
The question
Given n non-negative integers representing an elevation map where each bar has width 1, compute how much rain water it can trap.
Constraints
- 1 <= n <= 2 * 10^4
- 0 <= height[i] <= 10^5
Examples
- Input
- [0,1,0,2,1,0,1,3,2,1,2,1]
- Output
- 6
- Why
- Six units of water collect between the taller bars.
- Input
- [4,2,0,3,2,5]
- Output
- 9
- Why
- Water fills the valleys between the bars of height 4 and 5.
Approach
Bars have width 1, heights are non-negative integers, and water above a bar equals min(left max, right max) minus its height when positive.
For each index scan left and right for the highest bars: O(n^2) time, O(1) space.
Precompute left-max and right-max arrays for O(n) time and O(n) space, or use two pointers moving inward: handle the side with the smaller max, since that side's water level is already determined.
Fewer than three bars trap nothing, monotonic increasing or decreasing heights trap nothing, and flat plateaus. Final complexity O(n) time, O(1) space.
Solution
O(n) time, O(1) space
class Solution:
def trap(self, height):
l, r = 0, len(height) - 1
lmax = rmax = water = 0
while l < r:
if height[l] < height[r]: # left side is the limiting side
lmax = max(lmax, height[l])
water += lmax - height[l]
l += 1
else:
rmax = max(rmax, height[r])
water += rmax - height[r]
r -= 1
return water
Tips
- What they are testing: Whether you can reduce a per-index formula to a single pass with two pointers.
- Common mistake: Using the global maximum on both sides or forgetting that water at a bar depends on the smaller of the two side maxima.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.