Customers pay $5, $10, or $20 for $5 lemonade. Determine if you can give everyone correct change.
Input: bills=[5,5,5,10,20] → Output: true
Input: bills=[5,5,10,10,20] → Output: false
Track $5 and $10 bills. For $20, prefer to give $10+$5 change before $5+$5+$5.
- Keep count of fives and tens
- For $5 bill: fives++
- For $10 bill: need one $5 (fives--), tens++
- For $20 bill: prefer tens+fives, else 3*fives
- If any count < 0 return false
public boolean lemonadeChange(int[] bills) {
int fives = 0, tens = 0;
for (int bill : bills) {
if (bill == 5) fives++;
else if (bill == 10) {
if (fives == 0) return false;
fives--; tens++;
} else {
if (tens > 0 && fives > 0) { tens--; fives--; }
else if (fives >= 3) fives -= 3;
else return false;
}
}
return true;
}
- Time Complexity: O(n)
- Space Complexity: O(1)