Pro

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 10billsfor10 bills for15 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 5BillsBeforeOne5 Bills Before One10 and One $5

When giving 15changefora15 change for a20 bill, you should prefer using one 10andone10 and one5 over three 5bills.The5 bills. The5 bills are more versatile since they can be used for both 5and5 and10 change scenarios. Using three $5 bills depletes your flexibility for future transactions.

Not Tracking the $10 Bill Count

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