Lemonade Change

Customers pay $5, $10, or $20 for $5 lemonade. Determine if you can give everyone correct change.

Example 1

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

Example 2

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

Solution Approach

Track $5 and $10 bills. For $20, prefer to give $10+$5 change before $5+$5+$5.

Keep count of fives and tens
For $5 bill: fives++
For $10 bill: need one $5 (fives--), tens++
For $20 bill: prefer tens+fives, else 3*fives
If any count < 0 return false

Java

public boolean lemonadeChange(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 (tens > 0 && fives > 0) { tens--; fives--; }
            else if (fives >= 3) fives -= 3;
            else return false;
        }
    }
    return true;
}

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