Given the queue of bills customers pay for a 5-dollar lemonade, the machine must decide whether it can make exact change for every customer in order. Only 5, 10, and 20 dollar bills appear, and no change is needed for a 5. The machine starts with no money.
The key insight is that bills have a strict preference hierarchy: a 10 is only useful for making change on a 20, while a 5 is useful for both a 10 and a 20. When a 20 arrives, the machine should hand back one 10 and one 5 instead of three 5s, because fives are the scarcer, more flexible resource.
The approach runs in three steps. First, track counts of 5s and 10s, starting both at zero. Second, walk the queue: a 5 just increases the five count; a 10 requires a 5 to return and then becomes a 10; a 20 requires either one 10 plus one 5, or three 5s. Third, return false the moment any customer cannot be given exact change, and true if the walk completes. Time is O(n) and space is O(1).
The trickiest edge case is the order trap: [5,5,10,10,20] fails only because the machine burned its fives on the two 10s, leaving no five to pair with a ten. Hoarding fives is exactly what the "prefer 10 + 5" rule accomplishes, and it is what separates this greedy from a naive bill count.
def lemonadeChange(bills):
five = ten = 0
for bill in bills:
if bill == 5:
five += 1
elif bill == 10:
if five == 0:
return False
five -= 1
ten += 1
else:
if ten and five:
ten -= 1
five -= 1
elif five >= 3:
five -= 3
else:
return False
return True