#860

Easy

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Lemonade Change

Determine if you can provide exact change to every customer at a lemonade stand using greedy bill management techniques.

array greedy

Problem Statement

You are running a lemonade stand where each lemonade costs $5. Customers arrive in a queue, each paying with a$ 5, $10, or$ 20 bill. You must provide exact change to each customer so that they effectively pay $5.

Initially, you have no change. Given an integer array bills where bills[i] is the bill provided by the ith customer, return true if you can provide correct change to every customer, or false otherwise.

Examples

Example 1

Input: bills = [5,5,5,10,20]

Output: true

From the first 3 customers, we collect three $5 bills in order. From the fourth customer, we collect a$ 10 bill and give back a $5. From the fifth customer, we give a$ 10 bill and a $5 bill. Since all customers got correct change, we output true.

Example 2

Input: bills = [5,5,10,10,20]

Output: false

From the first two customers in order, we collect two $5 bills. For the next two customers in order, we collect a$ 10 bill and give back a $5 bill. For the last customer, we can not give the change of$ 15 back because we only have two $10 bills. Since not every customer received the correct change, the answer is false.

Constraints

1 <= bills.length <= 105
bills[i] is either 5, 10, or 20.

Solution Approach

Track $5 and$ 10 Bills Separately

Maintain counters for $5 and$ 10 bills. Every time a customer pays with a $5 bill, increment the$ 5 counter. For $10, decrement the$ 5 counter and increment the $10 counter. For$ 20, prioritize giving a $10 and a$ 5 bill as change, else use three $5 bills.

Apply Greedy Choice for Change

Always give the largest bills available as change to preserve smaller bills. This ensures that future $10 or$ 20 bills can be accommodated without running out of $5 bills prematurely.

Immediate Failure Detection

Check after each transaction if the necessary change can be given. If at any point you cannot provide correct change, return false immediately. This invariant validation ensures correctness without scanning the array again.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) because each bill is processed once. Space complexity is O(1) since only counters for $5 and$ 10 bills are maintained, independent of the input size.

What Interviewers Usually Probe

Are you tracking the denominations separately to manage change?
Do you prefer giving larger bills first when giving change?
What happens if a $20 bill arrives but you cannot provide$ 15 in change?

Common Pitfalls or Variants

Common pitfalls

Failing to prioritize giving a $10 and a$ 5 when available for a $20 bill.
Not updating the counters correctly for each transaction.
Assuming having any bills is sufficient without checking exact change required.

Follow-up variants

Change amounts could vary, requiring a flexible greedy approach.
Customers may pay with more denominations like $50, testing invariant logic.
Determine the minimum initial change needed to guarantee all customers can be served.

FAQ

What is the main pattern in Lemonade Change?

The problem uses a greedy choice plus invariant validation pattern, giving largest bills first to preserve smaller denominations.

Why do we prioritize giving $10 bills before$ 5 bills as change?

Prioritizing larger bills ensures that smaller $5 bills remain available for future$ 10 or $20 payments, avoiding early exhaustion.

Can this solution handle large arrays efficiently?

Yes, time complexity is O(n) and space complexity is O(1), so it scales efficiently even for up to 105 customers.

What happens if a $20 bill arrives but exact change cannot be given?

The function immediately returns false since the greedy invariant fails and the customer cannot be served correctly.

Do I need to track $20 bills for this problem?

No, $20 bills are only used for giving change; tracking them is unnecessary since only$ 5 and $10 counts are needed for greedy validation.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five = ten = 0
        for v in bills:
            if v == 5:
                five += 1
            elif v == 10:
                ten += 1
                five -= 1
            else:
                if ten:
                    ten -= 1
                    five -= 1
                else:
                    five -= 3
            if five < 0:
                return False
        return True

Solution 2: One-liner

#### TypeScript

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five = ten = 0
        for v in bills:
            if v == 5:
                five += 1
            elif v == 10:
                ten += 1
                five -= 1
            else:
                if ten:
                    ten -= 1
                    five -= 1
                else:
                    five -= 3
            if five < 0:
                return False
        return True

Continue Practicing

#861 score after flipping matrix #857 minimum cost to hire k workers #870 advantage shuffle