# 860. Lemonade Change
LeetCode Problem Link (opens new window)
At a lemonade stand, each cup of lemonade costs $5.
Customers are standing in a queue to buy from you, and they pay with bills in the order given by the integer array bills.
Each customer buys a single cup of lemonade and pays with either a $5, $10, or $20 bill. You must provide each customer with the correct change.
Note that you start with no change in hand.
Return true if and only if you can provide every customer with the correct change.
Example 1:
- Input:
[5,5,5,10,20] - Output:
true - Explanation:
- The first 3 customers pay with $5, so you take 3 $5 bills.
- The 4th customer pays with a $10 bill and you return $5.
- The 5th customer pays with a $20 bill and you return a $10 bill and a $5 bill.
- Since all customers get correct change, we output
true.
Example 2:
- Input:
[5,5,10] - Output:
true
Example 3:
- Input:
[10,10] - Output:
false
Example 4:
- Input:
[5,5,10,10,20] - Output:
false - Explanation:
- We take two $5 bills from the first two customers.
- For the next two customers who pay with $10 bills, we return $5.
- The last customer pays with a $20 bill, but we can't return $15 since we only have two $10 bills.
- Therefore, not every customer receives correct change, so we return false.
Constraints:
0 <= bills.length <= 10000bills[i]will be either5,10, or20
# Approach
This was a LeetCode daily challenge some days ago, and it's quite interesting, so let's discuss it.
At first glance, this problem might seem a bit confusing. How can we ensure that we always give the correct change?
But upon closer inspection, you'll realize that there's not much leeway for making decisions!
You just need to maintain the counts of three denominations: $5, $10, and $20.
There are three scenarios:
- Scenario 1: The bill is $5, just accept it.
- Scenario 2: The bill is $10, use one $5 to give change.
- Scenario 3: The bill is $20, first try to give change with one $10 and one $5. If that's not possible, give change with three $5 bills.
Now, if you look closely, you'll find that Scenario 1 and Scenario 2 have a fixed strategy, and there's not much room for analysis. The uncertainty lies in Scenario 3.
Scenario 3 can actually be solved by a greedy approach.
Why should we prefer to use a $10 bill and a $5 bill when the bill is $20?
Because the $10 bill can only be used to give change for a $20 bill, while the $5 bill can be used to give change for both $10 and $20 bills. The $5 bill is more versatile!
Thus, the local optimal solution: When encountering a $20 bill, prioritize using one $10 and one $5 bill. The global optimal solution is to provide correct change for all transactions.
If the local optimal strategies lead to the global optimal result and no counterexamples can be found, then a greedy algorithm might just work!
Here's the C++ code for reference:
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int five = 0, ten = 0, twenty = 0;
for (int bill : bills) {
// Scenario 1
if (bill == 5) five++;
// Scenario 2
if (bill == 10) {
if (five <= 0) return false;
ten++;
five--;
}
// Scenario 3
if (bill == 20) {
// Prefer using one $10 if possible, as $5 can be used more widely for change
if (five > 0 && ten > 0) {
five--;
ten--;
twenty++; // Actually, this line can be removed since tracking $20 isn't necessary
} else if (five >= 3) {
five -= 3;
twenty++; // Similarly, this line can also be omitted
} else return false;
}
}
return true;
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
- Time complexity: O(n)
- Space complexity: O(1)
# Summary
At first, this problem might seem really complicated, but after breaking down the logic, you'll find that the solution is actually quite fixed.
This problem can teach you that when facing a problem that seems to lack direction, slow down and analyze each situation thoroughly. Once you have broken it down into specific cases, everything becomes clear.
If you're stuck trying to find a global way to handle change, you might end up getting tangled in the possibilities, making it seem more complex than it actually is.
# Other Language Versions
# Java
class Solution {
public boolean lemonadeChange(int[] bills) {
int five = 0;
int ten = 0;
for (int i = 0; i < bills.length; i++) {
if (bills[i] == 5) {
five++;
} else if (bills[i] == 10) {
five--;
ten++;
} else if (bills[i] == 20) {
if (ten > 0) {
ten--;
five--;
} else {
five -= 3;
}
}
if (five < 0 || ten < 0) return false;
}
return true;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Python
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
five = 0
ten = 0
twenty = 0
for bill in bills:
# Scenario 1: Receive $5
if bill == 5:
five += 1
# Scenario 2: Receive $10
if bill == 10:
if five <= 0:
return False
ten += 1
five -= 1
# Scenario 3: Receive $20
if bill == 20:
# Prefer using one $10 and one $5 for change
if five > 0 and ten > 0:
five -= 1
ten -= 1
#twenty += 1
# If not possible, use three $5 for change
elif five >= 3:
five -= 3
#twenty += 1
else:
return False
return True
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# Go
func lemonadeChange(bills []int) bool {
ten, five := 0, 0
for i := 0; i < len(bills); i++ {
if bills[i] == 5 {
five++
} else if bills[i] == 10 {
if five == 0 {
return false
}
ten++; five--
} else {
if ten >= 1 && five >= 1 {
ten--; five--
} else if five >= 3 {
five -= 3
} else {
return false
}
}
}
return true
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# JavaScript
var lemonadeChange = function(bills) {
let fiveCount = 0
let tenCount = 0
for(let i = 0; i < bills.length; i++) {
let bill = bills[i]
if(bill === 5) {
fiveCount += 1
} else if (bill === 10) {
if(fiveCount > 0) {
fiveCount -=1
tenCount += 1
} else {
return false
}
} else {
if(tenCount > 0 && fiveCount > 0) {
tenCount -= 1
fiveCount -= 1
} else if(fiveCount >= 3) {
fiveCount -= 3
} else {
return false
}
}
}
return true
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Rust
impl Solution {
pub fn lemonade_change(bills: Vec<i32>) -> bool {
let mut five = 0;
let mut ten = 0;
// let mut twenty = 0;
for bill in bills {
if bill == 5 { five += 1; }
if bill == 10 {
if five <= 0 { return false; }
ten += 1;
five -= 1;
}
if bill == 20 {
if five > 0 && ten > 0 {
five -= 1;
ten -= 1;
// twenty += 1;
} else if five >= 3 {
five -= 3;
// twenty += 1;
} else { return false; }
}
}
true
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# C
bool lemonadeChange(int* bills, int billsSize){
// Record the count of $5 and $10 bills (no need to track $20 as it's not used for change)
int fiveCount = 0; int tenCount = 0;
int i;
for(i = 0; i < billsSize; ++i) {
// Different cases for each customer payment
switch(bills[i]) {
// Case 1: Directly receive $5
case 5:
fiveCount++;
break;
// Case 2: Receive $10
case 10:
// Return false if no $5 available
if(fiveCount == 0)
return false;
// Receive $10 and give back $5
fiveCount--;
tenCount++;
break;
// Case 3: Receive $20
case 20:
// Prefer using $10 and $5 (since $10 can only help $20)
if(fiveCount > 0 && tenCount > 0) {
fiveCount--;
tenCount--;
}
// If no $10, use three $5 instead
else if(fiveCount >= 3)
fiveCount-=3;
// Return false if can't give change
else
return false;
break;
}
}
// Return true if all change is possible
return true;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# TypeScript
function lemonadeChange(bills: number[]): boolean {
let five: number = 0,
ten: number = 0;
for (let bill of bills) {
switch (bill) {
case 5:
five++;
break;
case 10:
if (five < 1) return false;
five--;
ten++
break;
case 20:
if (ten > 0 && five > 0) {
five--;
ten--;
} else if (five > 2) {
five -= 3;
} else {
return false;
}
break;
}
}
return true;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Scala
object Solution {
def lemonadeChange(bills: Array[Int]): Boolean = {
var fiveNum = 0
var tenNum = 0
for (i <- bills) {
if (i == 5) fiveNum += 1
if (i == 10) {
if (fiveNum <= 0) return false
tenNum += 1
fiveNum -= 1
}
if (i == 20) {
if (fiveNum > 0 && tenNum > 0) {
tenNum -= 1
fiveNum -= 1
} else if (fiveNum >= 3) {
fiveNum -= 3
} else {
return false
}
}
}
true
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# C#
public class Solution
{
public bool LemonadeChange(int[] bills)
{
int five = 0, ten = 0, twenty = 0;
foreach (var bill in bills)
{
if (bill == 5) five++;
if (bill == 10)
{
if (five == 0) return false;
five--;
ten++;
}
if (bill == 20)
{
if (ten > 0 && five > 0)
{
ten--;
five--;
twenty++;
}
else if (five >= 3)
{
five -= 3;
twenty++;
}
else
{
return false;
}
}
}
return true;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37