Problem
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.
Examples
Example 1:
|
|
Example 2:
|
|
Solution
Method 1 - Count 5 and 10 bills
When the customer gives us $20
, we have two options:
- Return back three
$5
, OR - Return back one
$5
and one$10
.
When possible, second option is better because this way we have two $5
bills, which we can use in future transactions. So, this is why this is a greedy option, where we greedily try to return back $10
s, and then use $5
.
So, we can keep track of number of $5
and $10
bills. We don’t have to keep track of $20
bills, because customer will buy 1 lemonade at least, and we will never return them back $20
bills. So, we don’t have to track $20
bills to check if change can be made or not.
Video
Here is the video explanation:
Code
|
|
Complexity
- ⏰ Time complexity:
O(n)
where is number of transactions - 🧺 Space complexity:
O(1)