Trapping Rain Water

You'll find how much water sits above each bar, then use two pointers to get every answer in one pass with no extra lists. You need running maximums and pointers that move inward. Related chapter: two pointers.

1. The problem

You get a row of bars, each one unit wide, with heights that are integers of zero or more. After it rains, water collects between them. Return the total units of water held. Don't change the heights. This is LeetCode 42. An empty list returns 0.

Water over a bar can rise only as high as the shorter of two walls: the tallest bar on its left and the tallest on its right. In [3,0,2,0,4], the bar at index 1 has 3 on its left and 4 on its right. So water rises to 3 there, holding 3 units.

2. A correct baseline

def baseline(height):
    water=0
    for i in range(len(height)):
        left=max(height[:i+1])
        right=max(height[i:])
        water+=min(left,right)-height[i]
    return water

assert baseline([3,0,2,0,4])==7
assert baseline([0,1,2])==0
assert baseline([2,0,2])==2

For each bar, this scans everything to its left and right. That's O(n²) time: the work grows with the square of the number of bars. On 100,000 bars, that's ten billion steps. The slices also take O(n) temporary space.

The bottleneck. Neighboring bars rescan almost the same ranges to find the same tallest walls.

3. The observation

One fix is two lists: the tallest bar so far from the left, and from the right. That removes the rescanning, but takes O(n) space. We can do better with two pointers, one at each end. Each keeps the tallest wall it has seen on its side.

Take [3,0,2,0,4]. After reading both ends, the left wall is 3 and the right wall is 4. Look at index 1. Its left wall is exactly 3. Its right wall is at least 4, because we've already seen a 4 on that side. The shorter wall decides the water, and that's the left one: 3. Bars we haven't seen can't change it.

So always move the pointer on the side whose known wall is shorter. Its water level is already settled, even before you see the middle.

4. The solution and a trace

class Solution:
    def trap(self, height: list[int]) -> int:
        """Unit-width nonnegative bars; return trapped units without mutation."""
        left,right=0,len(height)-1
        left_max=right_max=0
        water=0
        while left<=right:
            if left_max<=right_max:
                left_max=max(left_max,height[left])
                water+=left_max-height[left]
                left+=1
            else:
                right_max=max(right_max,height[right])
                water+=right_max-height[right]
                right-=1
        return water

solve=Solution().trap
assert solve([3,0,2,0,4])==7
assert solve([0,1,2])==0
assert solve([2,0,2])==2
assert solve([])==0

Trace [3,0,2,0,4]:

5. Why it works

What stays true. Every bar outside the two pointers has had its water counted exactly once, and correctly.

Each bar we count is right. Say left_max <= right_max. Then we already know a wall on the right at least left_max tall. So the shorter wall for the bar at left is its left wall, left_max. If that bar is shorter than left_max, the water above it is left_max minus its height. If it's taller, it becomes the new left_max and holds no water. The right side works the same way.

Every bar gets counted. Each step settles one bar and moves one pointer inward, until the pointers cross.

6. Cost, edge cases, and failure

Cost. Each bar is settled once: O(n) time, growing in step with the number of bars. O(1) extra space.

Edge cases. When the two walls are equal, either side can move. Flat, rising, and falling rows hold no water. Starting both walls at zero works because no height is negative.

Where it fails. Using only the tallest wall overall ignores the shorter side:

height=[3,0,1]
assert max(height)-height[1]==3  # Deliberately wrong water depth using one global wall.
assert solve(height)==1

import random,itertools
rng=random.Random(42)
for _ in range(1000):
    height=[rng.randint(0,10) for _ in range(rng.randrange(30))]
    before=height.copy()
    assert solve(height)==baseline(height)
    assert height==before
for n in range(7):
    for height in itertools.product(range(3),repeat=n):
        assert solve(list(height))==baseline(list(height))