AlgoViz
HomeGreedy

Lemonade Change

Easy

Spend the largest bills you can

Problem

Customers pay with $5, $10, or $20 bills for a $5 lemonade. Return true if you can give correct change to everyone in order, starting with none.

In simple words

Give change greedily, always handing back the biggest bills first to keep small change in reserve.

The idea

Track how many $5 and $10 notes you hold. When giving change for a $20, prefer a $10 plus a $5 over three $5s, because $5 notes are useful for more situations and $10s are not.

The trick

  • Give the $10 + $5 combination first; keep $5s in reserve.
  • Never need to track $20s — they are never given as change.
  • Fail as soon as the required change cannot be made.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

5
5
5
10
20
0
1
2
3
4

Step 1 of 2. Here's the example — [5,5,5,10,20] Values: 5, 5, 5, 10, 20.

1/2
Optimal
timeO(n)spaceO(1)
1five=ten=02for bill in bills:3  if bill==5: five++4  elif bill==10: five--; ten++5  else: if ten>0: ten--; five-- else five-=36  if five<0: return false7return true

Input

array
[5, 5, 5, 10, 20]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
bills = [5, 5, 5, 10, 20]
Output:
true
Explanation:
You always have change ready.

Example 2

Input:
bills = [5, 5, 10, 10, 20]
Output:
false
Explanation:
You run out of change for the 20 → false.

Example 3

Input:
bills = [10, 10]
Output:
false
Explanation:
No 5 to start → can't give change.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.