Lemonade Change: Greedy Change-Making

You are selling lemonade at a stand where each lemonade costs $5. Customers line up and pay with $5, $10, or $20 bills. You start with no change in your register. For each customer, you must provide the correct change from the bills you have collected so far. Return true if you can serve every customer, or false if at any point you cannot make change.

This is LeetCode 860: Lemonade Change, an easy problem that introduces the greedy change-making pattern. The trick is that you never need to search for the best combination of bills. A simple priority rule (prefer giving $10 bills when possible) is always optimal.

Why this problem matters

Lemonade Change is one of the cleanest introductions to greedy algorithms. The problem has only three cases ($5, $10, $20), but the $20 case forces you to make a choice: give back one $10 and one $5, or give back three $5s. Choosing wrong means you run out of $5 bills sooner, which can cause a failure later.

This pattern of "prefer the larger denomination" shows up in real-world change-making, resource allocation, and scheduling problems. Learning to recognize when a greedy choice is provably optimal is a fundamental skill for algorithm design.

The brute force approach

For this problem, a brute force approach might try all possible combinations of change for each customer. But since the denominations are fixed and there are only three cases, the "brute force" is really just handling each case without the greedy optimization for $20 bills.

def lemonade_change_brute(bills):
    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 five >= 3:
                five -= 3
            elif ten > 0 and five > 0:
                ten -= 1
                five -= 1
            else:
                return False
    return True

This version always tries three $5s first when a customer pays $20. It works on some inputs, but it wastes $5 bills unnecessarily. Consider bills = [5, 5, 10, 10, 20]. After processing the first four bills, you have five=0, ten=2. The $20 customer needs $15 in change, but you have no $5 bills left. The algorithm returns false, even though choosing $10 + $5 earlier in a different order would not help here. The real issue is that the "three $5s first" priority is suboptimal. Swapping the priority to prefer $10 + $5 is the key.

The key insight: greedy bill selection

When a customer pays $20, you need to give $15 in change. You have two options:

• Give one $10 bill and one $5 bill ($15 total)
• Give three $5 bills ($15 total)

Always prefer the first option. Why? Because $5 bills are more versatile. A $10 bill can only be used as change for a $20. A $5 bill can be used as change for both $10 and $20 payments. By spending a $10 bill whenever possible, you conserve your $5 bills for future customers who might pay with $10.

This is a locally optimal choice that is also globally optimal. No matter what bills come next, you are never worse off having spent a $10 instead of three $5s.

Walking through it step by step

Let's trace through bills = [5, 5, 5, 10, 20]. We maintain two counters: five for the number of $5 bills and ten for the number of $10 bills in the register.

Every customer was served successfully. The greedy choice at step 5 (using $10 + $5 instead of three $5s) left us with one $5 bill in reserve. If we had used three $5s instead, we would have needed three but only had two. The greedy priority saved us.

The greedy solution

def lemonadeChange(bills):
    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

Two counters, one loop. Here is what each piece does:

1. five and ten track the number of each bill denomination in the register. You do not need to track $20 bills because they are never used as change.
2. If a customer pays $5, no change is needed. Just increment five.
3. If a customer pays $10, you must give back $5. If you have no $5 bills, return false. Otherwise, decrement five and increment ten.
4. If a customer pays $20, you need $15 in change. First try $10 + $5 (greedy preference). If that is not possible, try three $5 bills. If neither works, return false.
5. If you process every customer without returning false, return true.

Complexity analysis

This is optimal. You must inspect each bill at least once to know what change is needed, so O(n) is the lower bound. And O(1) space means no extra data structures beyond the two counters.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Greedy selection

The pattern of making a locally optimal choice at each step that leads to a globally optimal result:

for item in sequence:
    if multiple_options_exist(item):
        choose_option_that_preserves_flexibility()
    else:
        take_only_available_option()

In Lemonade Change, the greedy choice is preferring $10 + $5 over three $5s. In Jump Game, the greedy choice is always extending the farthest reachable index. In Gas Station, the greedy choice is resetting the candidate start when the tank goes negative. The skeleton is the same: process items one at a time and pick the locally best option.

2. Counter tracking

The pattern of maintaining a small number of counters that summarize the state of your resources:

resource_a = 0
resource_b = 0
for item in sequence:
    update_counters(item)
    if cannot_satisfy_constraint():
        return False
return True

In Lemonade Change, the counters are five and ten. In problems like Valid Parentheses, the counter is the depth of open brackets. In majority element problems, the counter tracks candidate frequency. The idea is the same: reduce the full state to a few numbers and check feasibility at each step.

Edge cases

Before submitting, make sure your solution handles these:

• All $5 bills [5, 5, 5, 5]: no change needed for any customer. Always returns true.
• First customer pays $10 [10]: you have no $5 bills to make change. Returns false.
• First customer pays $20 [20]: you have no bills at all. Returns false.
• Alternating $5 and $10 [5, 10, 5, 10]: each $10 customer gets a $5 back. five stays at 0 or 1, ten grows. Returns true.
• Multiple $20s in a row [5, 5, 5, 5, 20, 20]: first $20 uses $10+$5 or three $5s. Second $20 may fail if you spent too many $5s. With four $5s: first $20 takes three $5s (five=1, ten=0), second $20 fails. Returns false.
• Empty array []: no customers, nothing to do. Returns true.

The greedy solution handles all of these without special-case logic.

Common mistakes

1. Preferring three $5s over $10 + $5 for $20 change. This is the most common mistake. If you check five >= 3 before ten > 0 and five > 0, you waste $5 bills that might be needed later for $10 customers.

2. Forgetting to track $10 bills separately. Some people try to use a single counter for total change available. But you need to know specifically how many $10 bills you have, because the greedy choice for $20 change depends on it.

3. Not returning early on failure. If you cannot make change for a customer, you must return false immediately. Continuing to process bills after a failure produces incorrect results.

4. Tracking $20 bills. You never give $20 bills as change (the maximum change needed is $15). Tracking them adds unnecessary complexity.

From understanding to recall

You have read the greedy solution and it makes sense. Three cases, one priority rule, two counters. Clean. But can you write it from scratch in an interview without looking at it?

The details matter: checking ten > 0 and five > 0 before five >= 3, remembering to increment ten when a $10 bill comes in, and returning false at the right moments. These are small but critical, and they are easy to get wrong under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the greedy change-making loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "make change with limited denominations" and the code flows out without hesitation.

The greedy selection pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Jump Game - Another greedy problem where a simple local rule replaces brute-force simulation
• Gas Station - Greedy with running sums and reset logic for circular traversal
• Best Time to Buy and Sell Stock II - Greedy profit collection on every upward price move

CodeBricks breaks the lemonade change LeetCode problem into its greedy selection and counter tracking building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy change-making question shows up in your interview, you do not think about it. You just write it.