☕ DSA Java Articles

Topics › Greedy Algorithms › Easy Problems

Lemonade Change

Easy TUF ID 543 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You run a lemonade stand where each lemonade costs $5. Customers stand in a queue and are served in order; customer i buys exactly one lemonade and pays with a single bill bills[i], which is 5, 10 or 20. You start with no money at all, and the only cash you can use for change is what earlier customers paid you. Return true if you can give every customer the correct change, otherwise false.

Constraints: 1 ≤ n ≤ 10^5, and every bills[i] is one of 5, 10, 20.

Example 1

bills = [5, 5, 5, 10, 20]
answer = true       // keep three 5s, give a 5 back for the 10, give 10 + 5 back for the 20

Example 2

bills = [5, 5, 10, 10, 20]
answer = false      // before the 20 arrives the drawer holds two 10s and no 5, so 15 cannot be made

What the drawer really needs to remember

Change is always bill - 5, so it is 0, 5 or 15. A $20 bill can never be part of any change (it is bigger than 15), so we never need to track how many 20s we hold. The whole state is just two counters: fives and tens.

The only decision in the whole problem is which of those two ways to use for a 20. That is what the approaches disagree on.

Approach 1: Brute force, try both ways for every 20

Intuition. If we do not know which way of making 15 is better, try both. Write a recursive function canServe(i, fives, tens) that answers “starting at customer i with this drawer, can everybody be served?”. For a 20 it tries 10 + 5 and, if that branch fails, 5 + 5 + 5.

Algorithm.

  1. If every customer has been served (i == n), return true.
  2. For a 5, recurse with one more five.
  3. For a 10, fail if there is no five; otherwise recurse with one five fewer and one ten more.
  4. For a 20, try each legal way of giving 15 and return true if any branch succeeds.
static boolean bruteForce(int[] bills) {
    return canServe(bills, 0, 0, 0);
}

static boolean canServe(int[] bills, int i, int fives, int tens) {
    if (i == bills.length) return true;
    if (bills[i] == 5) return canServe(bills, i + 1, fives + 1, tens);
    if (bills[i] == 10) return fives > 0 && canServe(bills, i + 1, fives - 1, tens + 1);
    // a 20 needs 15 back: either 10 + 5 or 5 + 5 + 5
    boolean ok = false;
    if (tens > 0 && fives > 0) ok = canServe(bills, i + 1, fives - 1, tens - 1);
    if (!ok && fives >= 3) ok = canServe(bills, i + 1, fives - 3, tens);
    return ok;
}

Complexity. Time O(2^k) in the worst case, where k is the number of 20s, because each one can split the search in two. Space O(n) for the recursion stack, so a queue of 10^5 customers could overflow the default Java stack. This version is useful as a reference to test the greedy against, not as a submission.

Approach 2: Optimal, greedy counting

Intuition. Look at what the two options cost: 10 + 5 spends one ten and one five, 5 + 5 + 5 spends three fives. A 5 is the more flexible bill: it is needed for every 10 customer and can also be used for 20 customers, while a 10 is only ever useful as change for a 20. So whenever we have a ten available, spend it and keep the fives.

Why this never hurts: after 10 + 5 the drawer is (fives - 1, tens - 1); after 5 + 5 + 5 it is (fives - 3, tens). The first drawer has two extra fives and one fewer ten. Whatever the second drawer can do in the future, the first can do too: any time the second hands out that extra ten (always as part of 10 + 5 for a 20), the first can hand out two of its extra fives instead. So choosing 10 + 5 first is always at least as good, and the search tree from Approach 1 collapses to a single path.

Algorithm.

  1. Set fives = 0, tens = 0.
  2. For each bill:
    • 5: fives++.
    • 10: if fives == 0 return false; else fives--, tens++.
    • 20: if tens > 0 && fives > 0, spend one of each; else if fives >= 3, spend three fives; else return false.
  3. Return true.
static boolean optimal(int[] bills) {
    int fives = 0, tens = 0;
    for (int bill : bills) {
        if (bill == 5) {
            fives++;
        } else if (bill == 10) {
            if (fives == 0) return false;
            fives--;
            tens++;
        } else {                        // bill == 20
            if (tens > 0 && fives > 0) {
                tens--;
                fives--;
            } else if (fives >= 3) {
                fives -= 3;
            } else {
                return false;
            }
        }
    }
    return true;
}

Dry run on bills = [5, 5, 5, 5, 10, 20, 10, 10], a queue built to punish the wrong preference:

bill change given fives tens
5 none 1 0
5 none 2 0
5 none 3 0
5 none 4 0
10 5 3 1
20 10 + 5 2 0
10 5 1 1
10 5 0 2

Every customer is served, so the answer is true. Had we paid the 20 with three fives, the drawer would have been (1, 1), the next 10 would leave (0, 2), and the last 10 would find no five to give back.

Complexity. Time O(n): one pass, constant work per customer. Space O(1): two counters.

Edge cases and pitfalls