Lemonade Change

The key idea

A $5 bill is the only universal change. Always pay a $20 with a $10 + $5 first, keeping the more flexible $5 bills in reserve. Greedy: spend the least-useful bill that works.

Problem

At a lemonade stand, each lemonade costs 5 dollars. Customers stand in a queue and buy one lemonade each, paying with a 5, 10, or 20 dollar bill. You must give each customer correct change so that the net amount they pay is exactly 5 dollars.

You start with no change in hand. Given an integer array bills where bills[i] is the bill the i-th customer pays with, return true if you can give every customer correct change, and false otherwise.

Constraints

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

Examples

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

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

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

Complexity

Time: O(n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →