Scamming the coding interview: Problem 010: Rain water trapped

rain_water_trapped.py

"""
Scamming the coding interview
"""


def calculate_rain_water_trapped(bars):

    n = len(bars)
    left = [0 for i in range(0, n)]
    
    # find and store the highest bar on the left for all the elements
    left[0] = bars[0]
    for i in range(1, n):
        max_so_far = max(bars[i], left[i-1])
        left[i] = max_so_far

    # find and store the highest bar on the right for all the elements
    right = [0 for i in range(0, n)]
    right[n-1] = bars[n-1]
    for i in range(2, n+1):
        max_so_far = max(right[n-i+1], bars[n-i])
        right[n-i] = max_so_far

    # calculate the water units stored at each element
    water = 0
    for i in range(0, n):
        temp_water = min(left[i], right[i]) - bars[i]
        water += temp_water

    return water


if __name__ == '__main__':

    bars = [3, 0, 0, 2, 0, 4]

    water = calculate_rain_water_trapped(bars)

    print(water)