Lemonade Change

Easy

#0814Time: O(N), where N is the number of customers (the length of the `bills` array). We process each bill in a single pass.Space: O(1), as the hash map will store at most two keys (5 and 10), regardless of the input size. The space usage is constant.1 company

Patterns

Greedy

Data structures

Array

Companies

Zalando

Prompt

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 i^th customer pays, return true if you can provide every customer with the correct change, or false otherwise.

Example 1:

Input: bills = [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.

Example 2:

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

Constraints:

1 <= bills.length <= 10⁵
bills[i] is either 5, 10, or 20.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simulates the transaction process by keeping track of the available change using a hash map. We iterate through each customer's bill and update the counts of $5 and $10 bills we hold. For each transaction, we check if we have the necessary bills to provide the correct change.

Algorithm

Initialize a HashMap<Integer, Integer> to store counts of $5 and $10 bills.
Iterate through the bills array, one bill at a time.
If the bill is $5, increment the count of $5 bills in the map.
If the bill is $10, check if a $5 bill is available. If yes, decrement the $5 count and increment the $10 count. If no, return false.
If the bill is $20, try to make change for $15:
- First, check if a $10 bill and a $5 bill are available. If yes, decrement their counts.
- Else, check if three $5 bills are available. If yes, decrement the $5 count by 3.
- If neither change combination is possible, return false.
If the loop finishes without returning false, it means we can provide change to all customers. Return true.

Walkthrough

In this method, we use a hash map to represent our cash drawer, mapping bill denominations (like 5 and 10) to their respective counts. We don't need to track $20 bills since they cannot be used as change for a $5 lemonade.

We process the bills array sequentially.

When a customer pays with a $5 bill, we simply increment the count of $5 bills in our map.
When a customer pays with a $10 bill, we need to provide $5 in change. We check our map for an available $5 bill. If we have one, we decrement its count and increment the count of $10 bills. If not, we cannot make change, and we return false.
When a customer pays with a $20 bill, we need $15 in change. The best strategy is to be greedy and use larger bills first to save smaller, more versatile bills. We first try to use one $10 and one $5 bill. If that's not possible, we try to use three $5 bills. If neither option is available, we return false.

If we successfully process all bills, we return true.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public boolean lemonadeChange(int[] bills) {6        Map<Integer, Integer> change = new HashMap<>();7        change.put(5, 0);8        change.put(10, 0);9 10        for (int bill : bills) {11            if (bill == 5) {12                change.put(5, change.get(5) + 1);13            } else if (bill == 10) {14                if (change.get(5) > 0) {15                    change.put(5, change.get(5) - 1);16                    change.put(10, change.get(10) + 1);17                } else {18                    return false;19                }20            } else { // bill is 2021                // Greedy: try to use one $10 and one $5 first22                if (change.get(10) > 0 && change.get(5) > 0) {23                    change.put(10, change.get(10) - 1);24                    change.put(5, change.get(5) - 1);25                } else if (change.get(5) >= 3) {26                    change.put(5, change.get(5) - 3);27                } else {28                    return false;29                }30            }31        }32        return true;33    }34}

Complexity

Time

O(N), where N is the number of customers (the length of the `bills` array). We process each bill in a single pass.

Space

O(1), as the hash map will store at most two keys (5 and 10), regardless of the input size. The space usage is constant.

Trade-offs

Pros

Conceptually straightforward, directly mapping the problem's state (our cash drawer) to a data structure.
Easily extensible if more bill denominations were introduced.

Cons

Slightly more overhead than using simple variables due to the nature of hash maps (hashing, potential collisions).
The code can be a bit more verbose compared to a more optimized approach.

This is a more optimized approach that uses two integer variables to keep track of the counts of $5 and $10 bills. It follows a greedy strategy: for each customer, we process their payment and try to make change. When making change for a $20 bill, we greedily prioritize using a $10 bill over three $5 bills, as $5 bills are more flexible for future transactions.

Algorithm

Initialize two integer variables, five_count = 0 and ten_count = 0.
Iterate through the bills array.
For a $5 bill, increment five_count.
For a $10 bill, you need to give $5 change. Decrement five_count and increment ten_count. If five_count becomes negative after decrementing, it means you didn't have a $5 bill, so return false.
For a $20 bill, you need to give $15 change. The greedy strategy is to use a $10 bill and a $5 bill first, as this preserves the more versatile $5 bills.
- Check if you have at least one $10 bill and one $5 bill (ten_count > 0 and five_count > 0). If so, decrement both ten_count and five_count.
- Otherwise, check if you have at least three $5 bills (five_count >= 3). If so, decrement five_count by 3.
- If you cannot make change with either combination, return false.
If the loop completes, return true.

Walkthrough

This approach improves upon the hash map method by recognizing that we only need to track the counts of two types of bills: $5 and $10. Instead of a hash map, we can use two simple integer variables, fiveCount and tenCount, which is more efficient.

The logic remains the same. We iterate through the bills array:

If the bill is $5, we increment fiveCount.
If the bill is $10, we need a $5 for change. We decrement fiveCount and increment tenCount. If we don't have a $5 bill (fiveCount was 0), we fail and return false.
If the bill is $20, we need $15 change. We apply a greedy strategy. It's always better to use a $10 and a $5 bill for change if possible, because this saves our $5 bills, which are more versatile (they can make change for both $10 and $20 bills). So, we first check if we have both a $10 and a $5. If so, we use them. If not, our only other option is to use three $5 bills. If we can't do that either, we return false.

If we successfully process all customers, we return true.

1class Solution {2    public boolean lemonadeChange(int[] bills) {3        int fiveCount = 0;4        int tenCount = 0;5 6        for (int bill : bills) {7            if (bill == 5) {8                fiveCount++;9            } else if (bill == 10) {10                if (fiveCount == 0) {11                    return false;12                }13                fiveCount--;14                tenCount++;15            } else { // bill is 2016                // We need to give back $1517                // Greedy choice: use one $10 and one $518                if (tenCount > 0 && fiveCount > 0) {19                    tenCount--;20                    fiveCount--;21                } else if (fiveCount >= 3) {22                    // Alternative: use three $5s23                    fiveCount -= 3;24                } else {25                    // Cannot make change26                    return false;27                }28            }29        }30        return true;31    }32}

Complexity

Time

O(N), where N is the length of the `bills` array. We iterate through the array once.

Space

O(1). We only use a constant number of variables (`fiveCount`, `tenCount`) to store the state, regardless of the input size.

Trade-offs

Pros

Highly efficient with minimal overhead.
Simple and clean implementation.
Optimal solution in terms of both time and space complexity.

Cons

The logic is slightly less direct than a map-based simulation if one is not familiar with greedy algorithms.
Less extensible if the problem were to include many more bill types, where a map might become more manageable.

Solutions

Solution

1class Solution {2public3  boolean lemonadeChange(int[] bills) {4    int five = 0, ten = 0;5    for (int v : bills) {6      switch (v) { case 5 -> ++ five ; case 10 -> { ++ ten ; -- five ; } case 20 -> { if ( ten > 0 ) { -- ten ; -- five ; } else { five -= 3 ; } } } if ( five < 0 ) { return false ; } } return true ; } }

1export function lemonadeChange ( bills ) { let [ five , ten ] = [ 0 , 0 ]; for ( const x of bills ) { switch ( x ) { case 5 : five ++ ; break ; case 10 : five -- ; ten ++ ; break ; case 20 : if ( ten ) { ten -- ; five -- ; } else { five -= 3 ; } break ; } if ( five < 0 ) { return false ; } } return true ; }

1class Solution {2public:3  bool lemonadeChange(vector<int> &bills) {4    int five = 0, ten = 10;5    for (int v : bills) {6      if (v == 5) {7        ++five;8      } else if (v == 10) {9        ++ten;10        --five;11      } else {12        if (ten) {13          --ten;14          --five;15        } else {16          five -= 3;17        }18      }19      if (five < 0) {20        return false;21      }22    }23    return true;24  }25};

1class Solution:2    def lemonadeChange(self, bills: List[int]) -> bool: five = ten = 0 for v in bills: if v == 5: five += 1 elif v == 10: ten += 1 five -= 1 else: if ten: ten -= 1 five -= 1 else: five -= 3 if five < 0: return False return True

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem