Lemonade Change

Problem

Customers pay 5 each for lemonade, in $5, $10, or $20 bills. You start with no money. Return true iff you can give every customer correct change.

Constraints

• 1 ≤ bills.length ≤ 10⁵
• bills[i] ∈ {5,10,20}

Approach — Greedy

This is a Greedy problem. The idea: make the locally best choice at each step, which provably builds up to the global optimum here. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n log n) time.

Solution code

Python

class Solution:
    def lemonadeChange(self, bills):
        five = ten = 0
        for b in bills:
            if b == 5:
                five += 1
            elif b == 10:
                if not five:
                    return False
                five -= 1
                ten += 1
            else:
                if ten and five:
                    ten -= 1
                    five -= 1
                elif five >= 3:
                    five -= 3
                else:
                    return False
        return True

Java

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int fives = 0, tens = 0;
        for (int b : 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;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.