Greedy Algorithm: Lemonade Change

Welcome to PlayBook Library. This comprehensive study note covers the Lemonade Change problem, a classic interview question that demonstrates the core principles of Greedy Algorithms. We will break down the problem statement, examine concrete examples, analyze the step-by-step decision-making process, construct pseudocode, and evaluate time and space complexity.

1. Why Do We Need This? (Problem Statement & Status Quo)

Imagine you operate a lemonade stand at a local event. Every cup of lemonade costs $5**. Customers stand in a line, and each customer buys **exactly one cup** of lemonade. However, customers pay with different bill denominations: **$5, $10**, or **$20.

You start your shift with zero money in your register ($0$ dollars of $5$ bills, $0$ of $10$ bills, and $0$ of $20$ bills).

• If a customer hands you a $5 bill, you simply hand them the lemonade and keep the$5 bill. No change is required.
• If a customer hands you a $10 bill, you must hand them the lemonade **plus$5 in change**.
• If a customer hands you a $20 bill, you must hand them the lemonade **plus$15 in change**.

Given an array representing the bills handed to you by $n$ customers in sequential order, your objective is to determine whether you can successfully provide lemonade and exact change to every single customer. If you can serve everyone successfully, return true. If at any point you lack the correct denominations to make change, you must immediately halt and return false.

2. Core Mental Model & Greedy Strategy

The fundamental mental model for this problem revolves around prioritizing smaller denominations when making change, because smaller bills are much more versatile for future customers.

Real-Life Analogy

Analogy (The Cash Register Vault): Think of your cash register as having limited slots. A $5 bill is your most valuable asset because *everyone* who needs change requires a$5 bill (either alone or combined with a $10 bill to make$15). A $20 bill is practically useless for giving change because nobody costs negative dollars. Therefore, whenever you receive a$20 bill, your greedy instinct should be: "Get rid of larger, less flexible change first ($10 +$5), and preserve pure $5 bills as long as possible."

Why Greedy Works Here

At each step, you make the locally optimal choice that maximizes your flexibility for the future:

1. For $5 bills: Always accept and store them. They require no change and provide maximum future utility.
2. **For $10 bills:** Accept the$10 bill, store it, and greedily check if you have at least one $5 bill to give back as change.
3. **For $20 bills:** You owe$15 in change. You have two valid ways to make $15:
   • Preferred greedy choice: One $10 bill + One$5 bill (saving your remaining $5 bills).
   • Fallback choice: Three $5 bills (if you don't have a$10 bill).

3. Step-by-Step Evolution of Examples

Let's walk through two distinct customer sequences to visualize how our register state changes over time.

Example 1: Successful Transactions (true)

Customer Queue: [5, 5, 5, 10, 20]

Example 2: Failed Transaction (false)

Customer Queue: [5, 5, 10, 10, 20]

4. Handling Denominations & State Tracking

To implement this algorithm efficiently, we do not need complex data structures. We only need two integer counters to track our bill inventory:

5. Algorithmic Pseudocode

Here is the clean, production-ready pseudocode implementing the greedy strategy:

def lemonadeChange(bills):
    five = 0
    ten = 0
    
    for bill in bills:
        if bill == 5:
            five += 1
            
        elif bill == 10:
            if five > 0:
                five -= 1
                ten += 1
            else:
                return False  # Cannot give $5 change
                
        else:  # bill == 20
            # Greedily try to give $15 as (one $10 + one $5) first
            if ten > 0 and five > 0:
                ten -= 1
                five -= 1
            # Otherwise, try to give $15 as three $5 bills
            elif five >= 3:
                five -= 3
            else:
                return False  # Cannot give $15 change
                
    return True

6. Complete Flow Walkthrough

Let's trace how the execution flows when encountering each bill type:

7. Complexity Analysis

• Time Complexity: $\mathcal{O}(n)$, where $n$ is the number of customers (length of the bills array). We iterate through the customer queue exactly once, performing constant-time $\mathcal{O}(1)$ arithmetic checks for each bill.
• Space Complexity: $\mathcal{O}(1)$. We only store two integer variables (five and ten) regardless of how long the customer queue is, requiring constant auxiliary space.

8. Summary and Key Takeaways

• Greedy Choice Property: Always prioritize using a $10 bill combined with a$5 bill when giving $15 in change, saving pure$5 bills for future transactions.
• Minimal State Required: We only need to track $5 and$10 bills because $20 bills are never handed back as change to customers.
• Early Exit: The algorithm terminates and returns false the exact moment a required change denomination is unavailable.
• Optimal Efficiency: Achieves optimal linear time complexity ($\mathcal{O}(n)$) and constant space complexity ($\mathcal{O}(1)$).
• Practical Interview Pattern: Demonstrates how simple local greedy decisions prevent future invalid states in resource-allocation problems.