Problem Description

You're running a lemonade stand where each lemonade costs $5. Customers line up to buy lemonade one at a time, in the order they appear in the input array. Each customer buys exactly one lemonade and pays with either a $5, $10, or $20 bill.

Your task is to determine if you can make correct change for every customer. You start with no money in your cash register.

The key constraints are:

• Each lemonade costs exactly $5
• Customers can pay with $5, $10, or $20 bills
• You must give correct change to each customer (so they effectively pay $5)
• You start with no bills for making change
• You can only use bills received from previous customers to make change

For example:

• If a customer pays with $5, you don't need to give change
• If a customer pays with $10, you need to give back $5
• If a customer pays with $20, you need to give back $15 (which could be three $5 bills or one $10 and one $5)

Given an array bills where bills[i] represents the bill the i-th customer uses to pay, return true if you can successfully provide correct change to all customers, or false if at any point you cannot make the correct change.

The solution tracks the number of $5 and $10 bills available. When making change for a $20 bill, it prioritizes using one $10 and one $5 bill (if available) over using three $5 bills, as this preserves more $5 bills for future transactions.

Intuition

The key insight is that we only need to track the bills we receive, not the total money. Since each lemonade costs $5, we're essentially managing a change-making system.

Let's think through what happens with each type of payment:

• When someone pays with $5: Perfect! No change needed, and we gain a $5 bill for future use
• When someone pays with $10: We need to return $5, so we must have at least one $5 bill available
• When someone pays with $20: We need to return $15 in change

For the $20 case, we have two options for making $15 change:

1. Give one $10 bill + one $5 bill
2. Give three $5 bills

This leads to an important strategic decision: when we have both options available, which should we choose? The greedy approach suggests using option 1 (one $10 + one $5) whenever possible. Why? Because $5 bills are more versatile - they're needed for making change for both $10 and $20 bills, while $10 bills are only useful for $20 bills.

We don't need to track $20 bills at all because they're too large to be useful for making change (we never need to give back $20 or more).

The solution naturally emerges: maintain counters for $5 and $10 bills. Process each customer in order, updating our bill inventory and checking if we have enough bills to make change. If at any point we can't make change (particularly when our $5 bill count goes negative), we return false. If we successfully serve all customers, we return true.

Learn more about Greedy patterns.

Solution Approach

The implementation uses a greedy algorithm with simple counter variables to track our available bills.

We initialize two counters:

• five: tracks the number of $5 bills we have
• ten: tracks the number of $10 bills we have

We process each customer's payment in order:

Case 1: Customer pays with $5

• No change needed
• Increment five counter by 1

Case 2: Customer pays with $10

• Need to give back $5 in change
• Increment ten counter by 1 (we receive a $10 bill)
• Decrement five counter by 1 (we give back a $5 bill)

Case 3: Customer pays with $20

• Need to give back $15 in change
• We apply the greedy strategy:
  • If we have at least one $10 bill available (if ten:), give back one $10 and one $5:
    • Decrement ten by 1
    • Decrement five by 1
  • Otherwise, give back three $5 bills:
    • Decrement five by 3

After handling each customer, we check if five < 0. If it is, we couldn't make proper change for this customer, so we immediately return false.

If we successfully process all customers without the five counter going negative, we return true.

The algorithm runs in O(n) time where n is the number of customers, and uses O(1) space since we only maintain two counter variables regardless of input size.

Example Walkthrough

Let's walk through the solution with the input bills = [5, 5, 10, 10, 20].

We start with five = 0 and ten = 0 (no bills in our cash register).

Customer 1 pays with $5:

• No change needed
• Update: five = 1, ten = 0
• We now have one $5 bill

Customer 2 pays with $5:

• No change needed
• Update: five = 2, ten = 0
• We now have two $5 bills

Customer 3 pays with $10:

