How do you solve Lemonade Change on LeetCode?

Lemonade Change (LeetCode #860) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Always prioritize giving change with larger bills first when possible.

What is the time complexity of Lemonade Change?

The optimal solution for Lemonade Change runs in O(n) time and uses O(1) space. The time complexity is O(n) because we only traverse the bills array once, making it efficient even for larger inputs.

What is the brute force solution for Lemonade Change?

The brute force approach for Lemonade Change is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute force approach, we can simulate each transaction step-by-step, checking if we can provide the correct change for each customer. This method is straightforward but inefficient as it checks every possible combination of bills. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Lemonade Change?

Lemonade Change uses the following concepts: Array, Greedy. The recommended patterns to study are: Greedy, Array.

What are the interview tips for Lemonade Change?

Explain your thought process clearly as you code. Consider edge cases, such as starting with a $10 or $20 bill. Practice similar problems to get comfortable with greedy algorithms.

What are common mistakes when solving Lemonade Change?

Failing to check if enough $5 bills are available for a $10 bill. Not considering the order of bills when providing change.

#860

Lemonade Change

Easy

ArrayGreedyGreedyArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution uses a greedy approach to keep track of the number of $5 and $10 bills we have. This allows us to efficiently determine if we can provide change for each customer without unnecessary checks.

⚙️

Algorithm

6 steps

1Step 1: Initialize counters for $5 and $10 bills to zero.
2Step 2: Iterate through each bill in the bills array.
3Step 3: For each $5 bill, increment the $5 counter.
4Step 4: For each $10 bill, check if a $5 bill is available; if yes, decrement the $5 counter and increment the $10 counter.
5Step 5: For each $20 bill, check if we can provide change using one $10 and one $5 bill or three $5 bills; update the counters accordingly.
6Step 6: If at any point we cannot provide the required change, return false. If we finish the loop, return true.

solution.py20 lines

1def lemonadeChange(bills):
2    five, ten = 0, 0
3    for bill in bills:
4        if bill == 5:
5            five += 1
6        elif bill == 10:
7            if five > 0:
8                five -= 1
9                ten += 1
10            else:
11                return False
12        elif bill == 20:
13            if ten > 0 and five > 0:
14                ten -= 1
15                five -= 1
16            elif five >= 3:
17                five -= 3
18            else:
19                return False
20    return True

ℹ

Complexity note: The time complexity is O(n) because we only traverse the bills array once, making it efficient even for larger inputs.

1Always prioritize giving change with larger bills first when possible.
2Keep track of the number of $5 and $10 bills to make change efficiently.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.