#860
Lemonade Change
Easy Greedy change-making
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Lemonade costs $5. Customers pay with $5, $10 or $20 bills in order, and you start with no change. Decide whether you can give everyone correct change.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: can you give correct change to every customer, in order?
Why this works: for a $20, prefer $10 + $5 over three $5s; $5 bills are more useful later.
Example: [5, 5, 10, 10, 20]
5, 5 → two fives10 → give 5 (one five left)10 → give 5 (no fives)20 → no change possible → false
✦Hints open one at a time
Track how many $5 and $10 bills you hold.
For a $20, prefer giving $10 + $5 over three $5s — $5 bills are more flexible.
↗Approach
Simulate. $5: keep it. $10: needs one $5. $20: use a $10 and a $5 if possible, else three $5s. Fail if neither works.
</>Solution (Java)
class Solution {
public boolean lemonadeChange(int[] bills) {
int five = 0, ten = 0;
for (int b : bills) {
if (b == 5) five++;
else if (b == 10) {
if (five == 0) return false;
five--;
ten++;
} else {
if (ten > 0 && five > 0) { ten--; five--; } // keep $5s when possible
else if (five >= 3) five -= 3;
else return false;
}
}
return true;
}
}!Common mistake
Paying a $20 with three $5s first, which runs out of $5s too early.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Greedy
🎬 Episodes 69–73: video coming soon