Lemonade Change
Easy· Simulation
Problem
Lemonade costs $5 and customers arrive in order, each paying with a $5, $10 or $20 bill. You start with no change. Return true if you can give every customer correct change.
Examples
Input: bills = [5,5,5,10,20]
Output: true
Input: bills = [5,5,10,10,20]
Output: false
By the last customer you hold two $10 bills and no $5, so you cannot make $15.
Constraints
- • 1 <= bills.length <= 10^5
- • bills[i] is 5, 10 or 20
Hints & approach
Hint 1
You only ever need to track how many $5 and $10 bills you hold.
Hint 2
For a $20, you can give $10 + $5 or three $5 bills. Which one keeps you more flexible?
Approachtry the hints first
Count $5 and $10 bills. A $5 needs no change. A $10 needs one $5. For a $20, prefer giving one $10 and one $5, and fall back to three $5 bills; $5 bills are the more versatile change, so spending a $10 first is always at least as good. If a required bill is missing at any point, return false.
Time O(n) · Space O(1)