Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Lemonade Change

EASYProblemSolveExternal Links

Description

You are running a lemonade stand where each lemonade costs exactly **5∗∗.Customersarestandinginaqueueandwillbuyonelemonadeeach,payingwitheithera5**. Customers are standing in a queue and will buy one lemonade each, paying with either a 5, 10,or10, or 20 bill.

You must provide the correct change to every customer so that each customer effectively pays $5 for their lemonade. You start with no bills in your cash register at all.

Given an integer array bills where bills[i] represents the bill the i-th customer pays with, return true if you can provide every customer with the correct change, or false otherwise.

Examples

Example 1

Input: bills = [5, 5, 5, 10, 20]

Output: true

Explanation: The first three customers each pay with a 5bill,sonochangeisneeded—wesimplycollectthree5 bill, so no change is needed — we simply collect three 5 bills. The fourth customer pays with 10,sowegivebackone10, so we give back one 5 bill as change (we still have two 5billsandone5 bills and one 10 bill). The fifth customer pays with 20,andweneedtoreturn20, and we need to return 15. We give back one 10billandone10 bill and one 5 bill. Every customer received correct change, so the answer is true.

Example 2

Input: bills = [5, 5, 10, 10, 20]

Output: false

Explanation: The first two customers pay with 5bills—wecollecttwo5 bills — we collect two 5 bills. The third customer pays with 10,sowereturnone10, so we return one 5 bill as change (leaving us with one 5andone5 and one 10). The fourth customer also pays with 10,sowereturnourlast10, so we return our last 5 bill (leaving us with zero 5billsandtwo5 bills and two 10 bills). The fifth customer pays with 20andneeds20 and needs 15 in change. We have two 10billsbutzero10 bills but zero 5 bills. We cannot make 15fromtwo15 from two 10 bills alone, so we return false.

Example 3

Input: bills = [5, 5, 10, 20, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 20, 10, 5, 20]

Output: false

Explanation: This is a longer sequence that tests the greedy strategy. At some point in the sequence, a 20customerarriveswhenwedonothavetherightcombinationofbillstomake20 customer arrives when we do not have the right combination of bills to make 15 in change.

Constraints

  • 1 ≤ bills.length ≤ 10^5
  • bills[i] is either 5, 10, or 20

Editorial

Brute Force

Intuition

The most straightforward way to think about this problem is to simulate the process exactly as described. Imagine you are the cashier standing behind the lemonade stand with a cash register in front of you.

Each time a customer walks up, they hand you a bill. If it is a 5bill,youarehappy—nochangeisneeded,justdropitintheregister.Ifitisa5 bill, you are happy — no change is needed, just drop it in the register. If it is a 10 bill, you need to dig through your register and find a 5billtohandback.Ifitisa5 bill to hand back. If it is a 20 bill, you need to find bills totaling $15 to return.

In this brute force simulation, we keep an explicit list of all the bills currently in our register. When we need to give change, we search through that list to find the right bills. For a 10payment,welookforany10 payment, we look for any 5 bill. For a 20payment,wefirsttrytofinda20 payment, we first try to find a 10 and a 5(preferred),andifthatfails,wetrytofindthree5 (preferred), and if that fails, we try to find three 5 bills.

This approach directly mirrors what a real cashier would do — rifling through the cash drawer looking for the right combination of bills.

Step-by-Step Explanation

Let's trace through bills = [5, 5, 10, 10, 20]:

Step 1: Customer 1 pays 5.Nochangeneeded.Register:[5. No change needed. Register: [5].

Step 2: Customer 2 pays 5.Nochangeneeded.Register:[5. No change needed. Register: [5, $5].

Step 3: Customer 3 pays 10.Need10. Need 5 change. Search register for a 5bill—found!Removeone5 bill — found! Remove one 5, add 10.Register:[10. Register: [5, $10].

Step 4: Customer 4 pays 10.Need10. Need 5 change. Search register for a 5bill—found!Removethe5 bill — found! Remove the 5, add 10.Register:[10. Register: [10, $10].

Step 5: Customer 5 pays 20.Need20. Need 15 change. First try: search for a 10+10 + 5 — we have 10butno10 but no 5. Second try: search for three $5 bills — we have none. Cannot make change! Return false.

Brute Force — Simulating the Cash Register — Watch how we maintain an explicit list of bills and search through it each time we need to give change.

Algorithm

  1. Initialize an empty list to represent the cash register
  2. For each bill in the bills array:
    • If the bill is 5:add5: add 5 to register (no change needed)
    • If the bill is 10:searchregisterfora10: search register for a 5 bill. If found, remove it and add $10. If not found, return false
    • If the bill is 20:firsttrytofinda20: first try to find a 10 and a 5inregister.Ifthatfails,trytofindthree5 in register. If that fails, try to find three 5 bills. If both fail, return false
  3. If all customers served successfully, return true

Code

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        vector<int> reg;  // cash register
        for (int bill : bills) {
            if (bill == 5) {
                reg.push_back(5);
            } else if (bill == 10) {
                // Search for a $5 bill
                auto it = find(reg.begin(), reg.end(), 5);
                if (it == reg.end()) return false;
                reg.erase(it);
                reg.push_back(10);
            } else {
                // Try $10 + $5 first
                auto it10 = find(reg.begin(), reg.end(), 10);
                auto it5 = find(reg.begin(), reg.end(), 5);
                if (it10 != reg.end() && it5 != reg.end()) {
                    reg.erase(it10);
                    it5 = find(reg.begin(), reg.end(), 5);
                    reg.erase(it5);
                } else {
                    // Try three $5 bills
                    int count = 0;
                    for (auto it = reg.begin(); it != reg.end() && count < 3;) {
                        if (*it == 5) {
                            it = reg.erase(it);
                            count++;
                        } else {
                            ++it;
                        }
                    }
                    if (count < 3) return false;
                }
            }
        }
        return true;
    }
};
class Solution:
    def lemonadeChange(self, bills: list[int]) -> bool:
        register = []  # list of bills in the cash register
        for bill in bills:
            if bill == 5:
                register.append(5)
            elif bill == 10:
                if 5 in register:
                    register.remove(5)
                    register.append(10)
                else:
                    return False
            else:  # bill == 20
                # Try $10 + $5 first
                if 10 in register and 5 in register:
                    register.remove(10)
                    register.remove(5)
                elif register.count(5) >= 3:
                    for _ in range(3):
                        register.remove(5)
                else:
                    return False
        return True
class Solution {
    public boolean lemonadeChange(int[] bills) {
        List<Integer> register = new ArrayList<>();
        for (int bill : bills) {
            if (bill == 5) {
                register.add(5);
            } else if (bill == 10) {
                if (register.contains(5)) {
                    register.remove(Integer.valueOf(5));
                    register.add(10);
                } else {
                    return false;
                }
            } else {
                // Try $10 + $5 first
                if (register.contains(10) && register.contains(5)) {
                    register.remove(Integer.valueOf(10));
                    register.remove(Integer.valueOf(5));
                } else {
                    int count = 0;
                    Iterator<Integer> it = register.iterator();
                    while (it.hasNext() && count < 3) {
                        if (it.next() == 5) {
                            it.remove();
                            count++;
                        }
                    }
                    if (count < 3) return false;
                }
            }
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(n²)

For each of the n customers, we may need to search through the register list to find specific bills. The find or remove operation on a list takes O(n) time in the worst case (where n is the number of bills accumulated so far). Over all customers, this leads to O(n²) total work.

Space Complexity: O(n)

We store every received bill in the register list. In the worst case (all $5 payments), the list grows to size n.

Why This Approach Is Not Efficient

The brute force approach maintains an explicit list of bills and searches through it each time change is needed. This search takes O(n) per customer, leading to O(n²) total time.

With n up to 10^5, that means up to 10^10 operations in the worst case — far too slow for any reasonable time limit.

The core insight is that we do not need to track individual bills at all. Since there are only three denominations (5,5, 10, 20),and20), and 20 bills are never useful for making change, we only need to know how many 5and5 and 10 bills we have at any moment. Two simple integer counters replace the entire list, eliminating the need for searching.

Additionally, when giving change for a 20bill,thegreedystrategyofpreferringtogiveone20 bill, the greedy strategy of preferring to give one 10 + one 5(ratherthanthree5 (rather than three 5 bills) is always optimal. This is because 5billsaremoreversatile—theyareneededforboth5 bills are more versatile — they are needed for both 10 and 20customers—while20 customers — while 10 bills can only be used for 20customers.Conserving20 customers. Conserving 5 bills gives us the best chance of serving future customers.

Optimal Approach - Greedy with Bill Counters

Intuition

Instead of keeping a list of every bill, we observe that only two numbers matter: how many 5billswehaveandhowmany5 bills we have and how many 10 bills we have. We never need to track 20billsbecausetheyaretoolargetouseaschange(themostchangeweevergiveis20 bills because they are too large to use as change (the most change we ever give is 15).

Think of it like a simplified cash register with just two compartments — one for 5billsandonefor5 bills and one for 10 bills. When a customer pays:

  • **5bill:∗∗Dropitinthe5 bill:** Drop it in the 5 compartment. Done.
  • **10bill:∗∗Takeonefromthe10 bill:** Take one from the 5 compartment, drop the 10inthe10 in the 10 compartment.
  • **20bill:∗∗Youneedtoreturn20 bill:** You need to return 15. You have two options:
    • Option A: One 10bill+one10 bill + one 5 bill = $15
    • Option B: Three 5bills=5 bills = 15

The greedy choice is to always prefer Option A when available. Why? Because 5billsaretheuniversalcurrencyofchange−making—everycustomerwhodoesnotpayexactly5 bills are the universal currency of change-making — every customer who does not pay exactly 5 needs at least one 5billback.But5 bill back. But 10 bills are only useful when a 20customerarrives.Byusingupa20 customer arrives. By using up a 10 bill (which has limited use) instead of three $5 bills (which are highly flexible), we preserve our most valuable resource.

This greedy strategy is provably optimal: if a solution exists where you give three 5billsfora5 bills for a 20 while having a 10available,youcanalwaysswaptousing10 available, you can always swap to using 10+5andendupwithatleastasmany5 and end up with at least as many 5 bills for the remaining customers.

Step-by-Step Explanation

Let's trace through bills = [5, 5, 5, 10, 20]:

Step 1: Customer pays $5. No change needed. Increment fives counter.

  • fives = 1, tens = 0

Step 2: Customer pays $5. No change needed. Increment fives counter.

  • fives = 2, tens = 0

Step 3: Customer pays $5. No change needed. Increment fives counter.

  • fives = 3, tens = 0

Step 4: Customer pays 10.Need10. Need 5 change. We have fives = 3, so give one back.

  • Decrement fives, increment tens.
  • fives = 2, tens = 1

Step 5: Customer pays 20.Need20. Need 15 change.

  • Check Option A: do we have a 10ANDa10 AND a 5? tens = 1 ≥ 1 and fives = 2 ≥ 1 — YES!
  • Use one 10+one10 + one 5.
  • fives = 1, tens = 0

Step 6: All customers served successfully. Return true.

Greedy Strategy — Tracking Bill Counters — Watch how two simple counters (fives and tens) replace an entire cash register. For $20 bills, we greedily prefer using a $10 + $5 to conserve our flexible $5 bills.

Algorithm

  1. Initialize two counters: fives = 0 and tens = 0
  2. For each bill in the bills array:
    • If bill == 5: increment fives by 1
    • If bill == 10: increment tens by 1, decrement fives by 1
    • If bill == 20:
      • If tens ≥ 1 (greedy preference): decrement tens by 1, decrement fives by 1
      • Else: decrement fives by 3
    • After processing, if fives < 0: return false (cannot make change)
  3. Return true (all customers served)

Code

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int fives = 0, tens = 0;
        
        for (int bill : bills) {
            if (bill == 5) {
                fives++;
            } else if (bill == 10) {
                tens++;
                fives--;
            } else {  // bill == 20
                if (tens > 0) {
                    tens--;
                    fives--;
                } else {
                    fives -= 3;
                }
            }
            
            if (fives < 0) return false;
        }
        
        return true;
    }
};
class Solution:
    def lemonadeChange(self, bills: list[int]) -> bool:
        fives = 0
        tens = 0
        
        for bill in bills:
            if bill == 5:
                fives += 1
            elif bill == 10:
                tens += 1
                fives -= 1
            else:  # bill == 20
                if tens > 0:
                    tens -= 1
                    fives -= 1
                else:
                    fives -= 3
            
            if fives < 0:
                return False
        
        return True
class Solution {
    public boolean lemonadeChange(int[] bills) {
        int fives = 0, tens = 0;
        
        for (int bill : bills) {
            if (bill == 5) {
                fives++;
            } else if (bill == 10) {
                tens++;
                fives--;
            } else {  // bill == 20
                if (tens > 0) {
                    tens--;
                    fives--;
                } else {
                    fives -= 3;
                }
            }
            
            if (fives < 0) return false;
        }
        
        return true;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the bills array exactly once. Each customer is processed in O(1) time — we only perform counter increments, decrements, and a single comparison. No searching through any collection is required. For n customers, the total work is O(n).

Space Complexity: O(1)

We use only two integer variables (fives and tens) regardless of the input size. No additional data structures are allocated, so space usage is constant.