• Need to give back $5 in change
• We receive a $10 bill: ten = 1
• We give back a $5 bill: five = 2 - 1 = 1
• Update: five = 1, ten = 1
• Check: five >= 0 ✓ (we successfully made change)

Customer 4 pays with $10:

• Need to give back $5 in change
• We receive a $10 bill: ten = 2
• We give back a $5 bill: five = 1 - 1 = 0
• Update: five = 0, ten = 2
• Check: five >= 0 ✓ (we successfully made change)

Customer 5 pays with $20:

• Need to give back $15 in change
• Greedy decision: Since ten > 0, we prefer giving one $10 + one$5
• We give back one $10 bill: ten = 2 - 1 = 1
• We give back one $5 bill: five = 0 - 1 = -1
• Update: five = -1, ten = 1
• Check: five < 0 ✗ (we cannot make change!)

Since five < 0 after Customer 5, we return false. We don't have enough $5 bills to make proper change for the last customer.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the bills array. The algorithm iterates through the bills array exactly once, performing constant-time operations (arithmetic operations and comparisons) for each bill.

Space Complexity: O(1). The algorithm uses only two integer variables (five and ten) to keep track of the count of $5 and$10 bills, regardless of the input size. No additional data structures that scale with input size are used.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Checking for Negative Bills After Each Transaction

The Pitfall: A common mistake is only checking if you have enough bills before making change, rather than verifying the count remains valid after the transaction. Some implementations might check if five_dollar_count >= 1 before giving change but forget to verify the result isn't negative afterward.

Why It Happens: Developers might assume that checking availability beforehand is sufficient, but when dealing with $20 bills, you might need either 1 or 3 five-dollar bills depending on ten-dollar availability, making pre-checks complex.

Solution: Always check if five_dollar_count < 0 after processing each bill. This unified check handles all cases elegantly:

for bill in bills:
    # ... process bill ...
  
    # Single check after each transaction
    if five_dollar_count < 0:
        return False

2. Incorrect Greedy Strategy for $20 Bills

The Pitfall: When making change for a $20 bill, some might prioritize using three$5 bills to preserve $10 bills, or might not consider both options at all:

# Wrong approach - always uses $5 bills first
if bill == 20:
    if five_dollar_count >= 3:
        five_dollar_count -= 3
    elif ten_dollar_count >= 1 and five_dollar_count >= 1:
        ten_dollar_count -= 1
        five_dollar_count -= 1

Why It Matters: $5 bills are more versatile - they're needed for making change for both$10 and $20 bills.$10 bills can only be used for $20 bills. Using a$10 bill when possible preserves more $5 bills for future transactions.

Solution: Always try to use one $10 and one$5 first, falling back to three $5 bills only when necessary:

if bill == 20:
    if ten_dollar_count > 0:
        # Prefer this option to preserve $5 bills
        ten_dollar_count -= 1
        five_dollar_count -= 1
    else:
        # Fallback when no $10 bills available
        five_dollar_count -= 3

3. Forgetting to Track Received Bills

The Pitfall: Only decrementing bills when making change but forgetting to increment when receiving them:

# Wrong - forgets to add received bills to inventory
if bill == 10:
    five_dollar_count -= 1  # Gives change but doesn't add the $10

Why It Happens: Focus on the "making change" aspect can overshadow the fact that you're also receiving bills that become part of your available change.

Solution: Remember to update your bill inventory for received payments:

if bill == 10:
    ten_dollar_count += 1    # Add the received $10
    five_dollar_count -= 1    # Give $5 as change

4. Over-complicating with $20 Bill Tracking

The Pitfall: Some solutions unnecessarily track $20 bills:

twenty_dollar_count = 0  # Unnecessary
if bill == 20:
    twenty_dollar_count += 1  # Not needed

Why It's Wrong: $20 bills can never be used as change (change amounts are only$5 or $15), so tracking them wastes space and adds complexity.

Solution: Only track bills that can be used as change - $5 and$10 bills. Ignore $20 bills after processing them.