Archived

Trapping Rain Water

An old note — I haven't updated it since I wrote it.

1def trap(height):
2    l, r, level, water = 0, len(height)-1, 0, 0
3    while l < r:
4        lev_i, l, r = (l, l+1, r) if height[l] < height[r] else (r, l, r-1)
5        level = max(level, height[lev_i])
6        water += level - height[lev_i]
7    return water
8
9print(trap([0,1,0,2,1,0,1,3,2,1,2,1]))