A ferry ticket costs 5. Customers queue up and each pays with a single bill of 5, 10 or 20, in the order given by bills. You start with no money and can only give change from bills you have already collected. Return True if you can give every customer exact change, otherwise False.
Examples
Input: bills = [5, 5, 5, 10, 20]
Output: True
Explanation: The first three pay exactly. The 10 gets one 5 back, the 20 gets 10 + 5 back.
Input: bills = [5, 5, 10, 10, 20]
Output: False
Explanation: After the two 10s you hold no 5s, so the 20 cannot receive 15 in change.
Constraints
0 <= len(bills) <= 10**5; every bill is5,10or20.- An empty queue returns
True. - Target complexity: O(n) time, O(1) extra space.
Goals
- Track how many of each bill you hold as customers arrive
- Choose which bills to hand back when more than one combination works
- Stop early as soon as a customer cannot be served