Lemonade Change - Practice Coding Problems

Lemonade Change - Problem

Array Greedy Easy

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 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 the customer pays $5. Note that you do not have any change in hand at first.

Given an integer array bills where bills[i] is the bill the ith customer pays, return true if you can provide every customer with the correct change, or false otherwise.

Input & Output

Example 1 — Mixed Bills

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

› Output: true

💡 Note: Customer 1-3: pay $5, no change needed. Customer 4: pays $10, give $5 change. Customer 5: pays $20, give $10+$5 change.

Example 2 — Cannot Make Change

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

› Output: false

💡 Note: For the last customer paying $20, we need $15 change but only have $10+$10+$5 available. We cannot make exactly $15.

Example 3 — All Same Bills

$ Input: bills = [5,5,5,5]

› Output: true

💡 Note: All customers pay exact amount ($5), so no change is needed.

Constraints

1 ≤ bills.length ≤ 10⁵
bills[i] is either 5, 10, or 20

Visualization

Tap to expand

Understanding the Visualization

Input

Queue of customers with different bill denominations

Process

Make change using greedy strategy for each customer

Output

Return true if all customers can be served, false otherwise

Key Takeaway

🎯 Key Insight: Greedy strategy works because using larger denominations preserves maximum flexibility for future transactions

Asked in

G Google 12 a Amazon 8 M Microsoft 6 f Facebook 4

The key insight is that a greedy approach works optimally for this currency system. The best approach is to track counts of $5 and $10 bills, and always use the largest denominations first when making change. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Strategy	O(n)	O(1)	Always use the largest denomination bills first for making change
Brute Force Simulation	O(n × 2^k)	O(k)	Simulate each transaction and track all possible change combinations

Greedy Strategy — Algorithm Steps

Track count of $5 and $10 bills
For $10 payment: give one $5 bill as change
For $20 payment: give one $10 and one $5, or three $5 bills

Visualization

Tap to expand

Step-by-Step Walkthrough

Track Bills

Count $5 and $10 bills available

Greedy Choice

For $20: prefer $10+$5 over three $5s

Optimal Result

Always preserves maximum flexibility

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int* bills, int billsSize) {
    int fives = 0;
    int tens = 0;
    
    for (int i = 0; i < billsSize; i++) {
        int bill = bills[i];
        
        if (bill == 5) {
            fives++;
        } else if (bill == 10) {
            if (fives == 0) {
                return false;
            }
            fives--;
            tens++;
        } else if (bill == 20) {
            if (tens > 0 && fives > 0) {
                tens--;
                fives--;
            } else if (fives >= 3) {
                fives -= 3;
            } else {
                return false;
            }
        }
    }
    
    return true;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int bills[1000];
    int count = 0;
    
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char* end = strchr(ptr, ']');
        if (end) *end = '\0';
        
        char* token = strtok(ptr, ",");
        while (token != NULL) {
            bills[count++] = atoi(token);
            token = strtok(NULL, ",");
        }
    }
    
    printf(solution(bills, count) ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the bills array, constant work per customer

✓ Linear Growth

Space Complexity

O(1)

Only store counts of two bill denominations

✓ Linear Space

187.4K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Strategy — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler