Lemonade Change

At its core, this problem can be seen as a resource management challenge. You are tasked with managing two types of resources ($5 and $10 bills) that you accumulate over time (as you iterate over the ‘bills’ array).

Your objective is to ensure that you always have the necessary resources to satisfy a series of incoming requests (represented by the denominations in the ‘bills’ array), each requiring a specific combination of resources to be available ($5 bill when $10 bill is given, and either $10 and $5 or three $5 bills when $20 bill is given).

The problem is complicated by the sequential nature of the requests (you cannot reorder them) and by the fact that the availability of resources at any given time depends on the history of previous requests.

Solution

To solve this problem, we can keep track of the number of $5 and $10 bills we have in hand. We don’t need to track the $20 bills since they are not useful for making change.

When a customer gives us a bill, we have three scenarios:

It’s a $5 bill: We just keep it, no change is needed.
It’s a $10 bill: We need to give back one $5 bill. So we need to have at least one $5 bill.
It’s a $20 bill: We can either give back one $10 bill and one $5 bill, or three $5 bills. So we need to have either of these combinations.

Here is the python code that implements this idea:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five = ten = 0
        for bill in bills:
            if bill == 5:
                five += 1
            elif bill == 10:
                if five == 0: 
                    return False
                five -= 1
                ten += 1
            else:
                if ten > 0 and five > 0:
                    ten -= 1
                    five -= 1
                elif five >= 3:
                    five -= 3
                else:
                    return False
        return True

The time complexity for this solution is O(n), where n is the length of the bills list, since we traverse the list once. The space complexity is O(1), since we only use two variables to keep track of the number of $5 and $10 bills.

Greedy Approach

This problem can be solved using a greedy approach. At each step, when we need to provide the change, we make the locally optimal choice.

When a customer pays with a $10 bill, we will give back a $5 bill if we have it.

When a customer pays with a $20 bill, we have two choices for change: we could use one $10 bill and one $5 bill, or use three $5 bills. The optimal choice is to use one $10 bill and one $5 bill if we have them, because this will leave us with more $5 bills, which are more versatile as they can be used for change in either situation.

By following this greedy strategy, we maximize the likelihood of being able to make change for future customers, and can return false as soon as we know it’s impossible to give a customer the correct change.

It maintains two counters, five and ten, which track the number of $5 and $10 bills in the cash register respectively.
It iterates through the list of bills. If a bill is $5, it increments the five counter. If a bill is $10, it increments the ten counter and decrements the five counter (to give $5 change). If a bill is $20, it attempts to give change either by decrementing the ten counter and five counter (giving $15 change with a $10 bill and a $5 bill), or by decrementing the five counter three times (giving $15 change with three $5 bills).
If at any point, it’s not possible to give the correct change (because there are not enough $5 or $10 bills), the function returns False. If it successfully iterates through all the bills, it returns True.

This is a greedy strategy because at each step, it makes the locally optimal choice: it favors giving change with a $10 bill over three $5 bills when a customer pays with a $20 bill. By following this strategy, it maximizes the likelihood of being able to make change for future customers.