Lemonade Change

Problem Description

At a lemonade stand, each lemonade costs $5. Customers are standing in a queue to buy from you and order one at a time (in the order given by bills). Each customer will only buy one lemonade and pay with either a $5, $10, or $20 bill. You must provide the correct change to each customer such that the net transaction is that the customer pays $5.

Note that you do not have any change in hand at first.

Return true if you can provide every customer with the correct change, or false otherwise.

Examples

Constraints

• 1 ≤ bills.length ≤ 10⁵
• bills[i] is either 5, 10, or 20.

Prefer $10 Over $5 When Making Change

Track the count of $5 and $10 bills in hand (we don’t need to track $20 bills because we can never use them as change).

When a customer pays:

• Pays $5: increment the $5 bill count.
• Pays $10: decrement $5 by 1, increment $10 by 1. If we have no $5 bills, return false.
• Pays $20: we need to give $15 back as change. The greedy rule applies:
  • If we have at least one $10 bill and one $5 bill, use them: decrement $10 by 1 and $5 by 1.
  • Otherwise, if we have at least three $5 bills, use them: decrement $5 by 3.
  • Otherwise, return false.

Using a $10 bill first is always optimal because $5 bills are more flexible (a $5 bill can be used for change for both $10 and $20 transactions, whereas a $10 bill is only useful for $20 transactions).

Solution: Greedy Change Tracking

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0, ten = 0;

        for (int bill : bills) {
            if (bill == 5) {
                five++;
            } else if (bill == 10) {
                if (five == 0) return false;
                five--;
                ten++;
            } else { // bill == 20
                if (ten > 0 && five > 0) {
                    ten--;
                    five--;
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}

class Solution:
    def lemonadeChange(self, bills: list[int]) -> bool:
        five = 0
        ten = 0

        for bill in bills:
            if bill == 5:
                five += 1
            elif bill == 10:
                if five == 0:
                    return False
                five -= 1
                ten += 1
            else: # bill == 20
                # prioritize giving a 10 and a 5 as change
                if ten > 0 and five > 0:
                    ten -= 1
                    five -= 1
                elif five >= 3:
                    five -= 3
                else:
                    return False
        return True

#include <vector>

class Solution {
public:
    bool lemonadeChange(std::vector<int>& bills) {
        int five = 0, ten = 0;

        for (int bill : bills) {
            if (bill == 5) {
                five++;
            } else if (bill == 10) {
                if (five == 0) return false;
                five--;
                ten++;
            } else {
                if (ten > 0 && five > 0) {
                    ten--;
                    five--;
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
};

Complexity Analysis:

• Time Complexity: O(N) where N is the length of bills. We loop through the array once.
• Space Complexity: O(1) space.

← All Problems