Lemonade Change

At a lemonade stand, each lemonade costs $5. Customers are standing in a queue to buy from you and order one at a time.

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.

Return true if and only if you can provide every customer with the correct change.

Examples

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

Output: true

Collect three $5s, give one $5 as change for $10, and give one $10 and one $5 as change for $20.

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

Output: false

You run out of $5 bills for the last customer.

Constraints

• 1 <= bills.length <= 10^5
• bills[i] is either 5, 10, or 20.

Complexity Analysis

Time

O(N)

iterating through the bills array once.

Space

O(1)

only keeping track of counts of $5 and $10 bills.

Test Cases

#1 Change is exact

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

Expected: true

#2 Not enough $5 bills

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

Expected: false