Can you give change for every customer in an ice-cream queue?

Reported. A December 2023 coding-task post stated the problem in euros. Comments identified it as LeetCode 860, Lemonade Change.

Problem. Each ice cream costs €5. Customers stand in a queue, each buying one, and each pays with a €5, €10 or €20 note. You start with no notes. You must serve customers in order and give exact change from the notes you already hold. Return whether every customer can be served.

Reported examples:

• 5, 5, 5, 10, 20 → true
• 5, 5, 10 → true
• 10, 10 → false
• 10, 5 → false

The post's follow-ups: what if new denominations are added, and how to solve the task if you are given a list of available bank notes.

Approach. The only notes that help later customers are the fives and tens you keep. Count them as you go.

• A €5 needs no change; keep the note.
• A €10 needs one €5.
• A €20 needs €15 of change. Prefer one €10 and one €5, because fives are more flexible later. Only if that is impossible, use three €5 notes.

Greedy is correct here because the denomination set is canonical (each larger note is a multiple of a smaller one). Time O(n), extra space O(1).

public class IceCreamChange {
    static boolean canMakeChange(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 if (bill == 20) {
                if (tens > 0 && fives > 0) { tens--; fives--; }
                else if (fives >= 3) { fives -= 3; }
                else return false;
            } else {
                throw new IllegalArgumentException("unexpected bill: " + bill);
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(canMakeChange(new int[] {5, 5, 5, 10, 20})); // true
        System.out.println(canMakeChange(new int[] {5, 5, 10}));        // true
        System.out.println(canMakeChange(new int[] {10, 10}));          // false
        System.out.println(canMakeChange(new int[] {10, 5}));           // false
        System.out.println(canMakeChange(new int[] {5, 5, 10, 10, 20})); // false
    }
}

Verified with OpenJDK 21.0.13: it prints true, true, false, false and false. The last case is a useful extra: after two tens you hold no fives, so a twenty cannot be changed.

Follow-ups. For a starting stock of notes, seed the counts before the queue. For a larger but still canonical set (for example €5, €10, €20, €50) you can keep a map of counts and, for each customer, make change by always giving the largest possible notes. That greedy is not correct for arbitrary denominations (for example 1, 3 and 4); those need a complete search or DP over the change amount. In an interview, say which case you are in before you write the map version.