Twitter Interview Solution Problem described here: http://qandwhat.apps.runkite.com/i-failed-a-twitter-interview/ It's messy, but it solves it in one pass

puddle.py

def puddle(xs):
	result = 0
	unresolved = []
	for i in range(len(xs)):
		y = xs[i]
		if len(unresolved) > 0:
			while y > unresolved[-1][0]:
				z = unresolved.pop()[0]
				if len(unresolved) == 0:
					break
				g, j = unresolved[-1]
				g = min(g, y)
				result += (g-z) * (i-j-1)
			if len(unresolved) == 0:
				unresolved.append((y, i))
				continue
			if y <= unresolved[-1][0]:
				unresolved.append((y, i))
		else:
			unresolved.append((y, i))
	return result
 
 
 
a = [2,5,1,3,1,2,1,7,7,6]
b = [2,5,1,2,3,4,7,7,6]
c = [2,4,1,1,2,1,5,4,3,5,4]
 
print puddle(a) # 17
print puddle(b) # 10
b.reverse()
print puddle(b) # also 10!
print puddle(c) # 14 (2 puddles)

This breaks if you reverse the order of the elements:

print puddle([2,5,1,2,3,4,7,7,6]) → 10
print puddle([6,7,7,4,3,2,1,5,2]) → 11

AH! Good catch! It was an errant < vs <= bug that caused it to not add unresolved walls of the same height back-to-back. (Hopefully) fixed now!