Lemonade Change
An easy Greedy interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Greedy
- Sheets
- 1
- Core for
- 3 roles
The problem
You are working at a lemonade stand where each lemonade costs 5 dollars. Customers are standing in a queue and each buys exactly one lemonade. They pay with 5, 10, or 20 dollar bills. You start with no change. Return true if you can provide correct change to every customer.
Example 1
- Input
- bills = [5,5,5,20]
- Output
- true
- Why
- The three 5s cover the change for the 20.
Example 2
- Input
- bills = [5,10,5,10,20]
- Output
- false
- Why
- 5: keep. 10: give 5. 5: keep. 10: give 5 (now zero 5s). 20: need 15 but no 5s left.
Constraints
- 1 <= bills.length <= 10^5
- bills[i] is 5, 10, or 20
How to think about it
Updated 2026-09-29A 5-dollar bill is universal change, capable of breaking both 10 and 20 dollar payments, whereas a 10-dollar bill can only help break a 20. When making fifteen dollars in change, always surrender the less flexible 10-dollar bill first to hoard your 5-dollar bills.
Approaches, worst first
Recursive search on bill combinations
time O(2^n) · space O(n)
Explore combinations of bills to give as change for every transaction. Pointless overhead because greedy bill substitution is provably optimal.
Greedy register counterWrite this one
time O(n) · space O(1)
Maintain counts of available 5s and 10s (20s can never be used as change). On receiving 10, give a 5. On receiving 20, give a 10 and a 5 if available, otherwise three 5s. If counts drop below zero, return false immediately.
Where people lose marks · 3
- Giving three 5-dollar bills when a 10 and a 5 could have been given depletes 5-dollar bills prematurely, causing later 10-dollar customers to fail.
- Tracking twenty-dollar bills in your change inventory: 20-dollar bills can never be returned as change for any lemonade purchase.
- Decrementing bill counts before verifying availability can leave negative numbers in variables if not guarded cleanly.
The theory behind it
Greedy — the ground this problem stands on. All Greedy problems
What Greedy is
A greedy algorithm makes the best-looking choice available right now, at every step, without ever looking back or second-guessing its decision. Think of a cashier making change by handing over the largest possible coin first, repeatedly, until the total is reached. Unlike dynamic programming, which saves and compares answers to multiple overlapping paths, a greedy strategy commits to one immediate option and keeps moving forward.
When to reach for it
Reach for greedy when problems ask for minimum jumps, interval scheduling, assigning resources to maximize satisfaction, or finding fractional values. Key signals include sorted orders where greedily taking the next item never hurts future options, or gas station round trips where running balances prove reachability. If you can prove that taking the immediate best choice never leaves you worse off than any alternative, greedy gives the fastest answer.
How the pattern works
Start by sorting the input to bring the most promising candidates to the front. At each position, evaluate your local rule, take the best available piece, and update your running state. The crucial mental step is proving the greedy choice property: demonstrate that picking this immediate winner cannot block a better global solution down the road. If choosing an item now forces you to reconsider past decisions when conditions change later, greedy fails and you must switch to dynamic programming instead.
More Greedy problems
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .