Problem of The Day: Lemonade Change
Problem StatementPermalink
IntuitionPermalink
When approaching this problem, my first thought is to consider how I can efficiently manage the change I need to give to each customer. Since each customer only pays with a $5, $10, or $20 bill, I can use a greedy approach to maximize the use of higher denomination bills when providing change, thereby preserving smaller bills for future transactions.
ApproachPermalink
To solve the problem, I maintain a dictionary cash
to keep track of the number of $5, $10, and $20 bills I have on hand. As I iterate through each transaction, I update this dictionary with the bill received. When making change, I always try to use the largest bills available first, which allows me to save smaller bills for situations where they are absolutely necessary.
Specifically, after receiving a bill, I calculate the change required by subtracting $5 from the bill’s value. Then, I attempt to provide this change by deducting from the available bills in the order of $20, $10, and then $5. If I am unable to provide the exact change, I return False
, indicating that it’s impossible to serve all customers with the current cash on hand. If I successfully process all transactions, I return True
.
ComplexityPermalink
-
Time complexity:
The time complexity is \(O(n)\), where \(n\) is the number of transactions. For each transaction, I may need to check up to three different bill denominations. -
Space complexity:
The space complexity is \(O(1)\) because the amount of memory I use does not scale with the size of the input. I only store the count of three types of bills.
CodePermalink
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
cash = {5: 0, 10: 0, 20: 0}
for bill in bills:
cash[bill] += 1
change = bill - 5
for x in [20, 10, 5]:
while cash[x] > 0 and change >= x:
change -= x
cash[x] -= 1
if change != 0:
return False
return True
EditorialPermalink
Approach: SimulationPermalink
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
# Count of $5 and $10 bills in hand
five_dollar_bills = 0
ten_dollar_bills = 0
# Iterate through each customer's bill
for customer_bill in bills:
if customer_bill == 5:
# Just add it to our count
five_dollar_bills += 1
elif customer_bill == 10:
# We need to give $5 change
if five_dollar_bills > 0:
five_dollar_bills -= 1
ten_dollar_bills += 1
else:
# Can't provide change, return false
return False
else: # customer_bill == 20
# We need to give $15 change
if ten_dollar_bills > 0 and five_dollar_bills > 0:
# Give change as one $10 and one $5
five_dollar_bills -= 1
ten_dollar_bills -= 1
elif five_dollar_bills >= 3:
# Give change as three $5
five_dollar_bills -= 3
else:
# Can't provide change, return false
return False
# If we've made it through all customers, return true
return True