860. Lemonade Change

EasyGreedyArray
Leetcode Link

Problem Description

In this problem, you are operating a lemonade stand where each glass of lemonade is sold for $5. You start without any change in hand. Customers come in a queue, and you should sell them lemonade in the order they come, with each customer buying exactly one glass. Customers pay with a $5, $10, or $20 bill. Your task is to determine whether you can provide the correct change to each customer using the bills you have at your disposal. You need to give back the net difference such that each customer effectively pays exactly $5 for their lemonade. For instance, if a customer pays with $20, and you have enough change, you will hand back $15 in change. If it is possible to provide the correct change for all customers, the function should return true, otherwise it should return false.

Intuition

The main issue is to always have enough $5 bills to make change, since they are the cornerstone of all transactions. Here's the intuitive approach:

  1. Keep track of the number of $5 and $10 bills (we don't need to track $20 bills as they don't help in making change).
  2. Process each customer in the queue one by one and handle the payment.
    • If a customer pays with a $5 bill, no change is needed, and you just increase your count of $5 bills.
    • If a customer pays with a $10 bill, you need to give back a $5 as change, so you decrement the $5 bill count and increment the $10 bill count.
    • If a customer pays with a $20 bill, you prefer to give back one $10 and one $5 as change because this uses up larger bills and keeps more $5 bills for future transactions (which are more crucial). If you can't give change in this combination, you attempt to give three $5 bills as change.
  3. After handling a transaction, if the count of $5 bills is negative, that means you didn't have enough change for a customer, and hence you should return false.
  4. If you finish processing all customers and never ran out of $5 bills, then you return true.

Learn more about Greedy patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Solution Approach

The solution is straightforward and follows a greedy algorithmic approach, which operates on the simplest of principles: give out the minimal amount of change necessary.

In terms of data structures, we only need two variables to keep track of the number of $5 and $10 bills as these are the only denominations we can give out for change.

The algorithm goes as follows:

  1. Initialize two variables: five and ten to track the count of $5 and $10 bills we have. We do not need to keep track of $20 bills as they cannot be given as change.
  2. Iterate through each bill in the bills list.
    • If the bill is $5, increment the five counter, since we now have an additional $5 bill.
    • If the bill is $10, we need to give a $5 bill as change, so we decrement the five counter and increment the ten counter.
    • If the bill is $20, firstly, we check if we have any $10 bills:
      • If we have a $10 bill, we use it along with a $5 bill to make $15 in change (decrement both ten and five).
      • If we don't have a $10 bill, we need to give out three $5 bills (decrement five by three).
    • After handling the bill, we check if the five counter has gone negative. If it has, it means we can't make change for the current transaction, and we return false.
  3. After the loop, if we've successfully given change to every customer, our five counter should never be negative, and we can return true.

The algorithm effectively balances between preserving $5 bills, which are necessary for giving change to customers who pay with $10 and $20, and using up $10 bills when possible to avoid depleting the $5 bills too quickly. This greedy strategy works for any sequence of bills because making change with larger bills when possible is always at least as good as, and often better than, breaking down $5 bills.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Suppose we have a queue of customers with the following bills: 5,5, 10, 20,20, 5, $10.

  1. Initialize five = 0 and ten = 0.
  2. Customer 1 pays with $5:
    • five is incremented by 1 (five = 1, ten = 0).
  3. Customer 2 pays with $10:
    • We give one $5 bill as change: five is decremented by 1, ten is incremented by 1 (five = 0, ten = 1).
  4. Customer 3 pays with $20:
    • To give change, we'd prefer a 10anda10 and a 5 bill. We have one $10 bill:
      • ten is decremented by 1 and five is decremented by 1 to provide $15 in change (five = -1, ten = 0).
      • Since we don't have any $5 bills left to give as change, we cannot fulfill this transaction - we return false.

We stop the process as we've been unable to provide change for the third customer. Thus, the function will return false in this example.

Solution Implementation

