Definition
- Lemonade Change – a greedy problem where a cashier starting with an empty till must decide whether every customer in a queue can receive correct change for a fixed-price item.
- Note tracking – only five-unit and ten-unit counts matter because twenty-unit notes are never returned as change.
- Greedy rule – when fifteen units of change are needed, prefer giving one ten plus one five over three fives, preserving the more flexible small notes.
- Immediate failure – the algorithm returns
falsethe instant any required change cannot be formed from available notes. - Complexity – O(n) time for a single scan and O(1) space for two integer counters.
At the National Bank of India branch counter, Priya pays a fixed five-unit service fee using whatever note she has. The teller starts the day with an empty cash drawer and must return exact change from notes collected from earlier customers. The teller always hands back the largest notes first so the flexible small notes stay in reserve for future customers.
Understanding the Concepts
What is the Lemonade Change problem?
Lemonade Change asks whether a cashier who starts with no money can give correct change to every customer in a queue. Each customer buys an item that costs five units and pays with a five-unit, ten-unit, or twenty-unit note. The cashier must return exact change using only the notes collected from earlier customers.
package com.bank.service;
public class LemonadeChange {
public boolean canMakeChange(int[] payments) {
int fives = 0, tens = 0;
for (int pay : payments) {
if (pay == 5) {
fives++;
} else if (pay == 10) {
if (fives == 0) return false;
fives--;
tens++;
} else { // pay == 20
if (tens > 0 && fives > 0) {
tens--;
fives--;
} else if (fives >= 3) {
fives -= 3;
} else {
return false;
}
}
}
return true;
}
}
Why does the greedy strategy work here?
The greedy strategy works because five-unit notes are strictly more flexible than ten-unit notes. A five-unit note can satisfy change for both ten-unit and twenty-unit payments, but a ten-unit note can only help with twenty-unit payments. By spending the less flexible resource first (tens) and hoarding the more flexible resource (fives), we maximise our ability to serve future customers. This is provably optimal because no alternative spending order can increase the number of customers served.
package com.bank.service;
public class GreedyProof {
public static void main(String[] args) {
// Sequence: 5, 5, 10, 20
// After 5: fives=1, tens=0
// After 5: fives=2, tens=0
// After 10: fives=1, tens=1 (gave one five as change)
// After 20: needs 15 change
// Greedy: give ten+five -> fives=0, tens=0 -> SUCCESS
// Alt: give three fives -> only have 1 five -> FAIL
int[] payments = {5, 5, 10, 20};
LemonadeChange lc = new LemonadeChange();
System.out.println("Can serve all: " + lc.canMakeChange(payments));
// Output: Can serve all: true
}
}
How does the algorithm handle each payment type?
There are three cases depending on the note a customer presents. A five-unit payment requires no change, so we simply increment the five-unit counter. A ten-unit payment requires five units of change, so we must have at least one five-unit note to give back. A twenty-unit payment requires fifteen units of change, and we have two options: give one ten plus one five, or give three fives.
package com.bank.service;
public class PaymentCases {
public static void demonstrateCases() {
// Case 1: Five-unit payment, no change needed
int fives = 0;
fives++; // fives = 1
System.out.println("After 5-unit pay: fives=" + fives);
// Case 2: Ten-unit payment, give back one five
fives--; // fives = 0
int tens = 1;
System.out.println("After 10-unit pay: fives=" + fives + ", tens=" + tens);
// Case 3a: Twenty-unit payment, prefer ten + five
fives = 2; tens = 1;
tens--; fives--; // use ten + five
System.out.println("After 20-unit (ten+five): fives=" + fives + ", tens=" + tens);
// Case 3b: Twenty-unit payment, fallback three fives
fives = 4; tens = 0;
fives -= 3; // use three fives
System.out.println("After 20-unit (3 fives): fives=" + fives + ", tens=" + tens);
}
}
After 5-unit pay: fives=1
After 10-unit pay: fives=0, tens=1
After 20-unit (ten+five): fives=1, tens=0
After 20-unit (3 fives): fives=1, tens=0
What is the time and space complexity?
The algorithm makes a single pass through the payments array, processing each customer in constant time. It uses only two integer variables to track the note counts.
- Time complexity – O(n) where n is the number of customers.
- Space complexity – O(1) because we only store two counters regardless of input size.
- No sorting – unlike many greedy problems, this one processes customers in arrival order without any sorting step.
// Single pass: each of n customers processed in O(1)
// Total: O(n) time, O(1) space
for (int pay : payments) {
// constant-time branching and counter updates
}
What are the edge cases?
Several edge cases deserve attention. An empty queue returns true because there is nothing to serve. A queue of only five-unit payments always succeeds because no change is ever needed. A queue starting with a ten or twenty fails immediately because the till is empty.
package com.bank.service;
public class EdgeCases {
public static void main(String[] args) {
LemonadeChange lc = new LemonadeChange();
// Edge 1: empty queue
System.out.println(lc.canMakeChange(new int[]{})); // true
// Edge 2: all fives
System.out.println(lc.canMakeChange(new int[]{5,5,5})); // true
// Edge 3: first customer pays 10
System.out.println(lc.canMakeChange(new int[]{10})); // false
// Edge 4: first customer pays 20
System.out.println(lc.canMakeChange(new int[]{20})); // false
// Edge 5: barely fails
System.out.println(lc.canMakeChange(new int[]{5,5,10,10,20})); // false
}
}
true
true
false
false
false
What are common mistakes?
The most common mistake is not preferring the ten-plus-five option over three fives when making fifteen units of change. Another mistake is tracking twenty-unit note counts, which are unnecessary since twenties are never given as change.
// WRONG: using three fives before trying ten + five
if (pay == 20) {
if (fives >= 3) {
fives -= 3; // wastes fives!
} else if (tens > 0 && fives > 0) {
tens--; fives--;
} else {
return false;
}
}
// CORRECT: prefer ten + five to conserve fives
if (pay == 20) {
if (tens > 0 && fives > 0) {
tens--; fives--; // spend the less flexible note first
} else if (fives >= 3) {
fives -= 3;
} else {
return false;
}
}
How is this different from a general coin change problem?
Lemonade Change is simpler than the general coin change problem because the denominations and the item price are fixed. In general coin change, we may need dynamic programming to find the minimum number of coins or even determine feasibility. Here the fixed structure allows a direct greedy rule.
| Aspect | Lemonade Change | General Coin Change |
|---|---|---|
| Denominations | Fixed: 5, 10, 20 | Arbitrary set |
| Strategy | Greedy (provably optimal) | DP required for general case |
| Complexity | O(n) time, O(1) space | O(n * amount) time |
| Change amounts | Only 0, 5, or 15 | Any target amount |
// Lemonade: direct greedy with fixed cases
if (pay == 5) fives++;
else if (pay == 10) { fives--; tens++; }
else { tens--; fives--; } // or fives -= 3
// General coin change: needs DP
// dp[i] = min coins to make amount i
for (int coin : coins)
for (int i = coin; i <= amount; i++)
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
How would you apply this in a banking system?
At the National Bank of India, a branch counter collects a fixed processing fee from each customer using whatever denomination note they have. The teller starts the day with an empty till and must return exact change from notes collected earlier. Before opening the branch, the system runs the greedy check on the expected customer payment sequence to verify whether the teller can serve everyone without a change shortage.
package com.bank.service;
import java.util.List;
public class BranchCounterService {
public boolean canServeAllCustomers(List<Integer> customerPayments) {
int fiveNotes = 0, tenNotes = 0;
for (int payment : customerPayments) {
if (payment == 5) {
fiveNotes++;
} else if (payment == 10) {
if (fiveNotes == 0) return false;
fiveNotes--;
tenNotes++;
} else if (payment == 20) {
if (tenNotes > 0 && fiveNotes > 0) {
tenNotes--;
fiveNotes--;
} else if (fiveNotes >= 3) {
fiveNotes -= 3;
} else {
return false;
}
}
}
return true;
}
}
What should a senior engineer know?
A senior engineer should know that the greedy preference for spending tens before fives is provably optimal via an exchange argument. If any valid solution spent three fives instead of a ten-plus-five, we could swap without reducing the count of served customers. The problem also illustrates a broader pattern: when resources have different flexibility levels, always spend the least flexible resource first.
// Exchange argument:
// Suppose solution S uses 3 fives for a 20-unit customer.
// If S also has a ten available, swap to ten+five.
// This frees 2 fives for future use without harming any prior customer.
// Therefore, preferring ten+five is at least as good as 3 fives.
What are common interview follow-up questions?
Interviewers often ask these follow-ups after the main solution:
- What if the item cost is not five but an arbitrary value?
- What if customers can pay with additional denominations like fifty?
- What if the cashier starts with some initial float?
- Can you prove the greedy is optimal using an exchange argument?
- What if you need to return the minimum number of notes as change?
// Follow-up: cashier starts with initial float
public boolean canMakeChangeWithFloat(int[] payments, int initFives, int initTens) {
int fives = initFives, tens = initTens;
for (int pay : payments) {
if (pay == 5) fives++;
else if (pay == 10) {
if (fives == 0) return false;
fives--; tens++;
} else {
if (tens > 0 && fives > 0) { tens--; fives--; }
else if (fives >= 3) fives -= 3;
else return false;
}
}
return true;
}
Visual Overview
Customer Queue: [5] [5] [5] [10] [20]
│ │ │ │ │
▼ ▼ ▼ ▼ ▼
Till State: ┌──────────────────────────────────────┐
│ Pay=5 │ fives=1 tens=0 change=0 │
│ Pay=5 │ fives=2 tens=0 change=0 │
│ Pay=5 │ fives=3 tens=0 change=0 │
│ Pay=10 │ fives=2 tens=1 change=5 │
│ Pay=20 │ fives=1 tens=0 change=15 │
└──────────────────────────────────────┘
Result: true (all served)
Greedy Decision for 20-unit payment (needs 15 change):
Option A (preferred): Option B (fallback):
┌─────────┐ ┌─────────┐
│ 10 + 5 │ saves fives │ 5+5+5 │ wastes fives
└─────────┘ └─────────┘
│ │
▼ ▼
Fives preserved Fives depleted
for future 10s future 10s may fail
Key Takeaway
Lemonade Change is a greedy problem where the key insight is that not all notes are equally useful. I track running counts of the five-unit and ten-unit notes I hold, and I ignore the twenty-unit notes for change because they are never handed back. A five-unit payment needs no change, a ten-unit payment needs a single five, and a twenty-unit payment needs fifteen, which I can make either as a ten plus a five or as three fives.
The greedy decision that makes this correct is to always prefer giving a ten plus a five over three fives when I owe fifteen. Fives are the scarce, flexible currency because every ten-unit payment consumes one, so I hoard them by spending larger notes first. This is provably optimal through an exchange argument: if any valid solution used three fives where a ten-plus-five was available, we could swap without reducing the number of customers served.
The algorithm makes a single pass through the customer queue using only two integer counters, giving O(n) time and O(1) space. Edge cases include an empty queue (trivially true), a queue starting with a ten or twenty (immediate failure), and sequences that barely fail when the last customer drains all remaining fives.
At the National Bank of India, I used this exact logic at a branch counter for a fixed-fee service where the till started empty and had to return exact change to customers in arrival order. The greedy check confirmed whether a given arrival sequence could be fully served and alerted staff before a change shortage occurred.
Remember one sentence: prefer spending the least flexible resource first, so for fifteen units of change, give a ten plus a five before giving three fives.
---