Lemonade Change

How it works

This is a cleaner version of the same greedy approach. Instead of checking conditions before decrementing, we optimistically make the change and then verify if the $5 count went negative. This simplifies the code by deferring the validity check to a single condition after each transaction.

Steps

1. Track 5` and 10` bill counts.
2. For each bill:
   • If 5`: increment the 5` count.
   • If 10`: decrement 5, increment ``10.
   • If 20` and we have a 10: decrement both ``5 and ``10`.
   • If 20` and no 10: decrement ``5 by 3.
3. After each transaction, check if the $5 count is negative. If so, return false.
4. Return true after processing all customers.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Using Three 5` Bills Before One 10 and One ``5

When giving 15` change for a 20 bill, you should prefer using one ``10 and one 5` over three 5 bills. The ``5 bills are more versatile since they can be used for both 5` and 10 change scenarios. Using three ``5 bills depletes your flexibility for future transactions.

Not Tracking the ``10` Bill Count

Some solutions only track 5` bills, assuming 10 bills are not useful. However, ``10 bills are essential for efficiently making $15 change. Failing to track them means you cannot implement the optimal greedy strategy and may incorrectly return false when change is actually possible.

from typing import List

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five, ten = 0, 0
        for b in bills:
            if b == 5:
                five += 1
            elif b == 10:
                five, ten = five - 1, ten + 1
            elif ten > 0:
                five, ten = five - 1, ten - 1
            else:
                five -= 3
            if five < 0:
                return False
        return True

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