529. Lemonade Change
You sell lemonade for $5 a cup. Customers arrive one at a time, each buying one cup and paying with a single bill — $5, $10, or $20 — given in order as the integer array bills.
You open with an empty till: every dollar of change you hand back must come from bills collected earlier in the line. Each customer must receive their exact change immediately, before you serve the next one.
Return true if you can serve the entire line with correct change, and false if some customer would be shortchanged.
Example 1:
Input: bills = [5, 5, 5, 10, 20]
Output: true
Explanation: The first three customers pay exactly. The fourth pays $10 and gets a $5 back. The fifth pays $20 and gets the $10 plus a $5 — the till covers everyone.
Example 2:
Input: bills = [5, 5, 10, 10, 20]
Output: false
Explanation: After the two $10 customers take both $5 bills, the till holds two $10s. The $20 customer needs $15 back, but $10 bills can only make $10 or $20 — impossible.
Constraints:
- 1 ≤ bills.length ≤ 10⁵
- bills[i] is 5, 10, or 20.
Hints:
The only state that matters is how many $5 and $10 bills you are holding — $20 bills never leave the till as change. Simulate the line with two counters.
A $20 payment needs $15 back: either $10 + $5 or three $5s. Prefer spending a $10 first — $5 bills are strictly more flexible (they are the only way to change a $10), so hoard them.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: bills = [5, 5, 5, 10, 20]
Expected output: true