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

Function shape:

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

Examples

Example 1:

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:

0.0

Example 2:

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:

0.5

So the answer is:

0.5

Example 3:

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:

tower[row][glass]

be the amount of champagne that reaches that glass.

Start with:

tower[0][0] = poured

Then process rows from top to bottom.

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

overflow = tower[row][glass] - 1

Each child receives:

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.

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

Implementation

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:

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:

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

For each glass, if it overflows:

if tower[row][glass] > 1.0:

we compute the extra amount:

overflow = tower[row][glass] - 1.0

cap the current glass:

tower[row][glass] = 1.0

and split the overflow:

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

Finally, return the queried glass:

return tower[query_row][query_glass]

Space-Optimized Version

Only the current row and next row are needed.

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

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: