Lemonade Change

860. Lemonade Change

Average Rating: 4.89 (9 votes)

Input: [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: [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't give change of $15 back because we only have two $10 bills. Since not every customer received correct change, the answer is false.

Solution
- Approach 1: Simulation

Solution

Approach 1: Simulation

Intuition and Algorithm

Let's try to simulate giving change to each customer buying lemonade. Initially, we start with no five dollar bills, and no ten dollar bills.

If a customer brings a $5 bill, then we take it.
If a customer brings a $10 bill, we must return a five dollar bill. If we don't have a five dollar bill, the answer is False, since we can't make correct change.
If a customer brings a $20 bill, we must return $15.
- If we have a $10 and a $5, then we always prefer giving change in that, because it is strictly worse for making change than three $5 bills.
- Otherwise, if we have three $5 bills, then we'll give that.
- Otherwise, we won't be able to give $15 in change, and the answer is False.

Complexity Analysis

Time Complexity: $O(N)$ , where $N$ is the length of bills.
Space Complexity: $O(1)$ .

Analysis written by: @awice.