Scale Engineer

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 ith 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 <= 105
  • 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.

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

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.

Solutions

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

Next problem