Log inSign up
easyLeetCodeNot Started

Lemonade Change

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Greedy
Solve on LeetCode
Lesson

Problem Statement

At a lemonade stand, each lemonade costs 5. Customers are standing in a queue to buy from you and order one at a time. Each customer will only buy one lemonade and pay with either a 5, 10, or 20 bill.

You must provide the correct change to each customer so that the net transaction is $5.

You begin with no change in hand.

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

Example 1 · Example 1: All change supplied:

Input: bills = [5, 5, 5, 10, 20]
Output: true
Explanation: - From 1st three customers, collect three 5 bills.\n- 4th customer pays 10 -> give one 5 bill (left with two 5 and one 10).\n- 5th customer pays 20 -> give one 10 and one 5 bill (left with one $5).\nAll customers served successfully.

Example 2 · Example 2: Insufficient change:

Input: bills = [5, 5, 10, 10, 20]
Output: false
Explanation: - Collect two 5 bills.\n- For the two 10 bills, give both 5 bills as change.\n- When 20 arrives, no 5 bills remain to provide 15 change -> return false.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the greedy choice property where one denomination dominates another.
  • Recognize why 5 bills are strictly more valuable as change than 10 bills.
  • Implement the two-variable state machine across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Sequential queue transactions requiring exact change.
  • Limited denominations (5, 10, $20) with dominant versatility for smaller denomination.
  • Deterministic local choice maximizing future flexibility.

Algorithmic Decision Tree:

  • Always spend the highest valid denomination first to preserve lower denominations for future flexibility.

Connected Patterns:

Minimum Number of CoinsCoin Change

1. Backtracking Simulation

Intuition

Branch recursively on all valid combinations of coins used for change at each transaction step to find if any combination serves all customers.

Algorithm

  1. Step 1: Define recursive function canServe(idx, fiveCount, tenCount).
  2. Step 2: If idx == n, all customers were served; return true.
  3. Step 3: If bill is $5: recurse with fiveCount + 1.
  4. Step 4: If bill is $10: require fiveCount >= 1; recurse with fiveCount - 1, tenCount + 1.
  5. Step 5: If bill is $20: try (tenCount >= 1 and fiveCount >= 1) branch OR (fiveCount >= 3) branch.
  6. Step 6: Return whether any branch succeeds.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7 bool canServe(int idx, int five, int ten, const vector<int>& bills) {
8 if (idx == bills.size()) return true;
9 int b = bills[idx];
10 if (b == 5) {
11 return canServe(idx + 1, five + 1, ten, bills);
12 } else if (b == 10) {
13 if (five <= 0) return false;
14 return canServe(idx + 1, five - 1, ten + 1, bills);
15 } else { // b == 20
16 // Option 1: give 1 ten and 1 five
17 if (ten >= 1 && five >= 1) {
18 if (canServe(idx + 1, five - 1, ten - 1, bills)) return true;
19 }
20 // Option 2: give 3 fives
21 if (five >= 3) {
22 if (canServe(idx + 1, five - 3, ten, bills)) return true;
23 }
24 return false;
25 }
26 }
27public:
28 bool lemonadeChange(vector<int>& bills) {
29 return canServe(0, 0, 0, bills);
30 }
31};
32
33int main() {
34 Solution sol;
35 vector<int> bills1 = {5, 5, 5, 10, 20};
36 vector<int> bills2 = {5, 5, 10, 10, 20};
37 cout << boolalpha;
38 cout << "bills1: " << sol.lemonadeChange(bills1) << endl;
39 cout << "bills2: " << sol.lemonadeChange(bills2) << endl;
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(2^N)
  • Space complexity: O(N)

2. Frequency Map Simulation

Intuition

Maintain a frequency hash table of bill denominations and simulate change operations greedily.

Algorithm

  1. Step 1: Maintain a map of available bills {5: 0, 10: 0}.
  2. Step 2: For $5 bill: map[5]++.
  3. Step 3: For $10 bill: if map[5] == 0 return false; map[5]--, map[10]++.
  4. Step 4: For $20 bill: if map[10] > 0 and map[5] > 0: map[10]--, map[5]--; else if map[5] >= 3: map[5] -= 3; else return false.
  5. Step 5: Return true if all bills processed.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4
5using namespace std;
6
7class Solution {
8public:
9 bool lemonadeChange(vector<int>& bills) {
10 unordered_map<int, int> counts;
11 for (int b : bills) {
12 if (b == 5) {
13 counts[5]++;
14 } else if (b == 10) {
15 if (counts[5] <= 0) return false;
16 counts[5]--;
17 counts[10]++;
18 } else { // 20
19 if (counts[10] > 0 && counts[5] > 0) {
20 counts[10]--;
21 counts[5]--;
22 } else if (counts[5] >= 3) {
23 counts[5] -= 3;
24 } else {
25 return false;
26 }
27 }
28 }
29 return true;
30 }
31};
32
33int main() {
34 Solution sol;
35 vector<int> bills = {5, 5, 5, 10, 20};
36 cout << boolalpha << "Can provide change: " << sol.lemonadeChange(bills) << endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(1)

3. Greedy Bill Conservation

Intuition

Maintain two integer counters for 5 and 10 bills. When giving 15 change for a 20 bill, greedily use a 10 and a 5 bill before considering three $5 bills.

Algorithm

  1. Step 1: Initialize five = 0, ten = 0.
  2. Step 2: Iterate through each bill in bills.
  3. Step 3: If bill == 5, five++.
  4. Step 4: If bill == 10: if five == 0 return false; five--, ten++.
  5. Step 5: If bill == 20: if ten > 0 and five > 0 (give 10+5): ten--, five--; else if five >= 3 (give 3*5): five -= 3; else return false.
  6. Step 6: Return true if all transactions succeed.

Interactive Trace for Lemonade Change

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Customer pays $5
Visual state
Values and pointers at this exact step
pointers
S
paid
queue
queue
queue
0
↑ customer
1
2
3
Check / comparison
Bill == $5
Decision / next transition
Increment five: five = 1.
Why this step matters

Step 1: Customer pays $5. No change needed. five = 1, ten = 0.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 bool lemonadeChange(vector<int>& bills) {
9 int five = 0, ten = 0;
10 for (int b : bills) {
11 if (b == 5) {
12 five++;
13 } else if (b == 10) {
14 if (five == 0) return false;
15 five--;
16 ten++;
17 } else { // b == 20
18 if (ten > 0 && five > 0) {
19 ten--;
20 five--;
21 } else if (five >= 3) {
22 five -= 3;
23 } else {
24 return false;
25 }
26 }
27 }
28 return true;
29 }
30};
31
32int main() {
33 Solution sol;
34 vector<int> bills1 = {5, 5, 5, 10, 20};
35 vector<int> bills2 = {5, 5, 10, 10, 20};
36 cout << boolalpha;
37 cout << "bills1 result: " << sol.lemonadeChange(bills1) << endl;
38 cout << "bills2 result: " << sol.lemonadeChange(bills2) << endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Full State BacktrackingO(2^N)O(N)Recursively branch on both ways to give change for $20 (either 10+5 or 5+5+5) to check if any path satisfies all customers.Branching on $20 change.
2.Better — Frequency Map / Multiset SimulationO(N)O(1) (fixed map of 3 keys)Use a hash map or frequency array to store available counts of bills and execute greedy change deduction.Hash map operations.
3.Optimal — Two Counter Greedy SimulationOptimalO(N)O(1)Track two integer variables: five and ten. For $20, greedily decrement ten and five if ten > 0; otherwise decrement three fives. Return false immediately if count drops below zero.Single linear pass.
Back to DSA Sheet