Lemonade Change

Easy

Amazon

8 views

Topics:

Greedy AlgorithmsArrays

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 i^th 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 <= 10⁵
bills[i] is either 5, 10, or 20.

Try coding it in LeetCode

Lemonade Change

Easy

Amazon

8 views

Topics:

Greedy AlgorithmsArrays

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 i^th 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 <= 10⁵
bills[i] is either 5, 10, or 20.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible length of the bills array?
Can the bills array contain any values other than 5, 10, and 20?
If at any point I cannot provide correct change, should I return false immediately, or continue processing the remaining bills?
If the array is empty, should I return true or false?
Are the bills processed in the order they appear in the array, and must the change be given immediately after receiving each bill?

Brute Force Solution

Approach

We need to give correct change using only 5 and 10 dollar bills. The brute force method involves simulating every possible transaction and checking if we can always provide change correctly. If even one transaction fails, the whole scenario is impossible.

Here's how the algorithm would work step-by-step:

Start with no 5 or 10 dollar bills in our till.
Go through each customer's transaction one by one.
If a customer pays with a 5 dollar bill, simply add it to our till.
If a customer pays with a 10 dollar bill, we need to give them 5 dollars in change. Check if we have a 5 dollar bill to give. If not, this scenario is impossible.
If we have a 5 dollar bill, give it as change and add the 10 dollar bill to our till.
If a customer pays with a 20 dollar bill, we need to give them 15 dollars in change. Try all the possible combinations of 5 and 10 dollar bills we could use to make 15 dollars.
For example, we could give one 10 dollar bill and one 5 dollar bill, or three 5 dollar bills. For each possibility, check if we have enough of each type of bill.
If none of the possible combinations work (we don't have the bills), this scenario is impossible.
If at least one combination works, give the change and update our till (removing the bills used for change and adding the 20 dollar bill).
After processing all customers, if we never encountered an impossible scenario, then it's possible to give correct change in all cases.

Code Implementation

def lemonade_change_brute_force(bills):
    five_dollar_bills = 0
    ten_dollar_bills = 0

    for bill in bills:
        if bill == 5:
            five_dollar_bills += 1

        elif bill == 10:
            # Need to give one 5 dollar bill as change
            if five_dollar_bills == 0:
                return False

            five_dollar_bills -= 1
            ten_dollar_bills += 1

        else:
            # Need to give 15 dollars in change. Try 10 + 5 first.
            if ten_dollar_bills > 0 and five_dollar_bills > 0:
                ten_dollar_bills -= 1
                five_dollar_bills -= 1

            # Try three 5 dollar bills as a fallback.
            elif five_dollar_bills >= 3:
                five_dollar_bills -= 3

            # If we can't give 15 dollars in change, it's impossible.
            else:
                return False

    # If we made it through all transactions, it's possible.
    return True

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each customer's payment once. For each customer (n customers in total), it performs a fixed number of operations: updating the counts of 5 and 10 dollar bills, and possibly checking combinations of 5 and 10 dollar bills to provide change for a 20 dollar bill. Since the number of operations within the loop is constant and does not depend on the input size, the overall time complexity is determined by the single loop iterating through the customers. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The algorithm uses a fixed number of variables to keep track of the number of 5 and 10 dollar bills. These variables are updated based on each customer's transaction, but the number of variables does not depend on the number of customers (N). Therefore, the auxiliary space used is constant, resulting in a space complexity of O(1).

Optimal Solution

Approach

This problem is about making change with only two denominations of bills: $5 and $10. The optimal strategy is to always prioritize giving back larger bills ($10s) whenever possible, as this leaves us with more smaller bills ($5s) which are more versatile for future transactions.

Here's how the algorithm would work step-by-step:

Keep track of how many $5 and $10 bills you have.
When a customer gives you a $5 bill, just add it to your count.
When a customer gives you a $10 bill, try to give them a $5 bill back. If you can't (because you don't have any $5 bills), you can't make the sale.
When a customer gives you a $20 bill, first try to give them one $10 bill and one $5 bill. If you can't, then try to give them three $5 bills. If you can't do either, you can't make the sale.
After each transaction, check if you were able to give the correct change. If at any point you cannot provide the right change, the overall answer is that you cannot make change for everyone.
If you get through all customers without being unable to provide the change, the answer is that you can make change for everyone.

Code Implementation

def lemonadeChange(bills):
    five_dollar_count = 0
    ten_dollar_count = 0

    for bill in bills:
        if bill == 5:
            five_dollar_count += 1
        elif bill == 10:
            # Need to give back a $5
            if five_dollar_count == 0:
                return False
            five_dollar_count -= 1
            ten_dollar_count += 1

        elif bill == 20:
            # Try to give back a $10 and a $5 first
            if ten_dollar_count > 0 and five_dollar_count > 0:
                ten_dollar_count -= 1
                five_dollar_count -= 1

            # Otherwise, give back three $5s
            elif five_dollar_count >= 3:
                five_dollar_count -= 3

            # If neither of the above work, can't make change
            else:
                return False

    return True

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of bill amounts once. For each bill, a constant number of operations are performed: incrementing counters or checking if change can be made using a fixed number of subtractions. Therefore, the time complexity is directly proportional to the number of bills, n, resulting in O(n).

Space Complexity

O(1) – The algorithm keeps track of the number of $5 and $10 bills. These counts are stored in a fixed number of variables, regardless of the number of customers (N). No auxiliary data structures that scale with the input size are used. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input array	Return true immediately as there are no customers to serve, hence no change needed.
Input array with a single bill value (e.g., [5])	Return true as we can always provide change if the first bill is 5.
Array starts with a bill greater than 5 (e.g., [10, 5])	Return false immediately as we cannot provide change for the first customer.
Array contains only 5s	Return true since we never need to provide change.
Array contains only 10s and 20s, but no 5s.	Return false since we will never have 5s to make change for any 10s or 20s.
Array with a large number of bills (performance considerations)	The solution should use a constant-time lookup (e.g., using counters for each bill type) to maintain good performance irrespective of the array size.
A sequence of bills requiring precise change combinations (e.g., [5, 10, 20, 5, 5, 5, 5, 5, 5, 20, 20]) that may lead to incorrect change if not carefully handled	The algorithm must prioritize using 10s before 5s when making change for a 20 to ensure optimal usage of available bills.
Input contains very large numbers of 5, 10 and 20 dollar bills, nearing integer overflow	Use appropriate data types (e.g., long in Java/C++) to store the counts of bills to prevent integer overflow issues if the bill counts become excessively large.