DSA Tracker

Visualize

Lemonade Change

Greedy change-making with $5 and $10 bills

time O(n)space O(1)

Each lemonade costs $5. A $5 bill gives you change flexibility for any future customer, while a $10 bill can only help make change for a $20 bill. Therefore, the greedy rule is: when a customer gives $10, you must give one $5; when a customer gives $20 (requiring $15 change), always prefer giving one $10 and one $5 over three $5 bills. Preserving valuable $5 bills for future customers is strictly optimal.

Details

Animated on: bills = [5, 5, 5, 10, 20] — determine if you can provide every customer with correct change.

Problem:Lemonade ChangeEasy

Greedy change-making with $5 and $10 bills

step 1 / 9

5
[0]
5
[1]
5
[2]
10
[3]
20
[4]

Start with five=0, ten=0. Customer 0 pays with a $5 bill. No change required.

  • i=0· arr[0] = 5
Pseudocode
1FUNCTION lemonadeChange(bills):
2  five = 0, ten = 0
3  FOR each bill in bills:
4    IF bill is 5: add one to five
5    ELSE IF bill is 10: if no five available RETURN false, else five down one and ten up one
6    ELSE:   (bill is 20, needs $15 change)
7      IF ten > 0 and five > 0: give one ten and one five
8      ELSE IF five >= 3: give three fives
9      ELSE: RETURN false
10  RETURN true

← / → step · space play · Home restart

Every step in words

Show all 9 steps
  1. Start with five=0, ten=0. Customer 0 pays with a $5 bill. No change required.
  2. Collect $5: five count increases to 1, ten=0. Customer satisfied.
  3. Customer 1 pays with $5. No change needed: five becomes 2, ten=0.
  4. Customer 2 pays with $5. No change needed: five becomes 3, ten=0.
  5. Customer 3 pays with $10. Needs $5 change. We have five=3 > 0, so give one $5 bill.
  6. Hand over one $5 in change. Bank now holds five=2, ten=1.
  7. Customer 4 pays with $20 (requires $15 change). Check greedy option: one $10 + one $5 bill.
  8. Greedily give one $10 and one $5 ($15 total), preserving one remaining $5 bill. Updated bank: ten=0, five=1.
  9. All customers served with correct change. Return true.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Lemonade Change in the editorAll Greedy problemsBack to roadmap