Determine whether you can provide correct change to every customer in order as they buy lemonade with $5, $10, or $20 bills.
Lemonade Change
You are running a lemonade stand where each lemonade costs $5. Customers arrive one by one in the given order. Each customer pays with a bill of value 5, 10, or 20.
For each customer, you must provide exact change immediately if needed:
- A $5 bill requires no change.
- A $10 bill requires one $5 bill as change.
- A $20 bill requires $15 change, which can be given as either:
- one $10 bill and one $5 bill, or
- three $5 bills.
You start with no money. Return whether it is possible to serve every customer in order without ever failing to make change.
Notes
- You may only use bills collected from earlier customers.
- The order of customers cannot be changed.
- You do not need to minimize leftover bills; only determine feasibility.
Input Format
- A list of customer payments
bills, where each element is one of{5, 10, 20}. bills[i]is the bill paid by thei-th customer in arrival order.
Output Format
- Return
trueif exact change can be given to every customer in order. - Otherwise, return
false.
Constraints
- Each
bills[i]is one of5,10, or20. - You start with no cash on hand.
- The answer must be determined in a single left-to-right pass in typical optimal solutions.
Example 1
Input
bills = [5, 5, 5, 10, 20]
Output
true
Explanation
Collect three $5 bills, use one $5 bill as change for the $10 payment, then use one $10 and one $5 as change for the $20 payment.
Example 2
Input
bills = [5, 5, 10, 10, 20]
Output
false
Explanation
After serving the first four customers, you have two $5 bills and two $10 bills. The final $20 payment needs $15 change, but you do not have enough $5 bills to give change.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.