Lemonade Change
Problem Statement
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 of bills where of is the bill the ith customer pays, return true if you can provide every customer with the correct change, or false otherwise.
Examples:
Input: bills = [5,5,5,10,20]
Output: true
Explanation:
From the first three customers, we collect three $5 bills in sequence.
From the fourth customer, we collect a $10 bill and give back a $5 bill as change.
From the fifth customer, we collect a $20 bill and give back both a $10 bill and a $5 bill as change.
Since all customers received the correct change, we output true.
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 <= 10⁵
bills[i] is either 5, 10, or 20.
Approach
When we read the problem statement, we understand that it is about simulating transactions at a lemonade stand.
Customers pay with $5, $10, or $20 bills, and the goal is to provide the correct change for each transaction while keeping track of the available cash on hand. Since you start with no money, it is crucial to carefully manage the cash flow during each transaction to ensure that you can always provide the required change.
If a customer pays with a $5 bill, no change is required, and you simply increase your stock of $5 bills.
If a customer pays with a $10 bill, you must give back $5 as a change. Therefore, you need at least one $5 bill in your cash drawer.
If a customer pays with a $20 bill, you must give back $15 as change. To do this, you have two options:
- Giving one $10 bill and one $5 bill
- Giving three $5 bill
So what should your greedy approach be at this point of time?
It’s better to give one $10 bill and one $5 bill as change instead of three $5 bills because $5 bills are more useful for future transactions.
Many customers may pay with $10 bills, and you’ll need $5 bills to give them change. If you use too many $5 bills now, you might not have enough for the next customers, making it harder to give the correct change later.
By saving $5 bills whenever possible, you’re better prepared for future payments.
However, if a $10 bill is not available, you have no choice but to give three $5 bills as change to ensure the transaction can still be completed.
Let us understand by the below video,
Let's understand with an example
Initial array: bills = [5, 5, 5, 10, 20]
This means we have 5 customers, and the bills they pay are:
- First customer: Pays with a $5 bill.
- Second customer: Pays with a $5 bill.
- Third customer: Pays with a $5 bill.
- Fourth customer: Pays with a $10 bill.
- Fifth customer: Pays with a $20 bill.
Step-by-Step Process:
- The first customer pays $5:
- We have no change needed because they paid exactly $5.
- Action: We increment the count of $5 bills by 1.
- Status:
- fiveDollarBills = 1
- tenDollarBills = 0
- The Second customer pays $5:
- Again, no change is needed because they paid exactly $5.
- Action: We increment the count of $5 bills by 1.
- Status:
- fiveDollarBills = 2
- tenDollarBills = 0
- The third customer pays $5:
- No change is needed again because they paid $5.
- Action: We increment the count of $5 bills by 1.
- Status:
- fiveDollarBills = 3
- tenDollarBills = 0
- The fourth customer pays $10:
- This customer pays with a $10 bill, but they need $5 as a change.
- Check: We have at least one $5 bill available (we have 3 $5 bills).
- Action: We give back 1 $5 bill as change.
- Status:
- fiveDollarBills = 2 (1 $5 bill was given as change)
- tenDollarBills = 1 (1 $10 bill was collected)
- Fifth customer pays $20:
- This customer pays with a $20 bill, and they need $15 as a change.
- Check: We first try to give $10 + $5 as change (i.e., one $10 bill and one $5 bill).
- Available bills: We have 1 $10 bill and 2 $5 bills.
- Action: We give 1 $10 bill and 1 $5 bill as change.
- Status:
- fiveDollarBills = 1 (1 $5 bill was given as change)
- tenDollarBills = 0 (1 $10 bill was given as change)
Final Status: After all transactions, we were able to give change for every customer. There were enough $5 and $10 bills available to provide the correct change for each customer who paid with $10 or $20.
Since we successfully provided the correct change for all customers, the function will return true.
Steps to write code
Step 1: Define the Variables
- Define two variables to keep track of the number of $5 and $10 bills you have:
- fiveDollarBills: Number of $5 bills.
- tenDollarBills: Number of $10 bills.
- No variable is needed for $20 bills because they are only used to pay, never for change.
Step 2: Iterate Through the bills Array
- Use a loop to process each customer’s bill.
- For each bill:
- If it’s a $5 bill:
- Increment fiveDollarBills (no change required).
- If it’s a $10 bill:
- Check if at least one $5 bill is available for change:
- If yes, decrement fiveDollarBills and increment tenDollarBills.
- If no, return false.
- If it’s a $20 bill:
- Try to give one $10 bill and one $5 bill as change (if possible).
- If not, try to give three $5 bills as change.
- If neither option works, return false.
Step 3: Return the Final Result
- If the loop completes without returning false, return true.
Code Implementation
C++
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
// Count of $5 and $10 bills in hand
int fiveDollarBills = 0;
int tenDollarBills = 0;
// Iterate through each customer's bill
for (int customerBill : bills) {
if (customerBill == 5) {
// Just add it to our count
fiveDollarBills++;
} else if (customerBill == 10) {
// We need to give $5 change
if (fiveDollarBills > 0) {
fiveDollarBills--;
tenDollarBills++;
} else {
// Can't provide change, return false
return false;
}
} else { // customerBill == 20
// We need to give $15 change
if (tenDollarBills > 0 && fiveDollarBills > 0) {
// Give change as one $10 and one $5
fiveDollarBills--;
tenDollarBills--;
} else if (fiveDollarBills >= 3) {
// Give change as three $5
fiveDollarBills -= 3;
} else {
// Can't provide change, return false
return false;
}
}
}
// If we've made it through all customers, return true
return true;
}
};Java
class Solution {
public boolean lemonadeChange(int[] bills) {
// Count of $5 and $10 bills
int fiveDollarBills = 0;
int tenDollarBills = 0;
// Iterate through each customer's bill
for (int bill : bills) {
// If the customer gives a $5 bill
if (bill == 5) {
// Add the $5 bill to the count
fiveDollarBills++;
}
// If the customer gives a $10 bill
else if (bill == 10) {
// Check if we have a $5 bill to give as change
if (fiveDollarBills > 0) {
// Decrement $5 bills and increment $10 bills
fiveDollarBills--;
tenDollarBills++;
} else {
// If no $5 bills are available, return false
return false;
}
}
// If the customer gives a $20 bill
else { // bill == 20
// Try to give one $10 bill and one $5 bill as change
if (tenDollarBills > 0 && fiveDollarBills > 0) {
tenDollarBills--;
fiveDollarBills--;
}
// Otherwise, try to give three $5 bills as change
else if (fiveDollarBills >= 3) {
fiveDollarBills -= 3;
}
// If neither option is possible, return false
else {
return false;
}
}
}
// If all customers are served successfully, return true
return true;
}
}
Python
class Solution(object):
def lemonadeChange(self, bills):
"""
:type bills: List[int]
:rtype: bool
"""
# Initialize counts for $5 and $10 bills
five_dollar_bills = 0
ten_dollar_bills = 0
# Iterate through each customer's bill
for bill in bills:
# If the customer pays with a $5 bill
if bill == 5:
# Add the $5 bill to the count
five_dollar_bills += 1
# If the customer pays with a $10 bill
elif bill == 10:
# Check if we can give $5 as change
if five_dollar_bills > 0:
# Decrement $5 bills and add a $10 bill
five_dollar_bills -= 1
ten_dollar_bills += 1
else:
# Return False if we can't provide change
return False
# If the customer pays with a $20 bill
else: # bill == 20
# Try to give one $10 and one $5 as change
if ten_dollar_bills > 0 and five_dollar_bills > 0:
ten_dollar_bills -= 1
five_dollar_bills -= 1
# Otherwise, try to give three $5 bills as change
elif five_dollar_bills >= 3:
five_dollar_bills -= 3
else:
# Return False if we can't provide change
return False
# If all customers are served successfully, return True
return True
Javascript
/**
* @param {number[]} bills
* @return {boolean}
*/
var lemonadeChange = function(bills) {
// Initialize counts for $5 and $10 bills
let fiveDollarBills = 0;
let tenDollarBills = 0;
// Iterate through each customer's bill
for (let bill of bills) {
// If the customer pays with a $5 bill
if (bill === 5) {
// Add the $5 bill to the count
fiveDollarBills++;
}
// If the customer pays with a $10 bill
else if (bill === 10) {
// Check if we can give $5 as change
if (fiveDollarBills > 0) {
// Decrement $5 bills and increment $10 bills
fiveDollarBills--;
tenDollarBills++;
} else {
// Return false if we can't provide change
return false;
}
}
// If the customer pays with a $20 bill
else { // bill === 20
// Try to give one $10 and one $5 as change
if (tenDollarBills > 0 && fiveDollarBills > 0) {
tenDollarBills--;
fiveDollarBills--;
}
// Otherwise, try to give three $5 bills as change
else if (fiveDollarBills >= 3) {
fiveDollarBills -= 3;
} else {
// Return false if we can't provide change
return false;
}
}
}
// If all customers are served successfully, return true
return true;
};
Time Complexity: O(n)
- Iterating Through the Array:
- The loop runs once for each bill in the bills array.
- Let the number of bills (length of the bills array) be n.
- The cost of iterating through the array is O(n).
- Operations Inside the Loop:
- For each bill, we perform a constant number of operations:
- Checking the value of the bill O(1).
- Conditional checks for change availability O(1).
- Updates to the variables fiveDollarBills and tenDollarBills O(1).
- These operations are all independent of the size of the input.
Total Time Complexity
- Since the loop runs n times and each iteration performs O(1), work: O(n)×O(1)=O(n)
- Overall Time Complexity: O(n).
Space Complexity: O(1)
- Input Space:
- The input is the array bills which holds the values of the bills paid by each customer. The space required to store the input is O(n), where n is the number of elements in the array. However, this is not considered part of the auxiliary space since it's part of the input.
- Auxiliary Space:
- We only need a constant amount of extra memory:
- fiveDollarBills: an integer to track the number of $5 bills we have.
- tenDollarBills: an integer to track the number of $10 bills we have.
- These two variables take up constant space regardless of the size of the input, meaning they require O(1) space.
- No Additional Data Structures:
- We do not use any dynamic data structures (like arrays, lists, or hashmaps) that grow with the size of the input.
- We only need a fixed amount of space for the two integer variables, so there is no additional memory usage.
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
A circular typewriter has letters 'a' to 'z', and the pointer starts at 'a'. Each second, you can move the pointer clockwise or counterclockwise by one step or type the current character. Given a string word, calculate the minimum seconds needed to type it by minimizing movement for each character.
You are given a 0-indexed integer array nums and an integer k. Your task is to perform the following operation exactly k times in order to maximize your score
1. Select an element m from nums.
2. Remove the selected element m from the array.
3. Add a new element with a value of m + 1 to the array.
4. Increase your score by m.