860. Lemonade Change
Model: qwen2.5-coder:14b
Topics: Greedy
FAANG asked: 0
Acceptance rate: 51.9%
Problem Breakdown
The problem involves managing cash transactions at a lemonade stand where each lemonade costs 5, 20 bill. The task is to determine if it’s possible to provide the correct change for every customer in the queue.
Inputs:
bills: A list of integers representing the bills customers use to pay for lemonades.
Outputs:
- A boolean value (
trueorfalse) indicating whether it’s possible to provide the correct change to all customers.
Implicit Constraints and Edge Cases:
- The input list can be empty, in which case the output should be
truesince no transactions are needed. - The bills will only be 10, or $20.
- If a customer pays with a 5 bill as change.
- If a customer pays with a 5 bills or one 5 bill as change.
Intuition
A brute-force approach would involve checking all possible combinations of bills to make the correct change. However, this is inefficient due to its high time complexity (O(n^2) in the worst case).
The key insight is to use a greedy algorithm. By always trying to give back the largest denomination of bills first, we can ensure that we use the fewest number of bills and have the best chance of making correct change.
Approach
- Initialize two counters:
five_countfor 10 bills. - Iterate through each bill in the input list:
- If the bill is $5, increment the
five_count. - If the bill is 5 bill) and increment the
ten_count. - If the bill is 10 and one 5 bills.
- If the bill is $5, increment the
- After processing each bill, check if the counters are valid (i.e.,
five_countshould never be negative). - If all bills can be processed without running out of change, return
true. Otherwise, returnfalse.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the input list
bills. We iterate through the list once. - Space Complexity: O(1). We use a constant amount of extra space for the counters.
Solution
def lemonadeChange(bills):
five_count = 0
ten_count = 0
for bill in bills:
if bill == 5:
five_count += 1
elif bill == 10:
if five_count > 0:
five_count -= 1
ten_count += 1
else:
return False
elif bill == 20:
if ten_count > 0 and five_count > 0:
ten_count -= 1
five_count -= 1
elif five_count >= 3:
five_count -= 3
else:
return False
return True
Edge Cases Handled
- Empty Input: The function returns
truesince no transactions are needed. - **All 5 bills and returns
true. - Mixed 20 Bills: The function checks if it can provide the correct change for each bill, returning
falseif it cannot.