Lemonade Change

Difficulty: Easy Source: NeetCode

Problem

At a lemonade stand, each cup costs $5. Customers pay with $5, $10, or $20 bills. You start with no change. Return true if you can provide every customer with the exact change, false otherwise.

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

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

Constraints:

• 1 <= bills.length <= 10^5
• bills[i] is 5, 10, or 20

Prerequisites

Before attempting this problem, you should be comfortable with:

• Greedy algorithms — making locally optimal choices that lead to a globally correct answer
• Simulation — tracking state as you process each event

1. Brute Force

Intuition

For each customer, just simulate what happens. Track how many $5 and $10 bills you have. If a customer pays $5, no change needed — keep the bill. If they pay $10, give back a $5 (if you have one). If they pay $20, preferably give back a $10 and a $5 (keep $5s for flexibility), otherwise give three $5s. If you can’t make change, return false.

Algorithm

1. Initialise five = 0, ten = 0.
2. For each bill in bills:
   • $5: increment five.
   • $10: if five > 0, decrement five, increment ten. Else return False.
   • $20: prefer ten + five over five * 3. If neither works, return False.
3. Return True.

Solution

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

    return True


print(lemonadeChange([5, 5, 5, 10, 20]))     # True
print(lemonadeChange([5, 5, 10, 10, 20]))    # False
print(lemonadeChange([5, 5, 10]))            # True
print(lemonadeChange([10, 10]))              # False (no $5 to start)

Complexity

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

2. Greedy — Why Prefer $10 When Giving $15 Change

Intuition

This problem has only one real decision point: when giving $15 change (for a $20 bill), should we use $10 + $5 or $5 + $5 + $5? The greedy choice is to prefer $10 + $5. Why? $5 bills are more versatile — they can make change for both $10 and $20 bills. $10 bills can only be used to make change for $20 bills. So we should conserve $5s and spend $10s first when possible. This is the same code as above, just understanding why it works.

Solution

def lemonadeChange(bills):
    five = 0
    ten = 0

    for bill in bills:
        if bill == 5:
            five += 1
        elif bill == 10:
            if not five:
                return False
            five -= 1
            ten += 1
        else:
            # Greedy: use one $10 (less flexible) before using $5s
            if ten and five:
                ten -= 1
                five -= 1
            elif five >= 3:
                five -= 3
            else:
                return False

    return True


print(lemonadeChange([5, 5, 5, 10, 20]))     # True
print(lemonadeChange([5, 5, 10, 10, 20]))    # False
print(lemonadeChange([5, 5, 5, 20]))         # True

Complexity

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

Common Pitfalls

Not tracking $10 bills separately. You might think tracking only $5s is enough, but when giving change for $20 you need to know if you have a $10. Track five and ten as separate counters.

Giving $5 + $5 + $5 before $10 + $5. This is the classic greedy mistake — using more versatile bills when a less versatile one would suffice. Always prefer to spend the $10 first.

Accepting $20 as valid change. $20 bills are never useful as change (lemonade costs $5, so the most change you’d give is $15). You never need to track $20 bills.