algoadvance

Leetcode 860. Lemonade Change

Problem Statement

Suppose you are running a lemonade stand. Customers are standing in a queue to buy from you and order one cup of lemonade each. Each lemonade costs $5. Customers can only pay with a $5, $10, or $20 bill. You must provide the correct change to each customer so that the net transaction leaves you with appropriate denominations for future customers. Return true if you can provide every customer with correct change, and false otherwise.

Example 1:

Input: [5,5,5,10,20]
Output: true
Explanation: 
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 the customers got correct change, we output true.

Example 2:

Input: [5,5,10]
Output: true

Example 3:

Input: [10,10]
Output: false

Example 4:

Input: [5,5,10,10,20]
Output: false
Explanation: 
From the first two customers, we collect two $5 bills.
For the next two customers, we collect a $10 bill and give back a $5 bill.
For the last customer, we cannot 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.

Clarifying Questions

  1. Q: What should we return if the input list is empty?
    • A: You should return true because there are no customers, so no change needs to be made.
  2. Q: Are there constraints on the number of bills or length of the bills array?
    • A: Constraints are typically such that the input size is manageable within a reasonable time frame for execution.
  3. Q: Can we assume inputs are always valid and strictly follow the mentioned denominations?
    • A: Yes, you can assume the input list strictly contains 5, 10, and 20.

Strategy

  1. Use counters to track the number of $5 and $10 bills you have.
  2. Iterate over each bill in the bills array:
    • If a customer pays with a $5 bill, increment the $5 bill counter.
    • If a customer pays with a $10 bill, check if you have a $5 bill for change. If yes, decrement your $5 bill counter and increment the $10 bill counter. If not, return false.
    • If a customer pays with a $20 bill, check if you have a $10 bill and a $5 bill for change first. If so, decrement both counters. If not, check if you have three $5 bills for change. If you don’t have enough change, return false.
  3. If you successfully give change to all customers, return true.

Code

public class LemonadeChange {
    public boolean lemonadeChange(int[] bills) {
        int fiveCount = 0, tenCount = 0;
        
        for (int bill : bills) {
            if (bill == 5) {
                fiveCount++;
            } else if (bill == 10) {
                if (fiveCount == 0) {
                    return false;
                }
                fiveCount--;
                tenCount++;
            } else { // bill == 20
                if (tenCount > 0 && fiveCount > 0) {
                    tenCount--;
                    fiveCount--;
                } else if (fiveCount >= 3) {
                    fiveCount -= 3;
                } else {
                    return false;
                }
            }
        }
        
        return true;
    }

    public static void main(String[] args) {
        LemonadeChange lc = new LemonadeChange();
        int[] bills1 = {5, 5, 5, 10, 20};
        System.out.println(lc.lemonadeChange(bills1)); // true
        int[] bills2 = {5, 5, 10};
        System.out.println(lc.lemonadeChange(bills2)); // true
        int[] bills3 = {10, 10};
        System.out.println(lc.lemonadeChange(bills3)); // false
        int[] bills4 = {5, 5, 10, 10, 20};
        System.out.println(lc.lemonadeChange(bills4)); // false
    }
}

Time Complexity

The time complexity of the solution is O(n) where n is the number of elements in the bills array. This is because we are iterating through each bill exactly once and performing constant time operations within the loop.

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