In this guide, you will get 860. Lemonade Change LeetCode Solution with the best time and space complexity. The solution to Lemonade Change problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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 <= 105
bills[i] is either 5, 10, or 20.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
860. Lemonade Change LeetCode Solution in C++
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int fives = 0;
int tens = 0;
for (const int bill : bills) {
if (bill == 5) {
++fives;
} else if (bill == 10) {
--fives;
++tens;
} else { // bill == 20
if (tens > 0) {
--tens;
--fives;
} else {
fives -= 3;
}
}
if (fives < 0)
return false;
}
return true;
}
}; /* code provided by PROGIEZ */
860. Lemonade Change LeetCode Solution in Java
class Solution {
public boolean lemonadeChange(int[] bills) {
int fives = 0;
int tens = 0;
for (final int bill : bills) {
if (bill == 5) {
++fives;
} else if (bill == 10) {
--fives;
++tens;
} else { // bill == 20
if (tens > 0) {
--tens;
--fives;
} else {
fives -= 3;
}
}
if (fives < 0)
return false;
}
return true;
}
} // code provided by PROGIEZ
860. Lemonade Change LeetCode Solution in Python
class Solution:
def lemonadeChange(self, bills: list[int]) -> bool:
fives = 0
tens = 0
for bill in bills:
if bill == 5:
fives += 1
elif bill == 10:
fives -= 1
tens += 1
else: # bill == 20
if tens > 0:
tens -= 1
fives -= 1
else:
fives -= 3
if fives < 0:
return False
return True # code by PROGIEZ
