Lemonade Change

Problem Description

At a lemonade stand, each lemonade costs $5. Customers are standing in a queue to buy from you and order one at a time. 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 i-th customer pays, return true if you can provide every customer with the correct change, or false otherwise.

Key Insights

• Customers pay with three types of bills: $5, $10, and $20.
• You start with no cash on hand.
• Change must be given back based on the type of bill received.
• To give change for a $10 bill, you need a $5 bill. To give change for a $20 bill, you need either one $10 bill and one $5 bill or three $5 bills.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we can use a greedy approach with two counters to keep track of the number of $5 and $10 bills we have. We iterate through the list of bills and determine how to handle each payment:

1. If a customer pays with a $5 bill, increment the $5 counter.
2. If a customer pays with a $10 bill, check if a $5 bill is available for change. If yes, decrement the $5 counter and increment the $10 counter.
3. If a customer pays with a $20 bill, check for change:
   • Preferably give one $10 bill and one $5 bill if available.
   • If not, give three $5 bills if available.
   • If neither option is available, return false.
4. If we can provide change for all customers, return true.

Code Solutions