799. Champagne Tower - Explanation

1. Recursion

Intuition

Each glass receives champagne from the two glasses directly above it (its "parents"). When a glass overflows, half of the excess spills to each child below. We can recursively compute how much champagne flows into any glass by summing the overflow from its two parent glasses. The base case is the top glass, which receives all the poured champagne.

Algorithm

Define a recursive function that returns the total champagne flowing into glass (row, glass).
Base case: if we are out of bounds, return 0. If at position (0, 0), return the total poured amount.
For any other glass, compute the overflow from the left parent (row-1, glass-1) and right parent (row-1, glass).
Each parent contributes half of its excess (amount - 1) if positive.
The final answer is the minimum of 1 and the computed flow for the queried glass.

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        def rec(row, glass):
            if row < 0 or glass < 0 or glass > row:
                return 0

            if row == 0 and glass == 0:
                return poured

            left_parent = max(0, rec(row - 1, glass - 1) - 1)
            right_parent = max(0, rec(row - 1, glass) - 1)

            return (left_parent + right_parent) / 2

        return min(1, rec(query_row, query_glass))

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n)$

Where $n$ is the given $queryRow$ .

2. Dynamic Programming (Top-Down)

Intuition

The recursive solution recalculates the same glasses many times. By storing computed values in a memoization table, we avoid redundant work. Each glass only needs to be computed once since its inflow depends only on the glasses above it.

Algorithm

Create a memo table to store the champagne flow for each (row, glass) position.
Initialize memo[0][0] with the poured amount.
Use the same recursive logic as before, but check the memo before computing.
Store computed results in the memo table before returning.
Return min(1, memo[query_row][query_glass]).

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        memo = { (0, 0) : poured }

        def rec(row, glass):
            if row < 0 or glass < 0 or glass > row:
                return 0
            if (row, glass) in memo:
                return memo[(row, glass)]

            left_parent = max(0, rec(row - 1, glass - 1) - 1)
            right_parent = max(0, rec(row - 1, glass) - 1)

            memo[(row, glass)] = (left_parent + right_parent) / 2
            return memo[(row, glass)]

        return min(1, rec(query_row, query_glass))

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n * m)$

Where $n$ is the given $queryRow$ and $m$ is the given $queryGlass$ .

3. Dynamic Programming (Bottom-Up)

Intuition

Instead of working backwards from the query position, we can simulate the pouring process from top to bottom. We track how much champagne flows into each glass. When a glass overflows (has more than 1 unit), we distribute the excess equally to the two glasses below it.

Algorithm

Create a 2D array where dp[row][glass] represents the total flow into that glass.
Set dp[0][0] = poured.
For each row from 0 to query_row - 1:
- For each glass in that row, if the flow exceeds 1, compute the excess.
- Add half the excess to each of the two glasses below.
Return min(1, dp[query_row][query_glass]).

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        dp = [[0] * (i + 1) for i in range(query_row + 5)]
        dp[0][0] += poured

        for row in range(min(99, query_row + 1)):
            for glass in range(row + 1):
                excess = (dp[row][glass] - 1.0) / 2.0
                if excess > 0:
                    dp[row + 1][glass] += excess
                    dp[row + 1][glass + 1] += excess

        return min(1.0, dp[query_row][query_glass])

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n * m)$

Where $n$ is the given $queryRow$ and $m$ is the given $queryGlass$ .

4. Dynamic Programming (Space Optimized)

Intuition

Since each row only depends on the row directly above it, we do not need to store the entire 2D table. We can use two 1D arrays: one for the previous row and one for the current row being computed. After processing each row, the current row becomes the previous row for the next iteration.

Algorithm

Initialize prev_row with the poured amount at index 0.
For each row from 1 to query_row:
- Create a new cur_row array of appropriate size.
- For each glass in the previous row, if it overflows, distribute half the excess to cur_row[i] and cur_row[i+1].
- Set prev_row = cur_row for the next iteration.
Return min(1, prev_row[query_glass]).

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        prev_row = [poured]  # Flow

        for row in range(1, query_row + 1):
            cur_row = [0] * (row + 1)
            for i in range(row):
                extra = prev_row[i] - 1
                if extra > 0:
                    cur_row[i] += 0.5 * extra
                    cur_row[i + 1] += 0.5 * extra
            prev_row = cur_row

        return min(1, prev_row[query_glass])

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n)$

Where $n$ is the given $queryRow$ and $m$ is the given $queryGlass$ .

5. Dynamic Programming (Optimal)

Intuition

We can further optimize by using a single 1D array, processing from right to left within each row. This ensures we do not overwrite values we still need. Each position updates itself with half its excess, while contributing the other half to the next position.

Algorithm

Create a single array dp of size (query_row + 1), initialized with poured at index 0.
For each row from 1 to query_row:
- Iterate from right to left (from index row-1 down to 0).
- If dp[i] > 1, set dp[i] = 0.5 * (dp[i] - 1) and add the same to dp[i+1].
- If dp[i] <= 1, set dp[i] = 0 (it does not overflow).
Return min(1, dp[query_glass]).

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        dp = [poured] + [0] * query_row

        for row in range(1, query_row + 1):
            for i in range(row - 1, -1, -1):
                extra = dp[i] - 1
                if extra > 0:
                    dp[i] = 0.5 * extra
                    dp[i + 1] += 0.5 * extra
                else:
                    dp[i] = 0

        return min(1, dp[query_glass])

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n)$

Where $n$ is the given $queryRow$ and $m$ is the given $queryGlass$ .

Common Pitfalls

Forgetting to Clamp the Final Result to 1

A glass can receive more champagne than it can hold, but the answer should only report how full it is (max 1.0). Returning the raw flow value without capping it at 1 gives incorrect results for glasses that overflow.

# Wrong: returns overflow amount
return dp[query_row][query_glass]
# Correct: cap at 1.0 (glass can't be more than full)
return min(1, dp[query_row][query_glass])

Distributing Total Flow Instead of Excess

Each glass holds 1 unit before overflowing. A common mistake is distributing the total champagne received to children instead of only the excess (amount - 1). This incorrectly empties glasses that should remain full.

# Wrong: distributes everything
dp[row + 1][glass] += dp[row][glass] / 2
# Correct: only distribute the excess
excess = dp[row][glass] - 1
if excess > 0:
    dp[row + 1][glass] += excess / 2

Incorrect Parent Glass Indices

When computing flow from parent glasses, using wrong indices for left and right parents causes incorrect champagne distribution. The left parent is at (row-1, glass-1) and right parent is at (row-1, glass).

# Wrong: both parents at same index
left_parent = rec(row - 1, glass)
right_parent = rec(row - 1, glass)
# Correct: different parent positions
left_parent = rec(row - 1, glass - 1)
right_parent = rec(row - 1, glass)