Lemonade Change | Leetcode 860 | Greedy Solution

The Lemonade Change problem is a very popular coding interview question and a classic example of applying the Greedy Algorithm. It revolves around handling money transactions in the simplest possible way while ensuring that correct change is always provided.

In this blog, we will carefully understand the problem, analyze why a greedy approach is the best choice here, and then go through the optimal Python solution with explanation and complexity analysis.

Here’s the [Problem Link] to begin with.

Problem Statement – What Does the Problem Say?

You are running a lemonade stand where each lemonade costs 5 dollars. Customers come in a queue, and each one pays using a bill of 5, 10, or 20 dollars.

You must provide the correct change to each customer. Initially, you have no money in hand.

Your task: Return True if you can give change to every customer in the queue, otherwise return False.

Example 1:

Input: bills = [5,5,5,10,20]
Output: True
Explanation:
- Customer 1 pays 5 → no change needed.  
- Customer 2 pays 5 → no change needed.  
- Customer 3 pays 5 → no change needed.  
- Customer 4 pays 10 → give back one 5.  
- Customer 5 pays 20 → give back one 10 and one 5.  
All customers receive correct change, so the answer is True.

Example 2:

Input: bills = [5,5,10,10,20]
Output: False
Explanation:
- Customer 1 pays 5 → no change needed.  
- Customer 2 pays 5 → no change needed.  
- Customer 3 pays 10 → give back one 5.  
- Customer 4 pays 10 → give back one 5.  
- Customer 5 pays 20 → need 15 as change, but only two 10s available (no 5).  
Cannot give correct change, so the answer is False.

So the challenge is to simulate the process and ensure the right amount of change can always be given.

Intuition and Approach (Optimal – Greedy)

The greedy approach works perfectly for this problem. The key observation is:

• Since lemonade costs 5, we only ever need to give change in multiples of 5.
• We must prioritize giving larger bills first (10 + 5) before using smaller bills (three 5s).

Steps to Solve:

1. Keep track of how many 5-dollar and 10-dollar bills you currently have.
2. For each customer:
   • If they pay with a 5, just increase the count of 5s.
   • If they pay with a 10, you must give back one 5.
   • If they pay with a 20, the best option is:
     • First try to give one 10 and one 5.
     • If not possible, then try to give three 5s.
     • If neither is possible, return False.
3. If all customers can be served with correct change, return True.

This greedy choice ensures that smaller bills are preserved for future customers where only small change might work.

Code Implementation

Here’s the Python code for the Lemonade Change problem using the greedy method (with added comments for clarity):

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        n = len(bills)
        five = 0   # count of $5 bills
        ten = 0    # count of $10 bills
        
        for i in range(0, n):
            if bills[i] == 5:
                five += 1
            elif bills[i] == 10:
                if five >= 1:
                    five -= 1
                    ten += 1
                else:
                    return False
            else:  # customer pays with 20
                if ten >= 1 and five >= 1:
                    # best case: give one $10 and one $5
                    five -= 1
                    ten -= 1
                elif five >= 3:
                    # otherwise: give three $5 bills
                    five -= 3
                else:
                    return False
                    
        return True

Code Explanation

• The variables five and ten keep track of how many 5-dollar and 10-dollar bills you have at any point.
• When a customer pays:
  • If they use a 5, you just keep it.
  • If they use a 10, you must give back one 5.
  • If they use a 20, you prefer giving one 10 and one 5 (better strategy to save smaller bills). If that is not possible, then you give three 5s.
• If neither option is possible, return False immediately.
• If you process the entire queue successfully, return True.

This approach ensures you always have the correct change in the most efficient way.

Time and Space Complexity

• Time Complexity:
  • We only iterate through the list of customers once.
  • O(n) where n = number of customers.
• Space Complexity:
  • We only use two counters (five and ten).
  • O(1) constant extra space.

This makes the solution both efficient and optimal.

Conclusion

The Lemonade Change problem is a classic example of a Greedy Algorithm where you need to make local optimal choices (giving larger bills first when returning change) to achieve the global optimal result.

By simulating each transaction step by step and keeping track of 5 and 10 dollar bills, we can ensure that the change is always given correctly in O(n) time and O(1) space.

This problem is a perfect demonstration of why greedy strategies often lead to the simplest and most efficient solutions.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.