Practice: Trapping Rain Water
Water between the walls.
After rain, water collects between walls of different heights. How much water is trapped in total? This is a famous hard problem. Pause, and think about one single position. How high can water rise there?

- Water collects between walls
- How much in total?
- Think about one position
Two pointers, tracking the tallest
Water above a position rises to the shorter of the tallest wall on its left, and the tallest wall on its right. With two pointers, we move in from whichever side has the shorter tallest wall, because that side decides the water level. Each step adds the water above that position. Run it. Six units of water are trapped.
def trap(heights):
left, right = 0, len(heights) - 1
left_max = right_max = water = 0
while left < right:
if heights[left] < heights[right]:
left_max = max(left_max, heights[left])
water += left_max - heights[left]
left += 1
else:
right_max = max(right_max, heights[right])
water += right_max - heights[right]
right -= 1
return water
print(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))6
Hard problems, simple pieces
Hard problems are usually simple ideas combined. Here, it's two pointers, plus tracking a maximum. Start by asking what decides the answer at one position. Then find a way to know that quickly for every position. That question cracks many hard problems.
| key | value |
|---|---|
| At one spot | min(tallest left, tallest right) |
| Two pointers | move the smaller side |
| Add | level − height |
| Cost | O(n), O(1) space |
Summary
Water at each spot depends on the shorter of the tallest walls on each side. Two pointers solve it in O of N. Next, interview problems about trees and lists.
Key takeaways- Tallest on each side
- Move the smaller side
- O(n)