In [68]:

    

def answer0(heights):
    """returns the units of water collected given heights of hutches"""
    hlen = len(heights)
    if hlen < 2:
        return 0
    
    water_filled = 0
    max_left = 0
    max_right = max(heights)
    for i in range(hlen):
        if heights[i] == max_right and i+1 < hlen:
            max_right = max(heights[i+1:])
        min_wall = min((max_left, max_right))
        if min_wall > heights[i]:
            water_filled += min_wall - heights[i]
        if heights[i] > max_left:
            max_left = heights[i]
    
    return water_filled


    

In [65]:

    

def answer(heights):
    """returns the units of water collected given heights of hutches"""
    hlen = len(heights)
    if hlen < 2:
        return 0

    max_right = 0
    change_list = []
    for i in range(hlen-1, -1, -1):
        if heights[i] > max_right:
            max_right = heights[i]
            type(change_list.insert( 0, heights[i] ))

    max_right = change_list.pop(0)
    max_left = 0
    water_filled = 0
    for i in range(hlen-1):
        if heights[i] == max_right and i+1 < hlen:
             max_right = change_list.pop(0)
        min_wall = min((max_left, max_right))
        if min_wall > heights[i]:
            water_filled += min_wall - heights[i]
        if heights[i] > max_left:
            max_left = heights[i]

    return water_filled


    

In [66]:

    

heights1 = [1, 4, 2, 5, 1, 2, 3]
print(answer(heights1))


    

    




5

In [23]:

    

heights2 = [1, 2, 3, 2, 1]
print(answer(heights2))


    

    




0

In [24]:

    

from timeit import timeit
import random


    

In [36]:

    

def test_rand(num_hutches):
    rand_heights = []
    for i in range(num_hutches):
        rand_heights.append(random.randint(0, num_hutches))
    #%timeit answer(rand_heights)
    #print(answer(rand_heights))
    return rand_heights


    

In [67]:

    

%timeit answer(heights1)


    

    




100000 loops, best of 3: 7.31 µs per loop

In [69]:

    

%timeit answer0(heights1)


    

    




The slowest run took 4.06 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 6.05 µs per loop

In [71]:

    

rand_heights = test_rand(9000)

%timeit answer0(rand_heights)
%timeit answer(rand_heights)


    

    




100 loops, best of 3: 6.54 ms per loop
100 loops, best of 3: 7.09 ms per loop

In [ ]:

    

#print(min_wall)

#print(max(heights2[5:]))