Lemonade Change solution and explanation
Google
TCS
9 more videos on this problem
L2. Lemonade Change | Greedy Algorithm Playlisttake U forward · 9:00 · 166K views
Lemonade Change - Leetcode 860 - PythonNeetCodeIO · 10:37 · 11K views
LeetCode Lemonade Change Solution Explained - JavaNick White · 3:42 · 7K views
Lemonade Change | Leetcode 860 | codestorywithMIKcodestorywithMIK · 10:53 · 7K views
DSA in Python - Lemonade Change | Greedy Solution | Leetcode 860 - Part 101 [Hindi]Code and Debug · 11:13 · 2K views
860. Lemonade Change | Leetcode | Easy | Java | Greedy Algorithm | Striver's A to Z DSA Sheet/CourseAlgorithmHQ · 6:31 · 1K views
Lemonade Change | Leetcode 860 | Amazon Google Facebook interview questionSuper Lazy Coder · 7:05 · 539 views
860. Lemonade Change || #leetcode #solution || IN #javaLearn2Master · 14:33 · 354 views
Leetcode 860. Lemonade Change Explained | Best DSA Course- Greedy 2 in JAVAGET PLACED SOON · 5:32 · 157 views
Leetcode 860 Lemonade Change | Simple Solution | C# |Rikam Palkar · 1:43 · 155 views
The problem
At a lemonade stand, each lemonade costs $5. Customers are standing in a queue to buy from you and order one at a time (in the order specified by bills). 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 that the customer pays $5.
Note that you do not have any change in hand at first.
Given an integer array bills where bills[i] is the bill the ith customer pays, return true if you can provide every customer with the correct change, or false otherwise.
Example 1:
Input: bills = [5,5,5,10,20] Output: true Explanation: From the first 3 customers, we collect three $5 bills in order. From the fourth customer, we collect a $10 bill and give back a $5. From the fifth customer, we give a $10 bill and a $5 bill. Since all customers got correct change, we output true.
Example 2:
Input: bills = [5,5,10,10,20] Output: false Explanation: From the first two customers in order, we collect two $5 bills. For the next two customers in order, we collect a $10 bill and give back a $5 bill. For the last customer, we can not give the change of $15 back because we only have two $10 bills. Since not every customer received the correct change, the answer is false.
Constraints:
1 <= bills.length <= 105bills[i]is either5,10, or20.
Approach overview
Problem Overview: You run a lemonade stand where each lemonade costs $5. Customers pay with $5, $10, or $20 bills in a given order. After every transaction you must return the correct change using only the bills you have received so far. The task is to determine whether you can serve every customer successfully.
Approach 1: Greedy with Bill Counting (O(n) time, O(1) space)
This problem is a classic greedy decision scenario. You only need to track how many $5 and $10 bills you currently hold. Iterate through the input array of payments and simulate each transaction. When a customer pays with $10, give one $5 as change. When they pay with $20, prioritize giving $10 + $5 if possible because it preserves smaller bills for future transactions; otherwise give three $5 bills. If neither option exists, the transaction fails. The greedy insight is that larger bills should be used for change first when possible to keep more flexible denominations available later.
This works because each decision only affects future flexibility, not past transactions. The algorithm performs a single pass through the array while maintaining two counters. No additional data structures are required, making the space usage constant.
Approach 2: Simulation with Priority Change Strategy (O(n) time, O(1) space)
This method explicitly simulates the cashier behavior and prioritizes higher denomination change using a structured strategy. Track counts of $5, $10, and optionally $20 bills. For each payment, compute the required change and attempt to fulfill it by greedily subtracting the largest available denominations first (for example $10 before $5). The process mirrors how a real register might compute change.
Although the behavior is similar to the greedy approach, this version frames the logic as a small change-making routine rather than a direct rule set. You repeatedly deduct bills from your counts until the required change is satisfied or impossible. The complexity remains linear because each transaction involves only a few constant-time checks.
Recommended for interviews: The greedy bill counting approach is what interviewers expect. It shows that you recognize the optimal strategy of preserving smaller denominations and can reason about local decisions leading to a globally valid solution. The simulation approach demonstrates the same idea but with slightly more overhead. Candidates who first describe the greedy reasoning and then implement the constant-space counters usually produce the cleanest solution.
Approach 1: Greedy with Bill Counting
This approach involves using a greedy strategy where we maintain counters for $5 and $10 bills. When a $5 bill is received, simply increase the count. For a $10 bill, check if you have a $5 bill to give as change. For a $20 bill, prefer giving one $10 and one $5 bill as change if available, otherwise give three $5 bills.
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
five, ten = 0, 0
for bill in bills:
if bill == 5:
five += 1
elif bill == 10:
if five == 0:
return False
five -= 1
ten += 1
else:
if ten > 0 and five > 0:
ten -= 1
five -= 1
elif five >= 3:
five -= 3
else:
return False
return Trueclass Solution {
public boolean lemonadeChange(int[] bills) {
int five = 0, ten = 0;
for (int bill : bills) {
if (bill == 5) five++;
else if (bill == 10) {
if (five == 0) return false;
five--; ten++;
} else {
if (ten > 0 && five > 0) {
ten--; five--;
} else if (five >= 3) {
five -= 3;
} else {
return false;
}
}
}
return true;
}
}#include <vector>
using namespace std;
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int five = 0, ten = 0;
for (int bill : bills) {
if (bill == 5) five++;
else if (bill == 10) {
if (five == 0) return false;
five--; ten++;
} else {
if (ten > 0 && five > 0) {
ten--; five--;
} else if (five >= 3) {
five -= 3;
} else {
return false;
}
}
}
return true;
}
};var lemonadeChange = function(bills) {
let five = 0, ten = 0;
for (let bill of bills) {
if (bill === 5) five++;
else if (bill === 10) {
if (five === 0) return false;
five--; ten++;
} else {
if (ten > 0 && five > 0) {
ten--; five--;
} else if (five >= 3) {
five -= 3;
} else {
return false;
}
}
}
return true;
};#include <stdbool.h>
bool lemonadeChange(int* bills, int billsSize) {
int five = 0, ten = 0;
for (int i = 0; i < billsSize; i++) {
if (bills[i] == 5) five++;
else if (bills[i] == 10) {
if (five == 0) return false;
five--; ten++;
} else {
if (ten > 0 && five > 0) {
ten--; five--;
} else if (five >= 3) {
five -= 3;
} else {
return false;
}
}
}
return true;
}public class Solution {
public bool LemonadeChange(int[] bills) {
int five = 0, ten = 0;
foreach (int bill in bills) {
if (bill == 5) five++;
else if (bill == 10) {
if (five == 0) return false;
five--; ten++;
} else {
if (ten > 0 && five > 0) {
ten--; five--;
} else if (five >= 3) {
five -= 3;
} else {
return false;
}
}
}
return true;
}
}The Python solution uses variables to track the count of $5 and $10 bills. It processes each bill, updating counts and checking if a transaction can be completed. The function returns false if a customer cannot receive the correct change.
Time Complexity: O(n), where n is the number of bills.
Space Complexity: O(1), with constant space usage for tracking bill counts.
Approach 2: Default Approach
function lemonadeChange(bills: number[]): boolean {
let [five, ten] = [0, 0];
for (const x of bills) {
switch (x) {
case 5:
five++;
break;
case 10:
five--;
ten++;
break;
case 20:
if (ten) {
ten--;
five--;
} else {
five -= 3;
}
break;
}
if (five < 0) {
return false;
}
}
return true;
}func lemonadeChange(bills []int) bool {
five, ten := 0, 0
for _, v := range bills {
if v == 5 {
five++
} else if v == 10 {
ten++
five--
} else {
if ten > 0 {
ten--
five--
} else {
five -= 3
}
}
if five < 0 {
return false
}
}
return true
}impl Solution {
pub fn lemonade_change(bills: Vec<i32>) -> bool {
let (mut five, mut ten) = (0, 0);
for bill in bills.iter() {
match bill {
5 => {
five += 1;
}
10 => {
five -= 1;
ten += 1;
}
_ => {
if ten != 0 {
ten -= 1;
five -= 1;
} else {
five -= 3;
}
}
}
if five < 0 {
return false;
}
}
true
}
}Approach 3: One-liner
const lemonadeChange = (bills: number[], f = 0, t = 0): boolean =>
bills.every(
x => (
(!(x ^ 5) && ++f) ||
(!(x ^ 10) && (--f, ++t)) ||
(!(x ^ 20) && (t ? (f--, t--) : (f -= 3), 1)),
f >= 0
),
);Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy with Bill Counting | Time Complexity: O(n), where n is the number of bills. |
| Default Approach | – |
| One-liner | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Bill Counting | O(n) | O(1) | Best general solution. Minimal state tracking and expected in coding interviews. |
| Simulation with Priority Change Strategy | O(n) | O(1) | Useful when modeling change-making logic explicitly or extending to more denominations. |
Frequently asked questions
Is Lemonade Change easy or hard?
Lemonade Change is classified as an Easy problem on LeetCode with around a 59% acceptance rate. The challenge is recognizing the greedy strategy and handling the $20 bill case correctly by prioritizing $10 + $5 change.
Lemonade Change Python/Java solution
Most implementations follow the same greedy logic across languages. Maintain variables for five and ten dollar bills, iterate through the payments array, and update counts while validating change availability. This results in an O(n) time and O(1) space implementation in Python, Java, C++, or JavaScript.
How to solve Lemonade Change in O(n)?
Iterate through the payments array and keep counters for $5 and $10 bills. For a $5 bill, increment the $5 counter. For a $10 bill, give one $5 as change if available. For a $20 bill, prefer giving $10 + $5 change; otherwise give three $5 bills. If neither option is possible, return false.
What is the best approach for Lemonade Change?
The greedy bill counting approach is the best solution. Track the number of $5 and $10 bills while iterating through the payments array. Always prioritize giving $10 + $5 change for a $20 bill when possible. This strategy runs in O(n) time with O(1) space and is the standard interview solution.
Is Lemonade Change asked at Google/Amazon/Meta?
Lemonade Change is a common entry-level greedy interview problem and has appeared in interview preparation lists for companies like Amazon and other tech firms. It tests reasoning about greedy decisions, state tracking, and simple transaction simulation.
What data structure is used in Lemonade Change?
The problem mainly uses simple counters to track available bills. The input is processed as an array, and the algorithm maintains integer counts for $5 and $10 denominations instead of complex data structures.
What is the time complexity of Lemonade Change?
The optimal solution runs in O(n) time where n is the number of customers. Each payment is processed exactly once with constant-time checks for available bills. The space complexity is O(1) because only a few counters are maintained.