Problem of The Day: Lemonade Change

Problem Statement

Intuition

When approaching this problem, my first thought is to consider how I can efficiently manage the change I need to give to each customer. Since each customer only pays with a $5, $10, or $20 bill, I can use a greedy approach to maximize the use of higher denomination bills when providing change, thereby preserving smaller bills for future transactions.

Approach

To solve the problem, I maintain a dictionary cash to keep track of the number of $5, $10, and $20 bills I have on hand. As I iterate through each transaction, I update this dictionary with the bill received. When making change, I always try to use the largest bills available first, which allows me to save smaller bills for situations where they are absolutely necessary.

Specifically, after receiving a bill, I calculate the change required by subtracting $5 from the bill’s value. Then, I attempt to provide this change by deducting from the available bills in the order of $20, $10, and then $5. If I am unable to provide the exact change, I return False, indicating that it’s impossible to serve all customers with the current cash on hand. If I successfully process all transactions, I return True.

Complexity

• Time complexity:
  The time complexity is \(O(n)\), where \(n\) is the number of transactions. For each transaction, I may need to check up to three different bill denominations.

• Space complexity:
  The space complexity is \(O(1)\) because the amount of memory I use does not scale with the size of the input. I only store the count of three types of bills.

Code

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        cash = {5: 0, 10: 0, 20: 0}
        for bill in bills:
            cash[bill] += 1
            change = bill - 5
            for x in [20, 10, 5]:
                while cash[x] > 0 and change >= x:
                    change -= x
                    cash[x] -= 1
            if change != 0:
                return False
        return True

Editorial

Approach: Simulation

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        # Count of $5 and $10 bills in hand
        five_dollar_bills = 0
        ten_dollar_bills = 0

        # Iterate through each customer's bill
        for customer_bill in bills:
            if customer_bill == 5:
                # Just add it to our count
                five_dollar_bills += 1
            elif customer_bill == 10:
                # We need to give $5 change
                if five_dollar_bills > 0:
                    five_dollar_bills -= 1
                    ten_dollar_bills += 1
                else:
                    # Can't provide change, return false
                    return False
            else:  # customer_bill == 20
                # We need to give $15 change
                if ten_dollar_bills > 0 and five_dollar_bills > 0:
                    # Give change as one $10 and one $5
                    five_dollar_bills -= 1
                    ten_dollar_bills -= 1
                elif five_dollar_bills >= 3:
                    # Give change as three $5
                    five_dollar_bills -= 3
                else:
                    # Can't provide change, return false
                    return False
        # If we've made it through all customers, return true
        return True