The problem
Each number is the height of a building in a row (all width 1). After rain, water collects in the dips between buildings. Compute how much water is trapped in total.
Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6
Picture it
Picture the buildings and the blue water pooled between them. Water above any spot can only rise as high as the shorter of the tallest wall to its left and the tallest wall to its right, minus the building’s own height. Two walkers come in from both ends, each remembering the tallest wall they’ve passed. Whichever side has the lower wall is the limiting side, so that walker can settle the water at its spot and step inward.
How to recognise it
- The answer is a total over every position, and each position's share depends on what lies on both sides of it.
- The water above a bar is decided by the tallest bar to its left and the tallest bar to its right: it fills to the lower of the two.
- "Tallest to the left" and "tallest to the right" are running maxima, which you can build from each end.
- n is up to 2 × 10^4, so rescanning both sides for every bar is too slow.
Start with brute force
For each bar, find the tallest bar on each side (including itself). The water level there is the smaller of the two, so add that level minus the bar's own height.
def trap_brute(h):
water = 0
for i in range(len(h)):
left = max(h[:i + 1]) # tallest at or left of i
right = max(h[i:]) # tallest at or right of i
water += min(left, right) - h[i]
return water
Each bar scans the whole list, so time is O(n²). With n = 2 × 10^4 that is about 4 × 10^8 reads, too slow in Python. The slices also copy, so each step uses O(n) temporary space.
From brute force to the idea
- Find the waste. The tallest bar to the left of i + 1 is just the tallest to the left of i, compared with one more bar. Rescanning repeats that work.
- Precompute both sides. Two arrays of running maxima, one from the left and one from the right, give an O(n) solution with O(n) space.
- Notice you only need the lower side. Water at a bar depends on min(left max, right max). If you know which side is lower, the other side's exact value does not matter.
- Let two pointers decide. Keep
landrat both ends withleft_maxandright_max. Ifh[l] < h[r], then every bar the left pointer has passed was lower than some bar still on the right, soleft_maxis the lower side for position l. Settle l's water withleft_maxand move l. Otherwise settle r the same way from the right. - Update the max first.
left_max = max(left_max, h[l])comes before adding water, so a bar that is a new maximum adds 0, never a negative amount.
This is the key idea: the lower of the two side maxima decides the water, and moving the pointer at the lower bar always settles a position correctly.
The key idea
Water at i = min(maxLeft, maxRight) − height[i]. Two pointers know which side is the limit, so one pass with O(1) memory.
Python solution
def trap(h):
l, r = 0, len(h) - 1
left_max = right_max = water = 0
while l < r:
if h[l] < h[r]:
left_max = max(left_max, h[l])
water += left_max - h[l]
l += 1
else:
right_max = max(right_max, h[r])
water += right_max - h[r]
r -= 1
return waterIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²): each bar rescans both sides | O(n): the temporary slices |
| Two pointers (shown code) | O(n): one pointer moves inwards on each step | O(1): two pointers and two maxima |
Edge cases
- Empty list or one bar: returns 0; with
r = len(h) - 1, the loop never runs or ends at once. - Rising or falling only (
[1, 2, 3, 4],[4, 3, 2, 1]): returns 0; there is no wall on one side. - Simple valley (
[3, 0, 3]): returns 3. - Flat (
[2, 2, 2]): returns 0. - The last bar is never settled: the loop stops when
l == r. That is fine, because the pointers meet at a tallest bar, which holds no water. - The example (
[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]): returns 6.
Common mistakes
- Adding
left_max - h[l]before updatingleft_max. A new tallest bar then adds a negative amount:[1, 2, 3, 4]returns −3. - Moving the pointer at the taller bar. Then the settled side is not guaranteed to be the lower one, so water is overcounted on some inputs and undercounted on others.
- Using
max(left, right)instead ofmin, as if water could stand higher than the lower wall. - Confusing this with Container With Most Water, which picks one pair of walls instead of adding up every position.
Return a list with how much water stands above each bar, instead of the total. For [3, 0, 2, 0, 4] the answer is [0, 3, 1, 3, 0]. Describe your approach, then write it if you like.
Compare with our answer
Use the same two pointers. Each step settles exactly one position, so write its amount into a list instead of adding it to a total. The position where the pointers meet is never written and stays 0, which is correct for a tallest bar.
def water_per_position(h):
out = [0] * len(h)
l, r = 0, len(h) - 1
left_max = right_max = 0
while l < r:
if h[l] < h[r]:
left_max = max(left_max, h[l])
out[l] = left_max - h[l]
l += 1
else:
right_max = max(right_max, h[r])
out[r] = right_max - h[r]
r -= 1
return out
Its sum always equals trap(h). Time O(n), and O(n) space for the answer.
A strong answer mentions: that each step settles exactly one position, why the meeting point holds 0, and that the sum matches the original.
1. For every building in a row you must report the height of the tallest building somewhere to its right. Which approach fits best?
A one-sided question needs one running maximum built from that side: O(n). Two pointers are needed only when a position depends on both sides at once. Rescanning is O(n²).
2. When h[l] < h[r], why is the water at position l exactly left_max - h[l]?
Every bar the left pointer passed was lower than a bar still on the right, and h[r] beats h[l], so the right side is never the lower wall. The level at l is therefore left_max. Nothing is known about the bars in between.
3. A learner adds water += left_max - h[l] before updating left_max, leaving the right side as it is. Which input now gives a wrong total?
Each new taller bar on the left adds left_max - h[l] with the old, smaller maximum, which is negative: the total becomes −3. In the other inputs the left pointer never reaches a bar taller than the earlier left maximum (or, in [3, 0, 3] and [2, 0, 2], stays on the first bar while r walks in), so the bug never fires.
Score 60% or more and the lesson is marked complete.