Lemonade Change

EASY

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 (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

Checkout 2 different approaches to solve Lemonade Change. Click on different approaches to view the approach and algorithm in detail.

Simulation with Hash Map

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.

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.

import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean lemonadeChange(int[] bills) {
        Map<Integer, Integer> change = new HashMap<>();
        change.put(5, 0);
        change.put(10, 0);

        for (int bill : bills) {
            if (bill == 5) {
                change.put(5, change.get(5) + 1);
            } else if (bill == 10) {
                if (change.get(5) > 0) {
                    change.put(5, change.get(5) - 1);
                    change.put(10, change.get(10) + 1);
                } else {
                    return false;
                }
            } else { // bill is 20
                // Greedy: try to use one $10 and one $5 first
                if (change.get(10) > 0 && change.get(5) > 0) {
                    change.put(10, change.get(10) - 1);
                    change.put(5, change.get(5) - 1);
                } else if (change.get(5) >= 3) {
                    change.put(5, change.get(5) - 3);
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(N), where N is the number of customers (the length of the `bills` array). We process each bill in a single pass.Space Complexity: 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.

Pros and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for Lemonade Change. Click on different languages to view the code.

class Solution {
public
  boolean lemonadeChange(int[] bills) {
    int five = 0, ten = 0;
    for (int v : bills) {
      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 ; } }

Video Solution

Watch the video walkthrough for Lemonade Change

Patterns:

Greedy

Data Structures:

Array

Companies:

Zalando |