What is the brute force approach and complexity for Lemonade Change?

Recurse, trying 10 + 5 and 5 + 5 + 5 at each $20 bill with time complexity O(2^N) and space complexity O(N).

What is the optimal approach and complexity for Lemonade Change?

Keep two counters; for a $20 use a $10 and a $5 when possible with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Lemonade Change?

Look for key signals in the prompt: "change for every customer, in order" indicates Each step depends on what is left in the drawer, so we walk the bills left to right and keep a running balance.; "bills of $5, $10 and $20" indicates Only three bill types, so a count for each of the two change bills is enough. There is no need to store the drawer.; "return true or false" indicates We only need to know whether anyone gets stuck, so one failure is enough to stop..

Lemonade Change

Easy·LeetCode #860Basic Anchor

LeetCode

Jump:

30-Second Mental ModelLocal Feasibility — running balance with a greedy choice for $20 change

Complexity:O(2^N)→O(N)

Key Insight

Keep two counters, fives and tens. A 5 adds a five. A 10 takes a five and adds a ten. For a 20, spend a 10 and a 5 whenever you can, and use three 5s only when there is no $10 to spend. If neither works, return false.

Core Validity Invariant

A 20 customer can be served only if the drawer holds a 10 and a 5, or three 5s. A 10 customer can be served only if the drawer holds a 5.

Problem

A lemonade costs 5. Customers line up one at a time, and each pays with a 5, 10 or 20 bill. You start with no money in the drawer.

Each customer must leave having paid exactly $5, so if they pay more, you must hand back the difference right away. Return true if you can give every customer the right change in order, and false if at some point you cannot.

Input

An array bills, where bills[i] is the bill that customer i pays with. Every value is 5, 10 or 20.

Output

true if every customer can get the right change, otherwise false.

Example 1

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

Output: true

The first three customers pay 5, so the drawer holds three 5 bills. The fourth pays 10 and gets a 5 back. The fifth pays 20 and gets a 10 and a $5 back.

Example 2

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

Output: false

After four customers the drawer holds two 10 bills and no 5 bill. The last customer needs 15 back, and two 10s cannot make that.

Constraints

• 1 ≤ bills.length ≤ 10^5
• Each bill is 5, 10 or 20.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
To give change to the next customer, what do you need to know about the drawer right now?
2.
A 5 bill can pay any change, but a 10 bill can only ever be handed out as part of a $20's change. Does that difference matter?
3.
For a 20 customer, how many different ways are there to hand back 15?
4.
If you had to choose one way for a $20, which one would leave you with the most options for later customers?
5.
Do you really need the full list of bills in the drawer, or is a count of each kind enough?

Brute force approach

Idea

Walk through the bills in order and keep the counts of 5 and 10 bills in the drawer. At each 20 there are two ways to pay the 15 change. Try both ways, and recurse on each one. If either path serves every customer, the answer is true.

Thinking process

1
The only thing that matters for the future is how many 5 and 10 bills are in the drawer.
2
A 5 customer adds a five. A 10 customer takes one five and adds a ten. Each of these has only one way to be done.
3
A $20 customer has two options: a 10 and a 5, or three $5s. I do not know which one is right, so I try both.
4
Example: bills = [5, 5, 5, 5, 10, 20, 10]. After four 5s and the 10 customer, the drawer holds three 5s and one 10. At the 20, 10 + 5 leaves two 5s and no 10. 5 + 5 + 5 leaves no 5 and one 10. The last 10 customer can only be served on the 10 + 5 path.

Visual

Each node is a customer's bill; the note shows the drawer before that customer. Blue = the path being explored, green = everyone served, red = a dead end.

Brute force tries both ways for $20bills = [5, 5, 5, 5, 10, 20, 10]step 1/10

Call

fives: 0
tens: 0

$5: no change

Customer 1 pays $5. Keep it: fives becomes 1.

Code & Implementation

brute.cpp

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        return give(bills, 0, 0, 0);
    }

private:
    // fives and tens are the bills in the drawer. Try every way to pay the change.
    bool give(const vector<int>& bills, int i, int fives, int tens) {
        if (i == (int)bills.size()) return true;

        int bill = bills[i];
        if (bill == 5) return give(bills, i + 1, fives + 1, tens);
        if (bill == 10) {
            if (fives == 0) return false;  // no $5 to give back
            return give(bills, i + 1, fives - 1, tens + 1);
        }

        // bill == 20: owe $15. Option 1: a $10 and a $5. Option 2: three $5s.
        // Explore both, so we never assume either one is the right choice.
        bool viaTenAndFive = tens >= 1 && fives >= 1 && give(bills, i + 1, fives - 1, tens - 1);
        bool viaThreeFives = fives >= 3 && give(bills, i + 1, fives - 3, tens);
        return viaTenAndFive || viaThreeFives;
    }
};

Complexity

Time O(2^N)Space O(N)

Only a 20 bill has two choices, so the recursion has at most 2^N paths (it reaches that when many 20s come after plenty of $5s). It goes at most N levels deep, which uses O(N) stack space.

