Trapping Rain Water

Hard#42towards each other

You get the heights of bars that stand side by side, each one unit wide. Rain falls on them: how much water stays between the bars? Our example: heights [3, 0, 1, 4, 0, 2, 1, 3] — 11 units of water.

42 Trapping Rain WaterWalkthrough · 1×

Example: heights [3, 0, 1, 4, 0, 2, 1, 3]. Blue is the water counted so far; the dashed lines are leftMax and rightMax, the highest bar seen from each end.

3014021301234567left
not reached yetunder a pointerwater over it counted

left starts at the first bar, 3 high

01/54
restart · back · play · step
Speed
1function trap(height):
2 left = 0
3 right = len(height) - 1
4 leftMax = 0; rightMax = 0
5 water = 0
6 while left <= right:
7 leftMax = max(leftMax, height[left])
8 rightMax = max(rightMax, height[right])
9 if leftMax <= rightMax:
10 water = water + leftMax - height[left]
11 left = left + 1
12 else:
13 water = water + rightMax - height[right]
14 right = right - 1
15 return water
state
left
0
right
–
leftMax
–
rightMax
–
water
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Water over a bar rises to the lower of two walls: the highest bar on its left and the highest bar on its right. Any higher and it spills over the lower one.
  2. If leftMax ≤ rightMax, the right side already has a wall at least leftMax high, and the real highest bar on the right can only be higher. So the water over left is leftMax minus its height, whatever stands between the pointers. The right side works the same way, mirrored.
  3. That is why the side with the lower max moves: the water over its bar is already known for sure, and each step settles one bar for good.

Complexity

Time O(n): each step settles one bar and moves one pointer, so there are n steps. Memory O(1): two pointers, two maxes and the sum, with no arrays of maxes for every bar.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.