twitter water fill problem, solution to problem described here https://medium.com/@bearsandsharks/i-failed-a-twitter-interview-52062fbb534b

twitter_water.py

def water_collected(A):
    sortedHeights = [(x,i) for i,x in enumerate(A)]
    sortedHeights.sort(key=lambda v: v[0]*-1) #sort in decreasing order
    
    leftIdx = rightIdx = sortedHeights[0][1]
    waterLevel = 0
    for i in xrange(1,len(A)):
        x,idx = sortedHeights[i]
        if idx > rightIdx:
            water = (idx-rightIdx-1)*x
            rightIdx = idx
        elif idx < leftIdx:
            water = (leftIdx-idx-1)*x
            leftIdx = idx 
        else:
            water = -x
        waterLevel += water
    return waterLevel
            
assert water_collected([2, 5, 1, 2, 3, 4, 7, 7, 6])  == 10
assert water_collected([2, 5, 1, 3, 1, 2, 1, 7, 7, 6])  == 17
assert water_collected([2, 7, 2, 7, 4, 7, 1, 7, 3, 7])  == 18
assert water_collected([6, 7, 7, 4, 3, 2, 1, 5, 2])  == 10
assert water_collected([2, 5, 1, 2, 3, 4, 7, 7, 6, 2, 7, 1, 2, 3, 4, 5, 5, 4])  == 26       
assert water_collected( [2, 5, 1, 2, 3, 4, 7, 5, 6]) == 11

n log(n) solution with o(n) space, but simple solution