860. Lemonade Change

Intuition

The problem requires determining if we can provide the correct change for each customer in a line, given that customers will pay with a 5,10, or 20 bill. The key is to ensure that for each10 or 20 bill received, we have enough smaller bills (preferably5 bills) to give back the correct change.

Approach

• Initialize two counters, five and ten, to keep track of the number of 5 and10 bills we have.
• Iterate through the array of bills:
• If the bill is $5, increment the five counter.
• If the bill is 10, check if we have at least one5 bill to give as change. If so, decrement the five counter and increment the ten counter. If not, return false.
• If the bill is 20, prioritize giving one10 and one 5 as change (if possible). If not, try to give three5 bills. If neither is possible, return false.
• If we can successfully provide change for all customers, return true.

Complexity

• Time complexity: O(n)

• We only loop through the array of bills once.

• Space complexity: O(1)

• Only a constant amount of extra space is used for the five and ten counters.

Code

```java class Solution { public boolean lemonadeChange(int[] bills) { int five = 0, ten = 0;

    for (int bill : bills) {
        if (bill == 5) {
            five++;
        } else if (bill == 10) {
            if (five == 0) return false;
            five--;
            ten++;
        } else { // bill == 20
            if (ten > 0 && five > 0) {
                ten--;
                five--;
            } else if (five >= 3) {
                five -= 3;
            } else {
                return false;
            }
        }
    }
    return true;
}

}