Trapping Rain Water

def trap(height):
    n = len(height)
    water = 0
    for i in range(n):
        # The tallest bar at or left of i, and the tallest at or right of i.
        left_max = 0
        for j in range(i + 1):
            left_max = max(left_max, height[j])
        right_max = 0
        for j in range(i, n):
            right_max = max(right_max, height[j])
        water += min(left_max, right_max) - height[i]
    return water

def trap(height):
    n = len(height)
    left_max = [0] * n   # tallest bar from index 0 to i
    right_max = [0] * n  # tallest bar from index i to n-1
    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i - 1], height[i])
    right_max[n - 1] = height[n - 1]
    for i in range(n - 2, -1, -1):
        right_max[i] = max(right_max[i + 1], height[i])
    water = 0
    for i in range(n):
        water += min(left_max[i], right_max[i]) - height[i]
    return water

def trap(height):
    left, right = 0, len(height) - 1
    left_max = right_max = 0  # tallest bar passed so far from each end
    water = 0
    while left < right:
        if height[left] < height[right]:
            # A bar taller than height[left] waits on the right, so left_max sets the level here.
            left_max = max(left_max, height[left])
            water += left_max - height[left]
            left += 1
        else:
            # A bar at least as tall as height[right] waits on the left, so right_max sets the level.
            right_max = max(right_max, height[right])
            water += right_max - height[right]
            right -= 1
    return water