Skip to main content
Back to ChallengesLemonade ChangeEasy 20 min

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
Output
Click "Run Code" to see output here...