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.
- 1 <= bills.length <= 10⁵
- bills[i] is either 5, 10, or 20.
Intuition
Lemonade change simulates a queue of customers paying with $5, $10, or $20 bills for a $5 drink. Each customer must receive correct change immediately, using only bills already collected. The only case requiring a decision is a $20 payment, which needs $15 in change. Two combinations work — one $10 and one $5, or three $5 bills — and choosing between them is the entire problem: - Always prefer giving one $10 and one $5, because $5 bills are strictly more useful than $10s. The reasoning is what makes this greedy provably correct. A $5 bill can settle change for both a $10 payment and a $20; a $10 bill is only ever useful for a $20. So spending the less flexible bill first preserves options, and hoarding $10s can never help. A $5 payment needs no change and simply increases the $5 count. A $10 payment requires one $5, and there is no alternative to consider. Only two counters are needed. $20 bills are never given as change, so counting them serves no purpose — tracking them is harmless but pointless. When neither combination is available for a $20, the answer is false immediately; no later customer can retroactively supply the missing change. The order of the fallback matters: try the $10-plus-$5 combination first, and only fall back to three $5s. Reversing that check exhausts the flexible bills early and fails on inputs the greedy should handle.
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
Before reading on: price up what the direct approach costs here, then ask why the locally best choice is safe to commit to and never revisit. Aim for O(n) time and O(1) space.
Identify the only real decision
$5 and $10 payments have exactly one possible response. Only a $20 payment offers a choice, between one $10 plus one $5, or three $5 bills.
Prefer the ten-plus-five combination
Give the $10 first. A $5 bill can make change for both $10 and $20 payments, while a $10 is only useful for a $20 — spending the less flexible bill preserves options.
Handle the simple payments
A $5 needs no change and increments the count. A $10 consumes one $5, with no alternative to weigh.
Track only two counts
$20 bills are never given as change, so counting them serves no purpose. Two counters describe the entire state.
Order the fallback correctly
Check the $10-plus-$5 option before three $5s. Reversing the order drains the flexible bills early and fails inputs the greedy should handle.
Fail immediately when stuck
If neither combination is available for a $20, return false at once — no later customer can supply the change retroactively.
Cost of the simulation
One pass with constant work per customer gives O(n) time and O(1) space, using two integer counters.
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.