Problem Description

The "Lemonade Change" problem involves a line of customers at a lemonade stand. Each lemonade costs $5. Customers pay with either a $5, $10, or $20 bill, and you must provide correct change for each transaction. The challenge is to determine if you can provide change to every customer in the given order, starting with no money in your register.

• Each customer is represented in the bills array by the bill they use to pay (5, 10, or 20).
• You must give back correct change using only the bills you have already received from previous customers.
• You cannot break bills; you can only give change using the bills you currently have.
• Return true if you can provide change to every customer, otherwise return false.

Thought Process

At first glance, you might think about simulating every possible way to give change for each transaction, but that would be inefficient. Instead, you can keep track of the number of $5 and $10 bills you have, since those are the only denominations you'll need to give change (you never give out $20 bills as change).

For each customer:

• If they pay with a $5 bill, no change is needed—just add the $5 to your register.
• If they pay with a $10 bill, you must give back one $5 bill as change. If you don't have a $5 bill, you can't make change.
• If they pay with a $20 bill, you need to give $15 in change. The optimal way is to give one $10 and one $5 bill (if possible), otherwise, give three $5 bills. If neither is possible, you can't make change.

Solution Approach

Here’s how we solve the problem step by step:

1. Initialize counters: Start with two counters, five and ten, both set to 0. These represent the number of $5 and $10 bills in your register.
2. Iterate through each bill: For each customer in the bills array:
   • If the bill is $5, increment five by 1.
   • If the bill is $10:
     • Check if you have at least one $5 bill. If so, decrement five by 1 and increment ten by 1.
     • If not, return false.
   • If the bill is $20:
     • First, try to give one $10 and one $5 bill as change (if you have both). Decrement both counters accordingly.
     • If you don't have a $10 bill, try to give three $5 bills. Decrement five by 3.
     • If neither is possible, return false.
3. Return true if all customers are served: If you make it through the entire array without returning false, return true.

This greedy approach ensures you always use higher denominations for change first, preserving smaller bills for future transactions.

Example Walkthrough

Let's walk through an example input: bills = [5, 5, 5, 10, 20]

1. Customer 1 pays with $5. No change needed. Register: $5x1, $10x0.
2. Customer 2 pays with $5. No change needed. Register: $5x2, $10x0.
3. Customer 3 pays with $5. No change needed. Register: $5x3, $10x0.
4. Customer 4 pays with $10. Need to give $5 change. Register after: $5x2, $10x1.
5. Customer 5 pays with $20. Need to give $15 change. Prefer giving $10 + $5. Register after: $5x1, $10x0.

All customers receive correct change, so the answer is true.

Time and Space Complexity

Brute-force approach: If you tried every possible combination of bills for change, the time complexity would be exponential and impractical for large inputs.

Optimized (greedy) approach:

• Time complexity: O(n), where n is the number of customers, because you process each bill exactly once.
• Space complexity: O(1), because you only use two integer counters regardless of input size.

Summary

The Lemonade Change problem is elegantly solved using a greedy strategy: always give out the highest denomination possible for change, and track only the number of $5 and $10 bills. This approach ensures efficient change-making and avoids unnecessary complexity. By focusing on the constraints and using simple counters, you can handle any sequence of customer payments in linear time with constant space.

Code Implementation

class Solution:
    def lemonadeChange(self, bills):
        five, ten = 0, 0
        for bill in bills:
            if bill == 5:
                five += 1
            elif bill == 10:
                if five == 0:
                    return False
                five -= 1
                ten += 1
            else:  # bill == 20
                if ten > 0 and five > 0:
                    ten -= 1
                    five -= 1
                elif five >= 3:
                    five -= 3
                else:
                    return False
        return True
      

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five = 0, ten = 0;
        for (int bill : bills) {
            if (bill == 5) {
                five++;
            } else if (bill == 10) {
                if (five == 0) return false;
                five--;
                ten++;
            } else { // bill == 20
                if (ten > 0 && five > 0) {
                    ten--;
                    five--;
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
};
      

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0, ten = 0;
        for (int bill : bills) {
            if (bill == 5) {
                five++;
            } else if (bill == 10) {
                if (five == 0) return false;
                five--;
                ten++;
            } else { // bill == 20
                if (ten > 0 && five > 0) {
                    ten--;
                    five--;
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}
      

var lemonadeChange = function(bills) {
    let five = 0, ten = 0;
    for (let bill of bills) {
        if (bill === 5) {
            five += 1;
        } else if (bill === 10) {
            if (five === 0) return false;
            five -= 1;
            ten += 1;
        } else {
            if (ten > 0 && five > 0) {
                ten -= 1;
                five -= 1;
            } else if (five >= 3) {
                five -= 3;
            } else {
                return false;
            }
        }
    }
    return true;
};