LeetCode 860 - Lemonade Change

This problem simulates a lemonade stand where each lemonade costs 5, 20 bill. The challenge is to provide exact change to every customer as they pay. The input is a list of integers bills, where each element represents the bill a customer gives.

leetcodeeasyarraygreedy

LeetCode Problem 860

Difficulty: 🟢 Easy
Topics: Array, Greedy

Solution

Problem Understanding

This problem simulates a lemonade stand where each lemonade costs $5. Customers come in a specific order and pay with a $5, $10, or $20 bill. The challenge is to provide exact change to every customer as they pay. The input is a list of integers bills, where each element represents the bill a customer gives. The output is a boolean: true if it is possible to give correct change to every customer, and false otherwise.

Constraints indicate that the array can be very large, up to 100,000 elements. Each bill is guaranteed to be one of 5, 10, or 20, so we do not need to handle invalid denominations. The problem also implies that we start with zero cash on hand, so our initial transactions are restricted to exact payments or accumulation of small bills for future change.

Edge cases that can trip a naive solution include consecutive high-value bills, such as [10, 20] without an initial $5, or sequences where $20 bills appear before sufficient $10 and $5 bills are collected.

Approaches

The brute-force approach would attempt to simulate every possible way to give change, trying all combinations of available bills to satisfy each customer. This is unnecessary because the problem is constrained to only three bill types and the cost is fixed at $5. While correct, such a brute-force approach could involve recursive checking or backtracking, which is inefficient for large input sizes.

The key insight is that a greedy strategy works here: always give change using the largest bills available. For a $10 payment, give one $5. For a $20 payment, prioritize giving one $10 and one $5 if possible; otherwise, give three $5 bills. This ensures we preserve smaller bills for future transactions and avoids running out of necessary change.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Consider all combinations of giving change; correct but infeasible for large n
Optimal O(n) O(1) Greedy simulation using counters for $5 and $10 bills; linear pass through input

Algorithm Walkthrough

  1. Initialize two counters, five and ten, to zero. These will track the number of $5 and $10 bills in hand.
  2. Iterate over each bill in the bills array.
  3. If bill is $5, increment the five counter. No change is needed.
  4. If bill is $10, check if at least one $5 is available. If yes, decrement five by one and increment ten by one. If no $5 is available, return false.
  5. If bill is $20, first try to give one $10 and one $5 if both are available. If not, try giving three $5 bills. If neither option is possible, return false.
  6. If the loop completes without returning false, all customers received correct change. Return true.

Why it works: The greedy approach ensures that the largest bills are used for change first, preserving smaller bills for subsequent transactions. The algorithm maintains an invariant: at any point, the counters reflect the exact number of bills available for change, which guarantees correctness.

Python Solution

from typing import List

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

The Python implementation follows the algorithm exactly. Counters for $5 and $10 track available bills, and conditional checks handle each type of incoming bill. The greedy choice ensures correct change is given without using extra space or complex data structures.

Go Solution

func lemonadeChange(bills []int) bool {
    five, ten := 0, 0

    for _, bill := range bills {
        switch bill {
        case 5:
            five++
        case 10:
            if five == 0 {
                return false
            }
            five--
            ten++
        case 20:
            if ten > 0 && five > 0 {
                ten--
                five--
            } else if five >= 3 {
                five -= 3
            } else {
                return false
            }
        }
    }
    return true
}

In Go, we use a switch statement for clarity and maintain two integer counters. Slices handle iteration efficiently, and there is no need for dynamic allocation beyond the input slice. The logic mirrors the Python version.

Worked Examples

Example 1: [5,5,5,10,20]

Step Bill Five Count Ten Count Action
1 5 1 0 Collect $5
2 5 2 0 Collect $5
3 5 3 0 Collect $5
4 10 2 1 Give one $5 change, collect $10
5 20 1 0 Give one $10 and one $5 change

All customers receive change. Return true.

Example 2: [5,5,10,10,20]

Step Bill Five Count Ten Count Action
1 5 1 0 Collect $5
2 5 2 0 Collect $5
3 10 1 1 Give $5 change, collect $10
4 10 0 2 Give $5 change, collect $10
5 20 0 2 Cannot give $15 change

Return false.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through the bills array of length n
Space O(1) Only two integer counters are used regardless of input size

The linear time complexity is optimal because each bill must be checked. Space is constant because we do not need any dynamic data structures to store intermediate states.

Test Cases

# Provided examples
assert Solution().lemonadeChange([5,5,5,10,20]) == True  # basic valid sequence
assert Solution().lemonadeChange([5,5,10,10,20]) == False  # insufficient $5 for final $20

# Edge cases
assert Solution().lemonadeChange([5]) == True  # only one customer, exact change
assert Solution().lemonadeChange([10]) == False  # first customer pays $10, no change
assert Solution().lemonadeChange([20]) == False  # first customer pays $20, no change
assert Solution().lemonadeChange([5,10,5,10,20]) == False  # early $10 prevents change for $20
assert Solution().lemonadeChange([5,5,5,5,10,5,10,10,10,20]) == False  # complex sequence failing at end
assert Solution().lemonadeChange([5,5,5,5,5,5,20,20,20,20]) == False  # too many $20s early
Test Why
[5,5,5,10,20] Valid sequence, change is always available
[5,5,10,10,20] Fails due to insufficient $5 for $20
[5] Single customer edge case
[10] Single $10 payment without $5 available
[20] Single $20 payment without $5 available
[5,10,5,10,20] Early $10 prevents proper change later
[5,5,5,5,10,5,10,10,10,20] Complex sequence failing at last $20
[5,5,5,5,5,5,20,20,20,20] Multiple $20s early with insufficient change

Edge Cases

The first important edge case is when the first customer pays with a $10 or $20 bill. Since we start with zero change, it is impossible to satisfy these transactions, and the implementation correctly returns false.

The second edge case occurs when a $20 payment arrives, and we have multiple combinations of bills to provide change. The greedy strategy ensures we always use one $10 and one $5 if possible, preserving smaller bills for future $10 payments, which avoids running out of change.

The third edge case involves a long sequence of $5 bills followed by several $20 bills. Without careful accounting, one might attempt