Domain 1EasyCORE

Lemonade Change

The problem involves managing cash transactions at a lemonade stand where each lemonade costs $5. Customers pay with either a $5, $10, or $20 bill. The task is to determine if it's possible to provide the correct change for every customer in the queue.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Greedy

860. Lemonade Change

Model: qwen2.5-coder:14b
Topics: Greedy
FAANG asked: 0
Acceptance rate: 51.9%


Problem Breakdown

The problem involves managing cash transactions at a lemonade stand where each lemonade costs 5.Customerspaywitheithera5. Customers pay with either a 5, 10,or10, or 20 bill. The task is to determine if it’s possible to provide the correct change for every customer in the queue.

Inputs:

  • bills: A list of integers representing the bills customers use to pay for lemonades.

Outputs:

  • A boolean value (true or false) indicating whether it’s possible to provide the correct change to all customers.

Implicit Constraints and Edge Cases:

  • The input list can be empty, in which case the output should be true since no transactions are needed.
  • The bills will only be 5,5, 10, or $20.
  • If a customer pays with a 10bill,youmustreturnone10 bill, you must return one 5 bill as change.
  • If a customer pays with a 20bill,youcanreturneitherthree20 bill, you can return either three 5 bills or one 10andone10 and one 5 bill as change.

Intuition

A brute-force approach would involve checking all possible combinations of bills to make the correct change. However, this is inefficient due to its high time complexity (O(n^2) in the worst case).

The key insight is to use a greedy algorithm. By always trying to give back the largest denomination of bills first, we can ensure that we use the fewest number of bills and have the best chance of making correct change.

Approach

  1. Initialize two counters: five_count for 5billsand‘tencount‘for5 bills and `ten_count` for 10 bills.
  2. Iterate through each bill in the input list:
    • If the bill is $5, increment the five_count.
    • If the bill is 10,decrementthe‘fivecount‘(sinceweneedtogivebackone10, decrement the `five_count` (since we need to give back one 5 bill) and increment the ten_count.
    • If the bill is 20,trytogivebackone20, try to give back one 10 and one 5bill.Ifthat′snotpossible,trytogivebackthree5 bill. If that's not possible, try to give back three 5 bills.
  3. After processing each bill, check if the counters are valid (i.e., five_count should never be negative).
  4. If all bills can be processed without running out of change, return true. Otherwise, return false.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the input list bills. We iterate through the list once.
  • Space Complexity: O(1). We use a constant amount of extra space for the counters.

Solution

def lemonadeChange(bills):
    five_count = 0
    ten_count = 0
    
    for bill in bills:
        if bill == 5:
            five_count += 1
        elif bill == 10:
            if five_count > 0:
                five_count -= 1
                ten_count += 1
            else:
                return False
        elif bill == 20:
            if ten_count > 0 and five_count > 0:
                ten_count -= 1
                five_count -= 1
            elif five_count >= 3:
                five_count -= 3
            else:
                return False
    
    return True

Edge Cases Handled

  • Empty Input: The function returns true since no transactions are needed.
  • **All 5Bills:∗∗Thefunctioncorrectlycountsthenumberof5 Bills:** The function correctly counts the number of 5 bills and returns true.
  • Mixed 10and10 and 20 Bills: The function checks if it can provide the correct change for each bill, returning false if it cannot.