Lemonade Change

NeetCode: Lemonade Change · LeetCode: 860. Lemonade Change · Difficulty: Easy

At a lemonade stand each lemonade costs $5. Customers queue up and each buys one lemonade paying with a $5, $10 or $20 bill. You start with no change and must give every customer the correct change. Return true if you can serve everyone in order.

Example

Text

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

Brute force: try every way of making change

A $5 bill needs no change and a $10 bill needs one $5. A $20 bill needs $15, which can be made two ways: $10 + $5 or $5 + $5 + $5. Backtracking explores both options and succeeds if any sequence of choices serves everyone. Each $20 doubles the branching, so it is O(2^n) in the worst case. $20 bills are never given as change, so only the counts of fives and tens are tracked.

Java

class Solution {
    private boolean go(int[] bills, int i, int fives, int tens) {
        if (i == bills.length) {
            return true;
        }
        switch (bills[i]) {
            case 5:
                return go(bills, i + 1, fives + 1, tens);
            case 10:
                return fives >= 1 && go(bills, i + 1, fives - 1, tens + 1);
            case 20:
                return (tens >= 1 && fives >= 1 && go(bills, i + 1, fives - 1, tens - 1))
                        || (fives >= 3 && go(bills, i + 1, fives - 3, tens));
            default:
                return false;
        }
    }

    public boolean lemonadeChange(int[] bills) {
        return go(bills, 0, 0, 0);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.lemonadeChange(new int[]{5, 5, 5, 10, 20}));
        System.out.println(s.lemonadeChange(new int[]{5, 5, 10, 10, 20}));
        System.out.println(s.lemonadeChange(new int[]{}));
    }
}

Output

true
false
true

Time: O(2^n). Space: O(n) recursion depth.

Java

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int fives = 0;
        int tens = 0;
        for (int b : bills) {
            if (b == 5) {
                fives++;
            } else if (b == 10) {
                if (fives == 0) {
                    return false;
                }
                fives--;
                tens++;
            } else if (b == 20) {
                if (tens > 0 && fives > 0) {
                    tens--;
                    fives--;
                } else if (fives >= 3) {
                    fives -= 3;
                } else {
                    return false;
                }
            } else {
                return false;
            }
        }
        return true;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.lemonadeChange(new int[]{5, 5, 5, 10, 20}));
        System.out.println(s.lemonadeChange(new int[]{5, 5, 10, 10, 20}));
        System.out.println(s.lemonadeChange(new int[]{}));
    }
}

Output

true
false
true

Time: O(n). Space: O(1).