At a lemonade stand, each lemonade costs $5. Customers are standing in a queue to buy from you and order one at a time (in the order specified by bills). Each customer will only buy one lemonade and pay with either a $5, $10, or $20 bill. You must provide the correct change to each customer so that the net transaction is that the customer pays $5.
Note that you do not have any change in hand at first.
Given an integer array bills where bills[i] is the bill the ith customer pays, return true if you can provide every customer with the correct change, or false otherwise.
Example 1:
Input: bills = [5,5,5,10,20] Output: true Explanation: From the first 3 customers, we collect three $5 bills in order. From the fourth customer, we collect a $10 bill and give back a $5. From the fifth customer, we give a $10 bill and a $5 bill. Since all customers got correct change, we output true.
Example 2:
Input: bills = [5,5,10,10,20] Output: false Explanation: From the first two customers in order, we collect two $5 bills. For the next two customers in order, we collect a $10 bill and give back a $5 bill. For the last customer, we can not give the change of $15 back because we only have two $10 bills. Since not every customer received the correct change, the answer is false.
Constraints:
1 <= bills.length <= 105bills[i] is either 5, 10, or 20.This approach involves using a greedy strategy where we maintain counters for $5 and $10 bills. When a $5 bill is received, simply increase the count. For a $10 bill, check if you have a $5 bill to give as change. For a $20 bill, prefer giving one $10 and one $5 bill as change if available, otherwise give three $5 bills.
The C solution initializes counters for $5 and $10 bills. It iterates over the array and adjusts these counters based on the bill received, ensuring the correct change can be given. The function returns false if change cannot be provided at any point.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the bills array.
Space Complexity: O(1), since only a fixed amount of additional space is used for counters.
This approach focuses on prioritizing the use of $10 bills when giving change to customers with $20 bills. By simulating the process, we ensure that change is handled with a clear order of preference, utilizing available higher denominations first.
The solution processes each bill, adjusting the count of $5 and $10 bills and preferring to give back a $10 bill when changing for a $20 bill. It returns false if it can't make the correct change.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the size of the bills array.
Space Complexity: O(1), using only fixed space for counters.
| Approach | Complexity |
|---|---|
| Greedy with Bill Counting | Time Complexity: O(n), where n is the length of the bills array. |
| Simulation with Priority Change Strategy | Time Complexity: O(n), where n is the size of the bills array. |
L2. Lemonade Change | Greedy Algorithm Playlist • take U forward • 70,660 views views
Watch 9 more video solutions →Practice Lemonade Change with our built-in code editor and test cases.
Practice on FleetCode