1class Solution:
2    def lemonadeChange(self, bills: List[int]) -> bool:
3        # Initialize counters for five and ten dollar bills
4        five_dollar_count = ten_dollar_count = 0
5      
6        # Iterate over each bill received
7        for bill in bills:
8            if bill == 5:
9                # If it's a $5 bill, simply increase the count of $5 bills
10                five_dollar_count += 1
11            elif bill == 10:
12                # If it's a $10 bill, give one $5 bill as change
13                ten_dollar_count += 1
14                five_dollar_count -= 1
15            else:
16                # If it's a $20 bill, try to give one $10 and one $5 as change if possible
17                # Otherwise, give three $5 bills as change
18                if ten_dollar_count:
19                    ten_dollar_count -= 1
20                    five_dollar_count -= 1
21                else:
22                    five_dollar_count -= 3
23          
24            # If at any point the count of $5 bills drops below zero, it's impossible to give change
25            if five_dollar_count < 0:
26                return False
27      
28        # If we got to the end without running out of $5 bills, we can give change for all transactions
29        return True
30
1class Solution {
2    public boolean lemonadeChange(int[] bills) {
3        // Initialize counters for five and ten dollar bills
4        int fiveDollarBills = 0;
5        int tenDollarBills = 0;
6      
7        // Iterate over each bill in the array
8        for (int bill : bills) {
9            // Use switch-case to handle different bill values
10            switch (bill) {
11                case 5:
12                    // If it's a $5 bill, no change is needed, increase count of $5 bills
13                    fiveDollarBills++;
14                    break;
15                case 10:
16                    // For a $10 bill, we need to give one $5 bill as change
17                    tenDollarBills++;        // Increase $10 bills
18                    fiveDollarBills--;       // Reduce $5 bills as we give it as change
19                    break;
20                case 20:
21                    // For a $20 bill, prefer to give one $10 and one $5 as change if possible
22                    if (tenDollarBills > 0) {
23                        tenDollarBills--;     // Use a $10 bill for change
24                        fiveDollarBills--;    // Use a $5 bill for change
25                    } else {
26                        // If no $10 bills, we need to give three $5 bills as change
27                        fiveDollarBills -= 3;
28                    }
29                    break;
30            }
31            // If at any point we do not have enough $5 bills to give as change, return false
32            if (fiveDollarBills < 0) {
33                return false;
34            }
35        }
36        // If we can make change for all customers, return true
37        return true;
38    }
39}
40
1#include <vector> // Include the vector header for using the vector container.
2
3class Solution {
4public:
5    // Method to determine if we can provide every customer with correct change.
6    bool lemonadeChange(vector<int>& bills) {
7        // Initialize counters for $5 and $10 bills.
8        int fiveDollarBills = 0, tenDollarBills = 0;
9      
10        // Iterate over each bill in the vector 'bills'.
11        for (int bill : bills) {
12            if (bill == 5) {
13                // If the bill is $5, no change is needed, simply increment $5 bill counter.
14                ++fiveDollarBills;
15            } else if (bill == 10) {
16                // If the bill is $10, give one $5 bill as change and increment $10 bill counter.
17                ++tenDollarBills;
18                --fiveDollarBills; // Giving change of one $5 bill.
19            } else {
20                // For a $20 bill, prefer to give one $10 and one $5 bill as change if possible.
21                if (tenDollarBills > 0) {
22                    --tenDollarBills;
23                    --fiveDollarBills; // Giving change of one $10 and one $5 bill.
24                } else {
25                    // If no $10 bills are available, give three $5 bills as change.
26                    fiveDollarBills -= 3;
27                }
28            }
29          
30            // If at any point we do not have enough $5 bills to give change, return false.
31            if (fiveDollarBills < 0) {
32                return false;
33            }
34        }
35        // If we were able to provide change for all customers, return true.
36        return true;
37    }
38};
39
1function lemonadeChange(bills: number[]): boolean {
2    // Initialize the count of $5 and $10 bills
3    let fiveDollarBills = 0;
4    let tenDollarBills = 0;
5
6    // Iterate through each bill received
7    for (let bill of bills) {
8        switch (bill) {
9            case 5: // When the bill is $5, no change is needed, simply increase the count of $5 bills
10                fiveDollarBills++;
11                break;
12            case 10: // For a $10 bill, give back one $5 bill as change and increase $10 bill count
13                fiveDollarBills--;   // Giving change
14                tenDollarBills++;    // Receiving $10
15                break;
16            case 20: // For a $20 bill, try to give one $10 and one $5 as change if possible
17                if (tenDollarBills > 0) {
18                    tenDollarBills -= 1;    // Giving one $10 bill as change
19                    bill -= 10;             // $10 change has been given, need $10 more
20                }
21                fiveDollarBills -= bill / 5 - 1; // Give the rest of the change in $5 bills
22                break;
23            // Note: Though the use of the 'bill' variable here is a bit unconventional,
24            //       since we've subtracted $10 if we've used a $10 bill for change,
25            //       dividing 'bill' by 5 now effectively gives us how many more $5 bills
26            //       we need to give as change (either one $5 bill if we gave a $10, or 
27            //       three $5 bills if we didn't).
28        }
29      
30        // If we don't have enough $5 bills to give change, return false
31        if (fiveDollarBills < 0) {
32            return false;
33        }
34    }
35  
36    // If we've iterated through all bills and always had enough to give change, return true
37    return true;
38}
39
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Time and Space Complexity

Time Complexity:

The given algorithm iterates through the list of bills once. During each iteration, it performs a constant number of operations such as comparison, increment, and decrement on integer variables. These operations do not depend on the size of the input and hence take constant time.

Therefore, the time complexity of the algorithm is determined by the number of iterations, which is directly proportional to the length of the list of bills, n. Hence, the time complexity is O(n), where n is the length of the bills list.

Space Complexity:

The algorithm uses a fixed number of integer variables (five and ten) to keep track of the count of 5and5 and 10 bills. The space used does not grow with the size of the input list. These two integer variables use a constant amount of space.

Consequently, the space complexity of the algorithm is O(1), which means it uses constant additional space regardless of the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