Pular para o conteúdo principal

Lemonade Change

This question is asked by Amazon. You're running a popsicle stand where each popsicle costs $5. Each customer you encountered pays with either a $5 bill, a $10 bill, or a $20 bill and only buys a single popsicle. The customers that come to your stand come in the ordered given by the customers array where customers[i] represents the bill the ith customer pays with. Starting with $0, return whether or not you can serve all the given customers while also giving the correct amount of change.

Example(s)​

Example 1:

Input: customers = [5, 10]
Output: true
Explanation:
Customer 1: Pays $5, no change needed
  Cash: $5 bills = 1, $10 bills = 0
Customer 2: Pays $10, needs $5 change
  Give $5 change, cash: $5 bills = 0, $10 bills = 1
Can serve all customers.

Example 2:

Input: customers = [10]
Output: false
Explanation:
Customer 1: Pays $10, needs $5 change
  But we have $0, cannot give change
Cannot serve customer.

Example 3:

Input: customers = [5, 5, 5, 10, 20]
Output: true
Explanation:
Customer 1: Pays $5, no change needed
  Cash: $5 = 1, $10 = 0
Customer 2: Pays $5, no change needed
  Cash: $5 = 2, $10 = 0
Customer 3: Pays $5, no change needed
  Cash: $5 = 3, $10 = 0
Customer 4: Pays $10, needs $5 change
  Give $5 change, cash: $5 = 2, $10 = 1
Customer 5: Pays $20, needs $15 change
  Give $10 + $5 change, cash: $5 = 1, $10 = 0
Can serve all customers.

Example 4:

Input: customers = [5, 5, 10, 10, 20]
Output: false
Explanation:
Customer 1: Pays $5, cash: $5 = 1
Customer 2: Pays $5, cash: $5 = 2
Customer 3: Pays $10, give $5 change, cash: $5 = 1, $10 = 1
Customer 4: Pays $10, give $5 change, cash: $5 = 0, $10 = 2
Customer 5: Pays $20, needs $15 change
  Need $10 + $5 or 3 × $5, but we have $5 = 0
Cannot give change.

Solution​

The solution uses Greedy Algorithm:

  1. Track cash: Keep count of $5 and $10 bills we have
  2. Process customers: For each customer payment:
    • $5: Take it, no change needed
    • $10: Give $5 change (need one $5 bill)
    • $20: Give $15 change (prefer $10 + $5, else 3 × $5)
  3. Check feasibility: Return false if we can't give change

JavaScript Solution - Greedy

/**
* Check if we can serve all customers with correct change
* @param {number[]} customers - Array of customer payments (5, 10, or 20)
* @return {boolean} - Whether we can serve all customers
*/
function lemonadeChange(customers) {
let five = 0;  // Count of $5 bills
let ten = 0;   // Count of $10 bills

for (const bill of customers) {
  if (bill === 5) {
    // Customer pays $5, no change needed
    five++;
  } else if (bill === 10) {
    // Customer pays $10, need to give $5 change
    if (five === 0) {
      return false; // Cannot give change
    }
    five--;
    ten++;
  } else if (bill === 20) {
    // Customer pays $20, need to give $15 change
    // Prefer giving $10 + $5 (greedy: preserve $5 bills)
    if (ten > 0 && five > 0) {
      ten--;
      five--;
    } else if (five >= 3) {
      // Give 3 × $5 if we don't have $10 + $5
      five -= 3;
    } else {
      return false; // Cannot give change
    }
  }
}

return true; // Served all customers
}

// Test cases
console.log('Example 1:', lemonadeChange([5, 10])); 
// true

console.log('Example 2:', lemonadeChange([10])); 
// false

console.log('Example 3:', lemonadeChange([5, 5, 5, 10, 20])); 
// true

console.log('Example 4:', lemonadeChange([5, 5, 10, 10, 20])); 
// false
Output:
Click "Run Code" to execute the code and see the results.

Complexity​

  • Time Complexity: O(n) - Where n is the number of customers. We iterate through the customers array once.
  • Space Complexity: O(1) - Only using a constant amount of extra space to track $5 and $10 bills.

Approach​

The solution uses Greedy Algorithm:

  1. Track cash:

    • Keep count of $5 bills and $10 bills we have
    • We don't need to track $20 bills (we give them as change, but never use them)

  2. Process each customer:

    • $5 payment: Take it, increment $5 count (no change needed)
    • $10 payment: Need to give $5 change
      • If we have a $5 bill, give it and increment $10 count
      • Otherwise, return false
    • $20 payment: Need to give $15 change
      • Prefer: Give one $10 and one $5 (greedy: preserves $5 bills for future $10 customers)
      • Else: Give three $5 bills
      • Otherwise, return false

  3. Greedy choice:

    • When giving change for $20, prefer $10 + $5 over 3 × $5
    • This preserves $5 bills which are more useful for $10 customers

