# LeetCode 799: Champagne Tower

## Problem Restatement

We stack glasses in a pyramid.

The first row has `1` glass, the second row has `2` glasses, the third row has `3` glasses, and so on.

Each glass can hold exactly `1` cup of champagne.

We pour `poured` cups into the top glass. If a glass receives more than `1` cup, it keeps `1` cup and splits the extra champagne equally between the two glasses below it.

Given `query_row` and `query_glass`, return how much champagne is in that glass after the pouring stops. The answer is between `0` and `1`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `poured`, `query_row`, and `query_glass` |
| Output | Amount of champagne in the queried glass |
| Glass capacity | `1` cup |
| Overflow rule | Extra amount splits equally to the two glasses below |
| Indexing | Rows and glasses are `0`-indexed |

Function shape:

```python
class Solution:
    def champagneTower(
        self,
        poured: int,
        query_row: int,
        query_glass: int
    ) -> float:
        ...
```

## Examples

Example 1:

```python
poured = 1
query_row = 1
query_glass = 1
```

Only the top glass receives champagne.

It holds exactly `1` cup and does not overflow.

So the queried glass has:

```python
0.0
```

Example 2:

```python
poured = 2
query_row = 1
query_glass = 1
```

The top glass keeps `1` cup.

The extra `1` cup splits evenly to the two glasses in row `1`.

Each receives:

```python
0.5
```

So the answer is:

```python
0.5
```

Example 3:

```python
poured = 100000009
query_row = 33
query_glass = 17
```

Large poured values are allowed.

The simulation still only needs to process rows up to `query_row`.

## First Thought: Simulate Every Drop

A direct but poor idea is to simulate champagne one unit at a time.

That would be too slow when `poured` is very large.

Instead, we should treat champagne as continuous amounts and propagate overflow row by row.

## Key Insight

Each glass only affects the row directly below it.

So we can use dynamic programming.

Let:

```python
tower[row][glass]
```

be the amount of champagne that reaches that glass.

Start with:

```python
tower[0][0] = poured
```

Then process rows from top to bottom.

If a glass has more than `1` cup, the overflow is:

```python
overflow = tower[row][glass] - 1
```

Each child receives:

```python
overflow / 2
```

The current glass is capped at `1`.

## Algorithm

1. Create a 2D array large enough up to `query_row + 1`.
2. Put all poured champagne into `tower[0][0]`.
3. For each row from `0` to `query_row`:
   1. For each glass in that row:
      1. If it contains more than `1`, compute overflow.
      2. Cap it at `1`.
      3. Add half the overflow to each glass below.
4. Return `tower[query_row][query_glass]`.

## Correctness

The top glass receives exactly `poured` cups, so initializing `tower[0][0] = poured` is correct.

For any glass, if it receives at most `1` cup, it keeps all of it and sends nothing downward. If it receives more than `1` cup, it keeps exactly `1` cup and splits the extra amount equally between the two glasses below it. This is exactly how the algorithm updates the next row.

The algorithm processes rows from top to bottom. By the time it processes a glass, all champagne that can flow into that glass from the row above has already been added. Therefore, its overflow can be computed correctly.

By applying the same rule to every glass up to the queried row, the algorithm computes the final amount in the queried glass. Since each glass is capped at `1`, the returned value is valid.

## Complexity

Let `r = query_row`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(r^2)` | We process all glasses up to the queried row |
| Space | `O(r^2)` | The DP table stores rows up to `query_row + 1` |

Since LeetCode limits the tower to 100 rows, this is small.

## Implementation

```python
class Solution:
    def champagneTower(
        self,
        poured: int,
        query_row: int,
        query_glass: int
    ) -> float:
        tower = [[0.0] * (query_row + 2) for _ in range(query_row + 2)]
        tower[0][0] = float(poured)

        for row in range(query_row + 1):
            for glass in range(row + 1):
                if tower[row][glass] > 1.0:
                    overflow = tower[row][glass] - 1.0
                    tower[row][glass] = 1.0

                    tower[row + 1][glass] += overflow / 2.0
                    tower[row + 1][glass + 1] += overflow / 2.0

        return tower[query_row][query_glass]
```

## Code Explanation

The DP table stores champagne amounts:

```python
tower = [[0.0] * (query_row + 2) for _ in range(query_row + 2)]
```

We allocate `query_row + 2` so that writing to `row + 1` is always safe during processing.

All champagne starts at the top:

```python
tower[0][0] = float(poured)
```

For each glass, if it overflows:

```python
if tower[row][glass] > 1.0:
```

we compute the extra amount:

```python
overflow = tower[row][glass] - 1.0
```

cap the current glass:

```python
tower[row][glass] = 1.0
```

and split the overflow:

```python
tower[row + 1][glass] += overflow / 2.0
tower[row + 1][glass + 1] += overflow / 2.0
```

Finally, return the queried glass:

```python
return tower[query_row][query_glass]
```

## Space-Optimized Version

Only the current row and next row are needed.

```python
class Solution:
    def champagneTower(
        self,
        poured: int,
        query_row: int,
        query_glass: int
    ) -> float:
        row = [float(poured)]

        for _ in range(query_row):
            next_row = [0.0] * (len(row) + 1)

            for i, amount in enumerate(row):
                overflow = max(0.0, amount - 1.0)
                next_row[i] += overflow / 2.0
                next_row[i + 1] += overflow / 2.0

            row = next_row

        return min(1.0, row[query_glass])
```

## Testing

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

    assert s.champagneTower(1, 1, 1) == 0.0
    assert s.champagneTower(2, 1, 1) == 0.5
    assert s.champagneTower(1, 0, 0) == 1.0

    assert s.champagneTower(4, 2, 0) == 0.25
    assert s.champagneTower(4, 2, 1) == 0.5
    assert s.champagneTower(4, 2, 2) == 0.25

    assert s.champagneTower(100, 4, 2) == 1.0

    print("all tests passed")

run_tests()
```

Test coverage:

| Test | Why |
|---|---|
| `poured = 1` below top | No overflow |
| `poured = 2` | Equal split into second row |
| Query top glass | Top glass capped at `1` |
| `poured = 4`, row `2` | Checks uneven distribution |
| Large poured value | Confirms cap at `1` |