# LeetCode 860: Lemonade Change

## Problem Restatement

Each lemonade costs `$5`.

Customers stand in a queue. Each customer buys exactly one lemonade and pays with one bill.

The bill can be:

```python
5, 10, or 20
```

We start with no money.

For each customer, we must give the correct change immediately, using only bills received from earlier customers.

Return `True` if we can give correct change to every customer. Otherwise, return `False`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `bills`, where `bills[i]` is the bill paid by the `i`th customer |
| Output | `True` if every customer can receive correct change |
| Constraint | `1 <= bills.length <= 100000` |
| Bill values | Each bill is `5`, `10`, or `20` |

Function shape:

```python
class Solution:
    def lemonadeChange(self, bills: list[int]) -> bool:
        ...
```

## Examples

Example 1:

```python
bills = [5, 5, 5, 10, 20]
```

Process the customers in order:

| Bill | Action | Register |
|---|---|---|
| `5` | No change needed | one `$5` |
| `5` | No change needed | two `$5` |
| `5` | No change needed | three `$5` |
| `10` | Give one `$5` | two `$5`, one `$10` |
| `20` | Give one `$10` and one `$5` | one `$5`, zero `$10` |

We can serve every customer, so the answer is:

```python
True
```

Example 2:

```python
bills = [5, 5, 10, 10, 20]
```

Process the customers:

| Bill | Action | Register |
|---|---|---|
| `5` | No change needed | one `$5` |
| `5` | No change needed | two `$5` |
| `10` | Give one `$5` | one `$5`, one `$10` |
| `10` | Give one `$5` | zero `$5`, two `$10` |
| `20` | Need `$15` change | impossible |

For the last customer, we have two `$10` bills but no `$5` bill.

We cannot give exact `$15` change, so the answer is:

```python
False
```

## First Thought: Track Total Money

One might try to track only the total money in the register.

That is not enough.

For example, if we have:

```python
two $10 bills
```

the total is `$20`, but we still cannot give `$15` change because we need either:

```python
$10 + $5
```

or:

```python
$5 + $5 + $5
```

So the denominations matter.

We need to count the actual bills.

## Key Insight

We only need to track `$5` and `$10` bills.

A `$20` bill is never useful for change, because customers only pay with `$5`, `$10`, or `$20`, and every lemonade costs `$5`.

When a customer pays:

| Bill | Change needed |
|---|---|
| `$5` | `$0` |
| `$10` | `$5` |
| `$20` | `$15` |

For a `$20` bill, there are two ways to give `$15` change:

1. One `$10` and one `$5`
2. Three `$5` bills

We should prefer:

```python
$10 + $5
```

when possible.

This preserves more `$5` bills, and `$5` bills are the most flexible because they are needed for both `$10` and `$20` customers.

## Algorithm

Maintain two counters:

```python
five = 0
ten = 0
```

Process each bill in order.

If the bill is `5`:

1. Increase `five`.

If the bill is `10`:

1. We need one `$5` change.
2. If `five == 0`, return `False`.
3. Otherwise, decrease `five` and increase `ten`.

If the bill is `20`:

1. We need `$15` change.
2. If we have one `$10` and one `$5`, use them.
3. Otherwise, if we have at least three `$5` bills, use them.
4. Otherwise, return `False`.

If all customers are processed, return `True`.

## Correctness

The algorithm processes customers in the given order, which is necessary because change can only come from earlier customers.

For a `$5` bill, no change is needed, so adding one `$5` bill to the register is correct.

For a `$10` bill, the only possible exact change is one `$5` bill. If no `$5` bill is available, serving this customer is impossible. Otherwise, giving one `$5` and keeping the `$10` bill is forced.

For a `$20` bill, exact change is `$15`. The possible useful combinations are one `$10` plus one `$5`, or three `$5` bills. If one `$10` and one `$5` are available, using them is safe because it preserves two extra `$5` bills compared with using three `$5` bills. Since future `$10` customers require `$5` bills, preserving `$5` bills cannot make future transactions worse.

If neither valid change combination is available, no exact change can be given, so returning `False` is correct.

Thus, if the algorithm finishes all customers, every transaction has been served with correct change.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We process each bill once |
| Space | `O(1)` | We store only two counters |

## Implementation

```python
class Solution:
    def lemonadeChange(self, bills: list[int]) -> bool:
        five = 0
        ten = 0

        for bill in bills:
            if bill == 5:
                five += 1

            elif bill == 10:
                if five == 0:
                    return False

                five -= 1
                ten += 1

            else:
                if ten > 0 and five > 0:
                    ten -= 1
                    five -= 1
                elif five >= 3:
                    five -= 3
                else:
                    return False

        return True
```

## Code Explanation

We start with no change:

```python
five = 0
ten = 0
```

When a customer pays with `$5`:

```python
if bill == 5:
    five += 1
```

we simply keep the bill.

When a customer pays with `$10`:

```python
elif bill == 10:
```

we must return one `$5`.

If none is available:

```python
if five == 0:
    return False
```

Otherwise, we give one `$5` and keep the `$10`:

```python
five -= 1
ten += 1
```

When a customer pays with `$20`, we first try to give one `$10` and one `$5`:

```python
if ten > 0 and five > 0:
    ten -= 1
    five -= 1
```

If that is not possible, we try three `$5` bills:

```python
elif five >= 3:
    five -= 3
```

If neither works:

```python
else:
    return False
```

After all bills are processed, every customer received correct change:

```python
return True
```

## Testing

```python
def test_lemonade_change():
    s = Solution()

    assert s.lemonadeChange([5, 5, 5, 10, 20]) is True
    assert s.lemonadeChange([5, 5, 10, 10, 20]) is False
    assert s.lemonadeChange([5, 10, 5, 5, 20]) is True
    assert s.lemonadeChange([10]) is False
    assert s.lemonadeChange([5, 20]) is False
    assert s.lemonadeChange([5, 5, 5, 20]) is True
    assert s.lemonadeChange([5, 5, 10]) is True

    print("all tests passed")

test_lemonade_change()
```

Test meaning:

| Test | Why |
|---|---|
| `[5, 5, 5, 10, 20]` | Standard valid case |
| `[5, 5, 10, 10, 20]` | Has money but wrong denominations |
| `[5, 10, 5, 5, 20]` | Uses one `$10` and one `$5` for change |
| `[10]` | First customer cannot receive change |
| `[5, 20]` | Not enough `$5` bills for `$20` |
| `[5, 5, 5, 20]` | Uses three `$5` bills |
| `[5, 5, 10]` | Simple valid ending |