Optimized approach

Idea

Start from brute force

The brute force tries both ways to give 15 at every 20, and recurses on both. Most of that work is not needed, because one of the two ways is always at least as good.

Find the repeated work

Each 20 splits the search into two drawers, and the recursion follows both all the way to the end. Those two drawers differ only in how the money is split between 5s and 10s, and one of them always keeps more 5s.

Define the state — what variables do I need?

fives: How many $5 bills are in the drawer. A $5 can pay any change, so these are the most useful bills we hold.
tens: How many $10 bills are in the drawer. A $10 is only useful as part of a $20's change.

Define validity

A 20 customer can be served only if the drawer holds a 10 and a 5, or three 5s. A 10 customer can be served only if the drawer holds a 5.

Define the transitions — when does each pointer move, and why is it safe?

The bill is $5

fives++

The customer pays exactly $5, so no change is given. The bill stays in the drawer.

The bill is $10, and fives ≥ 1

fives−−, tens++

One 5 goes back to the customer. The 10 stays in the drawer, where it can help a later $20 customer.

The bill is $20, and tens ≥ 1 and fives ≥ 1

tens−−, fives−−

A 10 is only useful for a 20's change, but a 5 helps everyone. So spend the 10 and keep the $5s.

The bill is $20, and fives ≥ 3 (no $10 to use)

fives −= 3

This is the only other way to make $15, so it is the fallback.

Any other case (a $10 with no $5, or a $20 with no way to pay)

return false

The drawer cannot make the change, and no other choice could have helped.

What does the current window add to the answer?

Every customer either adds to the drawer or takes change out of it. The answer is true only if nobody gets stuck.

Code & Implementation

optimal.cpp

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int fives = 0;  // $5 bills in the drawer
        int tens = 0;   // $10 bills in the drawer

        for (int bill : bills) {
            if (bill == 5) {
                fives++;
            } else if (bill == 10) {
                if (fives == 0) return false;
                fives--;
                tens++;
            } else {
                // bill == 20: owe $15. A $10 can only ever help with a $20's change,
                // while a $5 helps with every bill. So spend the $10 first (10 + 5).
                if (tens > 0 && fives > 0) {
                    tens--;
                    fives--;
                } else if (fives >= 3) {
                    fives -= 3;  // no $10 left: three $5s
                } else {
                    return false;
                }
            }
        }
        return true;
    }
};

Complexity

Time O(N)Space O(1)

One pass over the bills with two counters. There is no recursion and no list of bills.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Recurse, trying 10 + 5 and 5 + 5 + 5 at each $20 bill	O(2^N)	O(N)
Optimal	Keep two counters; for a $20 use a $10 and a $5 when possible	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“change for every customer, in order”Each step depends on what is left in the drawer, so we walk the bills left to right and keep a running balance.
“bills of $5, $10 and $20”Only three bill types, so a count for each of the two change bills is enough. There is no need to store the drawer.
“return true or false”We only need to know whether anyone gets stuck, so one failure is enough to stop.

Running balance (drawer)+fails when a customer cannot be given change+keep the most flexible bills→Local Feasibility — running balance with a greedy choice for $20 change

This is a running balance question. The drawer must never run short, and it changes by one step per customer. What makes it different from a plain balance check is the choice for a $20: the two ways to make 15 leave different drawers. The greedy picks the one that keeps the most useful money, the 5s. In Candy and Gas Station there is no such choice to make.

Don't make this mistake

Pattern confusion: smallest bills first

✗ if (fives >= 3) { fives -= 3; // three $5s first } else if (tens > 0 && fives > 0) { tens--; fives--; }

✓ if (tens > 0 && fives > 0) { tens--; fives--; // a $10 and a $5 first } else if (fives >= 3) { fives -= 3; }

This looks like making change with as few small coins as possible, but the rule is about keeping the most useful money. With bills = [5, 5, 5, 5, 10, 20, 10], the wrong order pays the 20 with 5 + 5 + 5. That leaves no 5 and one 10, so the last 10 customer cannot get change and the answer is false. The right order pays 10 + 5 and keeps two $5s, so the answer is true.

Forgetting that a $10 stays in the drawer

✗ if (bill == 10) { fives--; // the $10 is not stored }

✓ if (bill == 10) { fives--; tens++; }

Without tens++, the 10 disappears and a later 20 cannot use it. With bills = [5, 5, 10, 20], the right answer is true: the 10 takes a 5 back, and the 20 is paid as 10 + 5. The buggy version has no 10 for the 20, needs three 5s, has only one, and returns false.

Not checking for change on a $10 customer

✗ if (bill == 10) { fives--; // fives may go negative tens++; }

✓ if (bill == 10) { if (fives == 0) return false; fives--; tens++; }

If no $5 is in the drawer, the counter goes negative and later checks read nonsense. With bills = [10, 5, 5, 5, 5, 20], the first customer cannot get change, so the answer is false. Without the check, the counters are fives = −1, then fives = 3 at the $20, and the code returns true.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Greedy translate into production architectures and low-level memory mechanics.

LLD Architecture