Lemonade Change

At your lemonade stand each glass costs $5. Customers queue up and pay with a $5, $10, or $20 bill; you must give each customer correct change so that their net payment is exactly $5. You start with no change.

Given the bills in the order customers pay, return true if you can give every customer correct change, and false otherwise.

Hints

· Stuck? Reveal one nudge at a time.

Which denominations do you ever actually hand back as change?

A $20 needs $15 back — in one of two ways. Which should you prefer?

Prefer $10 + $5 over three $5s, because $5s are the only change for a $10.

Common doubts

Because $5s are the only bill that makes change for a $10. Spending three of them when a $10 + $5 would do can leave a later $10 customer stranded.

No — a $20 is never used as change, so it's irrelevant once collected. Only $5 and $10 counts matter.

Yes. The moment you can't make a customer's change, no future customer can fix it, so you can return false immediately.

Interview follow-ups

· What an interviewer asks next.

General change-making is no longer safely greedy — for arbitrary coin systems you may need dynamic programming to decide feasibility.

Return the index instead of a boolean: fail at the first bill where the greedy change can't be made.

Fun facts

This is the canonical example of why greedy change works for some denomination systems (like 5/10/20) but not all.
The 'spend the least reusable resource first' heuristic reappears in cache eviction and register allocation.

Asked at

AmazonAdobe

Frequently Sometimes Occasionally

Example 1

Input: bills = [5,5,5,10,20]
Output: true
Collect three $5s, give a $5 change for the $10, then $10+$5 for the $20. Everyone gets change.

Example 2

Input: bills = [5,5,10,10,20]
Output: false
By the $20 customer you hold no $5s (two $10s), so you cannot make $15.

Constraints

- 1 <= bills.length <= 10^5 - bills[i] is either 5, 10, or 20.

You can only make change from bills you've already collected, so the order matters. The whole problem turns on one decision — how to give $15 of change to a $20 customer — and the greedy rule is to spend your least flexible bills last.

Prerequisites

Before you start

· Concepts used directly in the solution.

Simulation. Processing events in order while maintaining a little running state.

Greedy choice. Preferring to spend the bill you have more use for later — here, hoarding $5s.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The rules

“How much change does each bill need?”

A $5 needs none, a $10 needs $5 back, a $20 needs $15 back.

“Do I start with any bills?”

No — your only change comes from earlier customers.

The $20 case

“What are the ways to make $15?”

Either one $10 + one $5, or three $5s. Which you choose is the crux.

The ideal opening — say it like this

I only need to track how many $5 and $10 bills I hold — $20s are never used as change.

A $10 customer costs me a $5; a $20 customer costs me $15.

For the $20 I'll give a $10 + a $5 when I can, saving my $5s, since $5s are the only bill that makes $10 change.

Understand the problem

Worked example — bills = [5, 5, 5, 10, 20]

5  -> five=1
5  -> five=2
5  -> five=3
10 -> give $5   -> five=2, ten=1
20 -> give $10+$5 -> five=1, ten=0     (preferred over three $5s)
served everyone -> true

Key observations

1Aha

Only $5 and $10 are ever change

A $20 is never needed as change, so your entire state is two counters: how many $5s and $10s you hold.

2Aha

The $20 decision is the whole problem

For $15 of change, prefer $10 + $5 over $5 + $5 + $5. Spending the $10 (which has no other use) preserves $5s for future $10 customers.

3Aha

Greedy here is provably safe

Giving away a $5 when a $10 would do can only hurt a later customer, never help. So the greedy choice never forecloses a solution that some other choice would have kept open.

Summary

Key takeaway

Track only your $5 and $10 counts. Give change greedily, and for a $20 always prefer $10 + $5 over three $5s — hoarding $5s, the only bill that can make change for a $10. One pass, constant space.

five = ten = 0
for each bill:
    if 5:  five += 1
    if 10: need a $5 -> if none, fail; else five--, ten++
    if 20: prefer ten-- & five--; else need five>=3; else fail
return true