Problem statement

Customers buy lemonade at $5 each, paying with a $5, $10, or $20 bill, one customer at a time in the order of bills. You start with no change.

Return true if you can give every customer correct change.

Example 1

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

Example 2

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

Constraints

• 1 <= bills.length <= 30
• bills[i] is 5, 10, or 20.

Hints for Lemonade Change

1. Hint 1

   Track how many $5 and $10 bills you hold.

2. Hint 2

   For a $20, prefer giving $10+$5 over three $5s — fives are more versatile.

How to solve Lemonade Change

Only two denominations are ever handed back, so the whole state is how many $5s and $10s you hold. The one real decision is how to change a $20, and it should always be $10 + $5 when possible: a $10 can only ever be part of a $20's change, whereas a $5 is needed for both $10 and $20 customers. Spend the inflexible bill first.

Approach

1. Track counts of $5 and $10 bills.
2. A $5 customer needs no change — just bank the note.
3. A $10 customer needs one $5; fail if you have none.
4. A $20 customer needs $15: prefer one $10 plus one $5; otherwise use three $5s; if neither works, fail.
5. Surviving every customer means true.

Why it works

An exchange argument justifies the preference. Suppose an optimal run pays a $20 with three $5s while a $10 was available. Swapping to $10 + $5 leaves you with two more $5s and one fewer $10 — and since a $10 is only ever usable for a $20's change, while those $5s serve both customer types, the swapped state can satisfy every future request the original could. So greedy never forfeits a solution that existed.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Trying three $5s before $10 + $5 is the classic failure — it burns the flexible bills and strands the $10s.
• $20 notes are never given as change, so there is no reason to count them.
• Check availability before decrementing, or the counts go negative and later customers appear serviceable.
• Order matters: the customers must be processed exactly as given.

Reference solution

Python

from typing import List

def lemonadeChange(bills: List[int]) -> bool:
    fives = 0
    tens = 0
    for b in bills:
        if b == 5:
            fives += 1
        elif b == 10:
            if fives == 0:
                return False
            fives -= 1
            tens += 1
        else:
            if tens > 0 and fives > 0:
                tens -= 1
                fives -= 1
            elif fives >= 3:
                fives -= 3
            else:
                return False
    return True

Java

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

C++

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

JavaScript

var lemonadeChange = function(bills) {
    let fives = 0, tens = 0;
    for (const b of bills) {
        if (b === 5) {
            fives++;
        } else if (b === 10) {
            if (fives === 0) return false;
            fives--;
            tens++;
        } else {
            if (tens > 0 && fives > 0) { tens--; fives--; }
            else if (fives >= 3) fives -= 3;
            else return false;
        }
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy