Lemonade Change - Leetcode Solution

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 don't have any change in hand at first.

Return true if and only if you can provide every customer with correct change.

Solution:

We can solve this problem by simulating the transaction process, just like a real lemonade stand.

For each customer, we check if they have a $5 bill. If yes, we keep it as change and move on to the next customer.

If they have a $10 bill, we try to give them change of $5. If we don't have a $5 bill in our possession, we can't make the transaction and return false.

If they have a $20 bill, we try to give them change of $15 ($10 + $5). If we have both a $10 and a $5 bill, we give them that. If we don't have the exact change, we can try giving them $10 + $5 + $5. If we don't have that either, we can't make the transaction and return false.

If we reach the end of the queue without any issues, we return true.

Here's the code implementation:

def lemonadeChange(bills):
    num_5 = 0
    num_10 = 0
    
    for bill in bills:
        if bill == 5:
            num_5 += 1
        elif bill == 10:
            if num_5 == 0:
                return False
            num_5 -= 1
            num_10 += 1
        elif bill == 20:
            if num_10 >= 1 and num_5 >= 1:
                num_10 -= 1
                num_5 -= 1
            elif num_5 >= 3:
                num_5 -= 3
            else:
                return False
    
    return True

Time complexity: O(N), where N is the number of customers in the queue.

Space complexity: O(1), we only use constant space to store the number of $5 and $10 bills we have.

1