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 (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 either 5, 10, or 20.
Approach:
- Maintain a wallet to track count of
$5and$10bills. - Iterate over each customer’s bill:
- If bill is
$5→ add to wallet. - If bill is
$10→ give one$5as change and add one$10. - If bill is
$20→- Prefer giving one
$10+ one$5if possible. - Otherwise, give three
$5.
- Prefer giving one
- If bill is
- After each transaction, if wallet runs out of required bills (negative count), return
false. - If all transactions succeed, return
true.
Time & Space Complexity:
Time Complexity: O(n)
Space Complexity: O(1)
Dry Run
Input: bills = [5, 5, 5, 10, 20]
Step 1: Initialize wallet = [0, 0] // [count of $5, count of $10] Step 2: Process each bill i = 0 → bill = 5 Add one $5 → wallet = [1, 0] i = 1 → bill = 5 Add one $5 → wallet = [2, 0] i = 2 → bill = 5 Add one $5 → wallet = [3, 0] i = 3 → bill = 10 Give back one $5, keep one $10 wallet = [2, 1] i = 4 → bill = 20 Prefer $10 + $5 if possible Use one $10 and one $5 → wallet = [1, 0] Step 3: Validation At each step, wallet[0] (number of $5) never goes negative. Step 4: End Return true
Output: Result: true
var lemonadeChange = function(bills) {
let wallet = [0, 0];
for (let i = 0; i < bills.length; ++i) {
if (bills[i] === 5) {
wallet[0]++;
} else if (bills[i] === 10) {
wallet[1]++;
wallet[0]--;
} else { // bill is 20
if (wallet[1] > 0) {
wallet[1]--;
wallet[0]--;
} else {
wallet[0] -= 3;
}
}
if (wallet[0] < 0) {
return false;
}
}
return true;
};
def lemonadeChange(bills):
wallet = [0, 0]
for b in bills:
if b == 5:
wallet[0] += 1
elif b == 10:
wallet[1] += 1
wallet[0] -= 1
else: # b == 20
if wallet[1] > 0:
wallet[1] -= 1
wallet[0] -= 1
else:
wallet[0] -= 3
if wallet[0] < 0:
return False
return True
public class Solution {
public boolean lemonadeChange(int[] bills) {
int[] wallet = new int[2]; // wallet[0] = $5, wallet[1] = $10
for (int i = 0; i < bills.length; i++) {
int b = bills[i];
if (b == 5) {
wallet[0]++;
} else if (b == 10) {
wallet[1]++;
wallet[0]--;
} else { // b == 20
if (wallet[1] > 0) {
wallet[1]--;
wallet[0]--;
} else {
wallet[0] = wallet[0] - 3;
}
}
if (wallet[0] < 0) return false;
}
return true;
}
}
#include <vector>
using namespace std;
bool lemonadeChange(vector& bills) {
int wallet[2] = {0, 0};
for (int b : bills) {
if (b == 5) {
wallet[0]++;
} else if (b == 10) {
wallet[1]++;
wallet[0]--;
} else { // b == 20
if (wallet[1] > 0) {
wallet[1]--;
wallet[0]--;
} else {
wallet[0] -= 3;
}
}
if (wallet[0] < 0) return false;
}
return true;
}
#include <stdbool.h>
bool lemonadeChange(int* bills, int billsSize) {
int wallet[2] = {0, 0};
for (int i = 0; i < billsSize; ++i) {
int b = bills[i];
if (b == 5) {
wallet[0]++;
} else if (b == 10) {
wallet[1]++;
wallet[0]--;
} else { // b == 20
if (wallet[1] > 0) {
wallet[1]--;
wallet[0]--;
} else {
wallet[0] -= 3;
}
}
if (wallet[0] < 0) return false;
}
return true;
}
public class Solution {
public bool LemonadeChange(int[] bills) {
int[] wallet = new int[2];
for (int i = 0; i < bills.Length; i++) {
int b = bills[i];
if (b == 5) {
wallet[0]++;
} else if (b == 10) {
wallet[1]++;
wallet[0]--;
} else { // b == 20
if (wallet[1] > 0) {
wallet[1]--;
wallet[0]--;
} else {
wallet[0] -= 3;
}
}
if (wallet[0] < 0) return false;
}
return true;
}
}
