We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Lemonade Change

Number: 890

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Meta, Bloomberg, Zalando

Problem Description

Given a list of integers representing the bills customers pay at a lemonade stand (where each lemonade costs $5), determine if you can provide correct change to every customer. Initially, you have no change. The bills can be $5, $10, or $20.

Key Insights

  • You need to simulate the transaction process sequentially.
  • Use counters to keep track of the number of $5 and $10 bills.
  • For a $10 bill, you must have at least one $5 bill for change.
  • For a $20 bill, the preferred strategy is to give one $10 and one $5 if possible; if not, then try three $5 bills.
  • Early termination is possible if at any step you cannot provide the necessary change.

Space and Time Complexity

Time Complexity: O(n), where n is the number of customers (size of the bills array) because we process each bill exactly once.
Space Complexity: O(1), using only a constant amount of extra space for counters.

Solution

We utilize a greedy approach by tracking how many $5 and $10 bills are available at each step. For every transaction:

  1. If a customer pays with a $5 bill, increment the $5 counter.
  2. If a customer pays with a $10 bill, ensure at least one $5 bill is available to provide change. Decrement the $5 counter and increment the $10 counter.
  3. If a customer pays with a $20 bill, first try to provide change by using one $10 bill and one $5 bill. If that is not possible, try using three $5 bills. If neither option is available, return false. This approach ensures that change is provided optimally at each step.

Code Solutions

def lemonadeChange(bills):
    # Initialize counters for $5 and $10 bills.
    five_count, ten_count = 0, 0
    # Process each bill in the list.
    for bill in bills:
        # If the bill is $5, simply increase the $5 counter.
        if bill == 5:
            five_count += 1
        # If the bill is $10, we must provide a $5 bill as change.
        elif bill == 10:
            if five_count == 0:
                return False  # Not enough $5 bill for change.
            five_count -= 1
            ten_count += 1
        # If the bill is $20, try to provide change using one $10 and one $5 bill;
        # if not possible, then use three $5 bills.
        else:
            if ten_count > 0 and five_count > 0:
                ten_count -= 1
                five_count -= 1
            elif five_count >= 3:
                five_count -= 3
            else:
                return False  # Cannot provide change.
    return True
← Back to All Questions