LeetCode 860: Lemonade Change

Problem Restatement

Each lemonade costs $5.

Customers stand in a queue. Each customer buys exactly one lemonade and pays with one bill.

The bill can be:

5, 10, or 20

We start with no money.

For each customer, we must give the correct change immediately, using only bills received from earlier customers.

Return True if we can give correct change to every customer. Otherwise, return False.

Input and Output

Function shape:

class Solution:
    def lemonadeChange(self, bills: list[int]) -> bool:
        ...

Examples

Example 1:

bills = [5, 5, 5, 10, 20]

Process the customers in order:

We can serve every customer, so the answer is:

True

Example 2:

bills = [5, 5, 10, 10, 20]

Process the customers:

For the last customer, we have two $10 bills but no $5 bill.

We cannot give exact $15 change, so the answer is:

False

First Thought: Track Total Money

One might try to track only the total money in the register.

That is not enough.

For example, if we have:

two $10 bills

the total is $20, but we still cannot give $15 change because we need either:

$10 + $5

or:

$5 + $5 + $5

So the denominations matter.

We need to count the actual bills.

Key Insight

We only need to track $5 and $10 bills.

A $20 bill is never useful for change, because customers only pay with $5, $10, or $20, and every lemonade costs $5.

When a customer pays:

For a $20 bill, there are two ways to give $15 change:

1. One $10 and one $5
2. Three $5 bills

We should prefer:

$10 + $5

when possible.

This preserves more $5 bills, and $5 bills are the most flexible because they are needed for both $10 and $20 customers.

Algorithm

Maintain two counters:

five = 0
ten = 0

Process each bill in order.

If the bill is 5:

1. Increase five.

If the bill is 10:

1. We need one $5 change.
2. If five == 0, return False.
3. Otherwise, decrease five and increase ten.

If the bill is 20:

1. We need $15 change.
2. If we have one $10 and one $5, use them.
3. Otherwise, if we have at least three $5 bills, use them.
4. Otherwise, return False.

If all customers are processed, return True.

Correctness

The algorithm processes customers in the given order, which is necessary because change can only come from earlier customers.

For a $5 bill, no change is needed, so adding one $5 bill to the register is correct.

For a $10 bill, the only possible exact change is one $5 bill. If no $5 bill is available, serving this customer is impossible. Otherwise, giving one $5 and keeping the $10 bill is forced.

For a $20 bill, exact change is $15. The possible useful combinations are one $10 plus one $5, or three $5 bills. If one $10 and one $5 are available, using them is safe because it preserves two extra $5 bills compared with using three $5 bills. Since future $10 customers require $5 bills, preserving $5 bills cannot make future transactions worse.

If neither valid change combination is available, no exact change can be given, so returning False is correct.

Thus, if the algorithm finishes all customers, every transaction has been served with correct change.

Complexity

Implementation

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:
                if ten > 0 and five > 0:
                    ten -= 1
                    five -= 1
                elif five >= 3:
                    five -= 3
                else:
                    return False

        return True

Code Explanation

We start with no change:

five = 0
ten = 0

When a customer pays with $5:

if bill == 5:
    five += 1

we simply keep the bill.

When a customer pays with $10:

elif bill == 10:

we must return one $5.

If none is available:

if five == 0:
    return False

Otherwise, we give one $5 and keep the $10:

five -= 1
ten += 1

When a customer pays with $20, we first try to give one $10 and one $5:

if ten > 0 and five > 0:
    ten -= 1
    five -= 1

If that is not possible, we try three $5 bills:

elif five >= 3:
    five -= 3

If neither works:

else:
    return False

After all bills are processed, every customer received correct change:

return True

Testing

def test_lemonade_change():
    s = Solution()

    assert s.lemonadeChange([5, 5, 5, 10, 20]) is True
    assert s.lemonadeChange([5, 5, 10, 10, 20]) is False
    assert s.lemonadeChange([5, 10, 5, 5, 20]) is True
    assert s.lemonadeChange([10]) is False
    assert s.lemonadeChange([5, 20]) is False
    assert s.lemonadeChange([5, 5, 5, 20]) is True
    assert s.lemonadeChange([5, 5, 10]) is True

    print("all tests passed")

test_lemonade_change()

Test meaning: