Introduction

Lemonade Change is a classic Greedy simulation problem.

You are selling lemonade for:

$5 per lemonade

Customers pay using:

 $5, $10, or $20

Goal:

Return correct change to every customer.

Initially:

 You have no money.

Example

Input

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

Output

true

Explanation

Customer 1 → pays $5Customer 2 → pays $5
Customer 3 → pays $5
Customer 4 → pays $10
Give back $5
Customer 5 → pays $20
Give back $15
All customers receive correct change.

Key Observation

Whenever possible:

Use one $10 bill and one $5 bill instead of three $5 bills.

This preserves more small bills for future transactions.

Algorithm

  1. Maintain count of $5 bills.
  2. Maintain count of $10 bills.
  3. Process customers one by one.
  4. If bill is $5, keep it.
  5. If bill is $10, give one $5 back.
  6. If bill is $20:
    • Prefer $10 + $5 change.
    • Otherwise use three $5 bills.
  7. If change cannot be given, return false.

Dry Run

Input

[5,5,5,10,20]

Customer 1

Receive $5five = 1

Customer 2

Receive $5
five = 2
Customer 3
Receive $5
five = 3

Customer 4

Receive $10
Give $5
five = 2
ten = 1
Customer 5
Receive $20
Give $10 + $5
five = 1
ten = 0
Answer
true

Approach : Greedy

Always try to give larger bills first when returning change.

Using one $10 and one $5 is better than using three $5 bills because it preserves smaller denominations.

Practice

Complexity Analysis

Time Complexity: O(n)Explanation: Each customer is processed exactly once.

Space Complexity: O(1)
Explanation: Only two variables are maintained to store counts of $5 and $10 bills.

Why This Problem is Important

This problem teaches the core Greedy principle of making the best local decision while preserving future possibilities.

Common Beginner Mistakes

  • Giving three $5 bills before trying $10 + $5.
  • Not tracking bill counts correctly.
  • Forgetting impossible change cases.

Interview Tip

Always mention:

Giving one $10 and one $5 is the optimal greedy choice because it preserves more $5 bills for future customers.

Related Questions

  • Assign Cookies
  • Best Time to Buy and Sell Stock II
  • Jump Game
  • Gas Station
  • Candy

Final Takeaway

Lemonade Change is a classic Greedy simulation problem where the key idea is to preserve smaller bills whenever possible. Making the optimal local choice guarantees the correct overall solution.