860. Lemonade Change - Explanation

Problem Link

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.

You are 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,10,5,5,20]

Output: true

Explanation:
From first customer, we collect one $5 bill.
From second customer, we collect $10 bill and give back $5 bill.
From third and fourth customers, we collect two $5 bills.
From fifth customer, we collect $20 bill and give back one $10 bill and $5 bill.

Example 2:

Input: bills = [5,20,10,5]

Output: false

Constraints:

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


Topics

Array Greedy

Company Tags

Please upgrade to NeetCode Pro to view company tags.



Prerequisites

Before attempting this problem, you should be comfortable with:

  • Greedy Algorithms - Making optimal local decisions at each step (prioritizing $10 bills for $15 change to preserve flexibility)
  • Basic Iteration - Processing elements sequentially while maintaining state
  • Simple Counting - Tracking quantities of different bill denominations using variables

1. Iteration - I

Intuition

Each lemonade costs $5, so we need to give back the difference when customers pay with $10 or $20 bills. The key observation is that $5 bills are more versatile than $10 bills since they can be used for both $5 and $15 change. When giving $15 change, we should prefer using one $10 and one $5 rather than three $5s to preserve our flexibility for future transactions.

Algorithm

  1. Track the count of $5 and $10 bills we have.
  2. For each customer's bill:
    • If $5: simply add it to our $5 count.
    • If $10: we need to give $5 change. Decrement the $5 count and increment the $10 count. Return false if no $5 is available.
    • If $20: we need to give $15 change. Prefer using one $10 + one $5 if possible; otherwise use three $5s. Return false if neither option works.
  3. Return true if all customers received correct change.
class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five, ten = 0, 0
        for b in bills:
            if b == 5:
                five += 1
            elif b == 10:
                ten += 1
                if five > 0:
                    five -= 1
                else:
                    return False
            else:
                change = b - 5
                if change == 15 and five > 0 and ten > 0:
                    five -= 1
                    ten -= 1
                elif change == 15 and five >= 3:
                    five -= 3
                else:
                    return False
        return True

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1) extra space.

2. Iteration - II

Intuition

This is a cleaner version of the same greedy approach. Instead of checking conditions before decrementing, we optimistically make the change and then verify if the $5 count went negative. This simplifies the code by deferring the validity check to a single condition after each transaction.

Algorithm

  1. Track $5 and $10 bill counts.
  2. For each bill:
    • If $5: increment the $5 count.
    • If $10: decrement $5, increment $10.
    • If $20 and we have a $10: decrement both $5 and $10.
    • If $20 and no $10: decrement $5 by 3.
  3. After each transaction, check if the $5 count is negative. If so, return false.
  4. Return true after processing all customers.
class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five, ten = 0, 0
        for b in bills:
            if b == 5:
                five += 1
            elif b == 10:
                five, ten = five - 1, ten + 1
            elif ten > 0:
                five, ten = five - 1, ten - 1
            else:
                five -= 3
            if five < 0:
                return False
        return True

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1) extra space.

Common Pitfalls

Using Three $5 Bills Before One $10 and One $5

When giving $15 change for a $20 bill, you should prefer using one $10 and one $5 over three $5 bills. The $5 bills are more versatile since they can be used for both $5 and $10 change scenarios. Using three $5 bills depletes your flexibility for future transactions.

Not Tracking the $10 Bill Count

Some solutions only track $5 bills, assuming $10 bills are not useful. However, $10 bills are essential for efficiently making $15 change. Failing to track them means you cannot implement the optimal greedy strategy and may incorrectly return false when change is actually possible.