LeetCode #860 Easy

Lemonade Change

Each lemonade costs $5 and customers pay with $5, $10, or $20 bills. Serving them in order, return whether you can give correct change to everyone.

greedyarray

Open on LeetCode ↗

02

Intuition

💡

There is exactly one decision in this problem, and it is where people lose it: giving $15 back for a $20. Three fives works and feels natural. It is wrong. A ten can only ever serve a twenty, while a five serves both tens and twenties — so burning three flexible notes to save a rigid one strands you later. Spend the ten. Everything else here is forced, and a twenty is never change at all, so two counters cover the whole problem.

03

Approach

1

Notice that twenties are dead weight

Change is only ever given in fives and tens, so a $20 bill enters the till and never leaves it. Tracking it would be wasted state; two counters describe everything that matters.

2

Handle the forced cases

A $5 needs no change — take it and the five count rises. A $10 needs exactly $5 back, and the only way to make that is one five, so there is no choice to make: if no five is available, fail immediately.

3

Make the greedy choice on $20

A $20 needs $15 back: a ten plus a five, or three fives. Always prefer the ten. The exchange argument: any solution paying with three fives can be rewritten to use the ten instead without getting worse, since the ten has no other use. Hand out the specialised note, hoard the versatile one. Try it on [5,5,5,10,20] — pay the twenty with three fives and the next ten has nothing to draw on. One pass, O(n) time and O(1) space.

04

Solution & live demo

python

▶1class Solution:
▶2    def lemonadeChange(self, bills):
▶3        five = ten = 0
▶4        for b in bills:
▶5            if b == 5:
▶6                five += 1
▶7            elif b == 10:
▶8                if five == 0:
▶9                    return False
▶10                five -= 1
▶11                ten += 1
▶12            else:
▶13                if ten > 0 and five > 0:
▶14                    ten -= 1
▶15                    five -= 1
▶16                elif five >= 3:
▶17                    five -= 3
▶18                else:
▶19                    return False
▶20        return True

05

Edge cases

First customer pays with $10 or $20

The till is empty, so change is impossible and the answer is false on the first step.

All customers pay with $5

No change is ever needed; the answer is true.

Giving three fives when a ten was available

The greedy rule prevents this; doing it can strand a later $20 that only a ten could have helped serve.

Exactly enough change throughout

Handled naturally — the counters simply reach zero at the end.

06

Complexity

Time

O(n)

Space

O(1)

Two integer counters. The greedy choice needs an exchange argument to justify, but no extra state.