Lemonade Change
Lemonade Change is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Greedy Patterns pattern, in the Sorting Based subpattern.
Problem statement
You are given bills, where each element is the bill paid by one customer, in arrival order. Each bill is 5, 10, or 20 dollars, and one lemonade costs exactly 5 dollars. The seller starts with no bills.
Serve customers in order. A customer paying 5 requires no change. A customer paying 10 requires one 5-dollar bill as change. A customer paying 20 requires 15 dollars as change, supplied either by one 10-dollar bill and one 5-dollar bill or by three 5-dollar bills. After each successful sale, keep the customer's bill for making change for later customers; no bills may be obtained from outside the transactions.
Return True if every customer can be served with exact change. Return False as soon as any customer cannot receive the required change.
Example 1:
Input: bills = [5,10,5,5,20,5,10,20] Output: true Explanation: Each transaction can be completed in order; for each 20-dollar bill, the seller has a valid combination of change available.
Example 2:
Input: bills = [5,10,20] Output: false Explanation: After serving the 10-dollar customer, the seller has no 5-dollar bill left, so the 20-dollar customer cannot receive 15 dollars in change.
Example 3:
Input: bills = [5,10,5,20,5,10,20] Output: false Explanation: The first 20-dollar customer can be served with a 10-dollar and a 5-dollar bill. Later, the final 20-dollar customer has no available combination totaling 15 dollars.
Constraints:
- 1 <= bills.length <= 10^5 - bills[i] is one of 5, 10, or 20 - Customers are processed in the order represented by bills - The lemonade price is exactly 5 dollars - The seller has no bills before processing bills[0]
Topics and companies
Topics: Greedy, Array, Counting, Simulation.
How to practise Lemonade Change on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n), where n is the number of bills. time and O(1) space.
Open Lemonade Change in the code editor, or read the Lemonade Change editorial for a worked solution with its approach and complexity analysis.
Where Lemonade Change sits in the DSA pattern sheet
- Greedy Patterns pattern guide
- Sorting Based subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Lemonade Change
Other problems that use the same Sorting Based and Greedy Patterns techniques:
- Assign Cookies — Easy, same subpattern
- Candy — Hard, same subpattern
- Hand of Straights — Medium, same subpattern
- Merge Triplets to Form Target Triplet — Medium, same subpattern
- Queue Reconstruction by Height — Medium, same subpattern
- Sort an Array — Medium, same subpattern