Leetcode – Lemonade Change Solution in Python

Spread the love

The Lemonade Change problem is an engaging coding challenge on Leetcode, allowing problem solvers to simulate real-world transactions and test their logic. The problem revolves around the concept of making change in a typical vendor-customer transaction scenario. This article provides a comprehensive dive into the problem statement, the underlying logic, the solution strategy, and the implementation in Python.

Problem Statement

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 the given 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 you receive exactly $5 for each lemonade.

Return true if and only if you can provide every customer with correct change.

Constraints:

  • 0 ≤ bills.length ≤ 10000
  • bills[i] ∈ [5, 10, 20]

Examples:

  1. bills = [5,5,5,10,20] → Return true
  2. bills = [5,5,10] → Return true
  3. bills = [10,10] → Return false
  4. bills = [5,5,10,10,20] → Return false

Analysis

The main challenge here is to determine if we can give back the required change for each customer given the bills we have on hand. Let’s break down the change requirements:

  1. If the customer pays with a $5 bill, no change is needed.
  2. If the customer pays with a $10 bill, we need to give back a $5 bill.
  3. If the customer pays with a $20 bill, we have two options:
    • Give back one $10 bill and one $5 bill, or
    • Give back three $5 bills.

From the above, we notice that the $5 bill is crucial for making change. Thus, we should prioritize giving change with $10 bills if we have them.

Solution Strategy

The solution follows a greedy approach:

  1. Maintain a count of $5 and $10 bills.
  2. For each bill in the bills array:
    • If it’s a $5 bill, increment the $5 bill count.
    • If it’s a $10 bill, check if we have a $5 bill to give as change. If yes, decrement the $5 bill count and increment the $10 bill count. If not, return false.
    • If it’s a $20 bill, prioritize giving a $10 bill and a $5 bill as change if possible. Otherwise, give three $5 bills. If we can’t do either, return false.
  3. If we’ve successfully navigated the entire bills array without returning false, then we can provide change to every customer and should return true.

Python Code:

def lemonadeChange(bills: List[int]) -> bool:
    # Initialize bill counters
    five, ten = 0, 0
    
    for bill in bills:
        # Customer pays with $5, no change needed
        if bill == 5:
            five += 1
        # Customer pays with $10, give back $5
        elif bill == 10:
            if five == 0: return False
            five -= 1
            ten += 1
        # Customer pays with $20
        else:
            # Prioritize giving $10 + $5 as change
            if ten > 0 and five > 0:
                ten -= 1
                five -= 1
            # Otherwise, give three $5 bills
            elif five >= 3:
                five -= 3
            # Can't give correct change
            else:
                return False
    return True

Complexity Analysis

  1. Time Complexity: We are iterating through the bills array once, leading to a time complexity of O(n), where n is the number of bills.
  2. Space Complexity: We are using constant space, regardless of the input size, so the space complexity is O(1).

Conclusion

The Lemonade Change problem provides a practical scenario to test one’s skills in handling and processing transactions. Using a greedy approach to always provide change in the most efficient way ensures that all customers can be catered to. While the problem seems simple, it emphasizes the importance of understanding and handling different transaction cases to ensure smooth operations, which is fundamental in real-world vending scenarios.

Leave a Reply