Lemonade Change

Explanation & Solution

Description

At a lemonade stand, each lemonade costs $5. Customers are standing in a queue to buy from you, and they pay with either a $5, $10, or $20 bill (represented by the bills array).

You must provide the correct change to each customer so that the net transaction is that each customer pays $5. Note that you don't have any change in hand at first.

Return true if you can provide every customer with the correct change, or false otherwise.

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

Output: true

Explanation:

Customer 1 pays $5 — no change needed. (fives: 1)
Customer 2 pays $5 — no change needed. (fives: 2)
Customer 3 pays $5 — no change needed. (fives: 3)
Customer 4 pays $10 — give back one $5. (fives: 2, tens: 1)
Customer 5 pays $20 — give back one $10 + one $5. (fives: 1, tens: 0)

Constraints

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

Approach

Greedy Techniques pattern

1. Track Available Bills

Maintain two counters: fives for the number of $5 bills and tens for the number of $10 bills
We don't need to track $20 bills because they are never useful as change

2. Handle Each Customer

$5 bill: No change needed — simply increment fives
$10 bill: Need $5 in change — decrement fives and increment tens. If no $5 bill is available, return false
$20 bill: Need $15 in change — two options exist

3. Greedy Choice for $20 Bills

Option A: Give one $10 + one $5 (preferred — preserves $5 bills which are more flexible)
Option B: Give three $5 bills (fallback if no $10 is available)
If neither option is possible, return false

4. Return the Result

If we successfully process every customer without running out of change, return true

Key Insight

The greedy strategy of preferring to give a $10 bill (over three $5s) when making change for $20 is optimal — $5 bills are more versatile since they can make change for both $10 and $20, while $10 bills can only help with $20

Time

O(n)single pass through the bills array

Space

O(1)only two counters are used

Solution Code

Assign Cookies

Partition Labels