Key Insights​

  • Greedy algorithm: Prefer giving $10 + $5 for $20 payments
  • Track only $5 and $10: $20 bills are received but not used for change
  • Preserve $5 bills: They're needed for $10 customers
  • O(n) time: Single pass through customers
  • O(1) space: Only track two counts

Step-by-Step Example​

Let's trace through Example 3: customers = [5, 5, 5, 10, 20]

customers = [5, 5, 5, 10, 20]
five = 0, ten = 0

Customer 1: Pays $5
  five = 1, ten = 0
  No change needed

Customer 2: Pays $5
  five = 2, ten = 0
  No change needed

Customer 3: Pays $5
  five = 3, ten = 0
  No change needed

Customer 4: Pays $10, needs $5 change
  Check: five > 0? Yes (five = 3)
  Give $5 change: five = 2, ten = 1

Customer 5: Pays $20, needs $15 change
  Option 1: ten > 0 and five > 0? Yes (ten = 1, five = 2)
    Give $10 + $5: ten = 0, five = 1
  Success!

Result: true (served all customers)

Let's trace through Example 4: customers = [5, 5, 10, 10, 20]

customers = [5, 5, 10, 10, 20]
five = 0, ten = 0

Customer 1: Pays $5
  five = 1, ten = 0

Customer 2: Pays $5
  five = 2, ten = 0

Customer 3: Pays $10, needs $5 change
  Check: five > 0? Yes (five = 2)
  Give $5 change: five = 1, ten = 1

Customer 4: Pays $10, needs $5 change
  Check: five > 0? Yes (five = 1)
  Give $5 change: five = 0, ten = 2

Customer 5: Pays $20, needs $15 change
  Option 1: ten > 0 and five > 0? No (ten = 2, five = 0)
  Option 2: five >= 3? No (five = 0)
  Cannot give change!

Result: false (cannot serve customer 5)

Visual Representation​

Example 3: customers = [5, 5, 5, 10, 20]

Cash state after each customer:
  Start:     $5 = 0, $10 = 0
  After $5:  $5 = 1, $10 = 0
  After $5:  $5 = 2, $10 = 0
  After $5:  $5 = 3, $10 = 0
  After $10: $5 = 2, $10 = 1  (gave $5 change)
  After $20: $5 = 1, $10 = 0  (gave $10 + $5 change)

Result: true ✓

Example 4: customers = [5, 5, 10, 10, 20]

Cash state after each customer:
  Start:     $5 = 0, $10 = 0
  After $5:  $5 = 1, $10 = 0
  After $5:  $5 = 2, $10 = 0
  After $10: $5 = 1, $10 = 1  (gave $5 change)
  After $10: $5 = 0, $10 = 2  (gave $5 change)
  After $20: Need $15 change
    Need: $10 + $5 or 3 × $5
    Have: $10 = 2, $5 = 0
    Cannot give change! ✗

Result: false

Edge Cases​

  • Empty array: Return true (no customers to serve)
  • All $5: Return true (no change needed)
  • All $10: Return false (need $5 for change, but start with $0)
  • All $20: Return false (need $15 change, but start with $0)
  • First customer $10 or $20: Return false (no change available)

Important Notes​

  • Greedy choice: Prefer $10 + $5 for $20 payments
  • Track $5 and $10: $20 bills received but not used for change
  • Preserve $5 bills: More useful for $10 customers
  • O(n) time: Single pass through customers
  • O(1) space: Only track two counts

Why Greedy Works​

Key insight:

  • When giving change for $20, we have two options:
    • Give $10 + $5 (uses one $10 and one $5)
    • Give 3 × $5 (uses three $5)
  • We should prefer $10 + $5 because:
    • $5 bills are more valuable (needed for $10 customers)
    • Using a $10 bill when possible preserves $5 bills
    • This greedy choice is optimal

Proof sketch:

  • If we can serve customers with greedy, we can serve them with any strategy
  • If we cannot serve with greedy, we cannot serve with any strategy
  • The greedy choice (prefer $10 + $5) maximizes future flexibility
  • Coin Change: Similar change-making problem
  • Assign Cookies: Different greedy problem
  • Queue Reconstruction by Height: Different greedy problem
  • Non-overlapping Intervals: Different greedy problem

Takeaways​

  • Greedy algorithm solves this efficiently
  • Prefer $10 + $5 for $20 payments (preserves $5 bills)
  • Track only $5 and $10 bills
  • O(n) time single pass through customers
  • O(1) space only track two counts
  • Classic greedy problem with practical applications