Lemonade Change
Easy · Greedy · Array · Greedy
Problem
You run a lemonade stand where each cup costs $5. Customers arrive one at a time in the order of bills; each buys exactly one cup and pays with a $5, $10 or $20 bill.
The till starts empty, and you must give every customer exact change (so each pays $5 net), using only bills received from earlier customers.
Return true if you can give every customer correct change, otherwise false.
Examples
Input: bills = [5,5,10,20] Output: true
The $10 customer gets a $5 back; the $20 customer gets the $10 and a $5.
Input: bills = [10,5] Output: false
The first customer needs $5 in change, but there is no money yet.
Input: bills = [5,5,5,20,20] Output: false
The first $20 takes all three $5 bills, leaving nothing for the second.
Constraints
- 1 <= len(bills) <= 10^5
- bills[i] is 5, 10 or 20
Approaches
- Track every possible till — time O(n · S), S = tills kept, space O(S)
Follow-up
What if the cup cost a different amount, or bills came in arbitrary denominations? Then "spend the largest bill first" can fail (it is the general change-making problem), and you would need a search over reachable tills like the baseline below. The fixed 5/10/20 setup is what makes the greedy exact.
Related problems
Start free on Cariara · Coding problems · System design studio
