algoadvance

Leetcode 860. Lemonade Change

Problem Statement

The problem is taken from LeetCode and is as follows:

At a lemonade stand, each lemonade costs $5. Customers are standing in a queue to buy from you, and they order one at a time (in the order specified by the given integer array bills where bills[i] is the bill the i-th customer pays). 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 based only on the bills you have previously received.

Return true if you can provide every customer with the correct change, or false otherwise.

Clarifying Questions

To ensure the problem is fully understood, let’s clarify potential questions:

  1. Can the initial amount of money be assumed to be zero?
    • Yes, you start with no money.
  2. Is the input bills array guaranteed to only contain valid bill denominations (i.e., $5, $10, $20)?
    • Yes, as per the problem statement, bills only contains these denominations.
  3. Should we handle cases where no bills are passed (empty array)?
    • Yes, if no bills are passed, we should return true as no transaction means no need to change.

Strategy

To solve this problem, follow these steps:

  1. Maintain a count for $5 and $10 bills since $20 bills don’t need to be tracked individually for giving change (as they can’t contribute to giving any meaningful change).

  2. Iterate through the list of bills received:
    • If a customer gives a $5 bill, simply increase the count of $5 bills.
    • If a customer gives a $10 bill, decrease the count of $5 bills by one (for change) and increase the count of $10 bills. If you don’t have a $5 bill to give as change, return false.
    • If a customer gives a $20 bill, try to give one $10 bill and one $5 bill as change, if possible. If not, then try to give three $5 bills. If neither is possible, return false.
  3. If you can handle all customers correctly, return true.

Code

Here’s the solution implemented in C++:

#include <vector>

bool lemonadeChange(std::vector<int>& bills) {
    int count5 = 0, count10 = 0;
    
    for (int bill : bills) {
        if (bill == 5) {
            count5++;
        } else if (bill == 10) {
            if (count5 <= 0) return false;
            count5--;
            count10++;
        } else {  // bill == 20
            if (count10 > 0 && count5 > 0) {
                count10--;
                count5--;
            } else if (count5 >= 3) {
                count5 -= 3;
            } else {
                return false;
            }
        }
    }
    
    return true;
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI