Trapping Rain Water
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Given bar heights, compute how much rainwater is trapped between the bars.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1For one bar, what limits the water level above it?
- Hint 2You need the tallest bar to its left and to its right. Can two pointers give you that without extra lists?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
It rains on a skyline of buildings. A puddle forms above a building only if there is a taller building somewhere on both sides. The puddle's depth is the height of the SHORTER of those two tallest neighbours, minus your own roof. Two watchers walk in from the two ends of the street, each remembering the tallest building they have passed. Whichever watcher stands on the lower side can calculate their puddle straight away.
- The obvious way
For each bar scan to the left and to the right for the tallest: O(n²).
- The key insight
Water at a bar = min(tallest on the left, tallest on the right) - its height. Walk two pointers inward. If the left bar is lower than the right bar, the left side's tallest alone decides its puddle (the right side is at least as tall), so settle the left bar and step in. Otherwise settle the right bar. No lists needed.
- The algorithm
- Left watcher at the first bar, right watcher at the last. Both tallest-seen start at 0. Water = 0.
- Whichever of the two bars is lower, that watcher works.
- He updates his tallest-seen, adds (tallest-seen minus this bar) to the water, and steps inward.
- Repeat until they meet.
Watch it run
Exampleheights = [0,1,0,2,1,0,1,3,2,1,2,1]
Left bar 0 is lower than right bar 1: the left watcher works. Tallest seen 0, adds 0.
water 0
Where people slip
- Update the tallest-seen BEFORE adding water, so the water is never negative.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def trap(heights):
left, right = 0, len(heights) - 1
tallest_left = tallest_right = 0
water = 0
while left < right:
if heights[left] < heights[right]: # left side decides
tallest_left = max(tallest_left, heights[left])
water += tallest_left - heights[left]
left += 1
else: # right side decides
tallest_right = max(tallest_right, heights[right])
water += tallest_right - heights[right]
right -= 1
return waterNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.