Lemonade Change
Each lemonade costs $5 and customers pay with $5, $10, or $20 bills. Serving them in order, return whether you can give correct change to everyone.
Open on LeetCode ↗Intuition
There is exactly one decision in this problem, and it is where people lose it: giving $15 back for a $20. Three fives works and feels natural. It is wrong. A ten can only ever serve a twenty, while a five serves both tens and twenties — so burning three flexible notes to save a rigid one strands you later. Spend the ten. Everything else here is forced, and a twenty is never change at all, so two counters cover the whole problem.
Greedy with a tie-break that matters: paying out a $20's change prefers a ten-plus-five over three fives, because fives are the more flexible denomination. Spending the least useful bills first is the general principle behind making-change greedies.
Approach
Notice that twenties are dead weight
Change is only ever given in fives and tens, so a $20 bill enters the till and never leaves it. Tracking it would be wasted state; two counters describe everything that matters.
Handle the forced cases
A $5 needs no change — take it and the five count rises. A $10 needs exactly $5 back, and the only way to make that is one five, so there is no choice to make: if no five is available, fail immediately.
Make the greedy choice on $20
A $20 needs $15 back: a ten plus a five, or three fives. Always prefer the ten. The exchange argument: any solution paying with three fives can be rewritten to use the ten instead without getting worse, since the ten has no other use. Hand out the specialised note, hoard the versatile one. Try it on [5,5,5,10,20] — pay the twenty with three fives and the next ten has nothing to draw on. One pass, O(n) time and O(1) space.
Solution & live demo
Common pitfalls
Preferring three fives for a $20
if five >= 3:
five -= 3
elif ten and five:
ten -= 1; five -= 1if ten > 0 and five > 0:
ten -= 1; five -= 1
elif five >= 3:
five -= 3Tens can only ever be used for $20 change, while fives are needed for both $10 and $20. Burning three fives when a ten was available strands the ten and fails a later customer.
Tracking only a running total
cash += b - change
five, ten = 0, 0
Having $15 doesn't mean you can make $15 in change — a single ten and a five is different from three fives. Only the per-denomination counts answer the question.
Counting twenties
twenty += 1
# no counter for twenties
Harmless but pointless: a twenty is never given as change, since no bill exceeds it. Tracking it suggests a use that never comes and hides the fact that only two denominations matter.
Edge cases
The till is empty, so change is impossible and the answer is false on the first step.
No change is ever needed; the answer is true.
The greedy rule prevents this; doing it can strand a later $20 that only a ten could have helped serve.
Handled naturally — the counters simply reach zero at the end.