LeetCode 799 - Champagne Tower

The problem asks us to simulate a process of pouring champagne into a pyramid of glasses. Each glass can hold exactly one cup of champagne, and any excess from a glass flows evenly to the two glasses immediately below it.

leetcodemediumdynamic-programming

LeetCode Problem 799

Difficulty: 🟡 Medium
Topics: Dynamic Programming

Solution

Problem Understanding

The problem asks us to simulate a process of pouring champagne into a pyramid of glasses. Each glass can hold exactly one cup of champagne, and any excess from a glass flows evenly to the two glasses immediately below it. We are given a non-negative integer poured representing the total cups poured into the top glass, and we need to determine how full a specific glass is at row query_row and column query_glass. The rows and glasses are 0-indexed, so (0, 0) is the topmost glass.

The input poured can be as large as 10^9, and the maximum row we need to query is 99, which suggests that a solution that simulates all cups individually would be inefficient. The output is a float representing the fraction of a cup filled in the target glass, capped at 1.0 because glasses cannot hold more than one cup. Edge cases include pouring zero cups, querying the top glass, querying glasses that may receive only partial overflow, and very large pours where all glasses up to the query row may be full.

Approaches

The brute-force approach would simulate pouring each cup one by one, propagating overflow down each row. While it would give the correct result, it is inefficient for large values of poured because each cup could affect up to query_row rows, making it impractical for poured = 10^9.

The optimal approach uses dynamic programming. We can maintain a 2D array (or triangular array) where dp[i][j] stores the amount of champagne in the glass at row i and column j. We initialize the top glass with the poured amount. Then, for each glass that exceeds 1 cup, we calculate the excess and distribute it evenly to the two glasses below. This allows us to calculate the exact amount in any glass without simulating each cup individually. We only need to propagate excess, making this method efficient and easy to implement.

Approach Time Complexity Space Complexity Notes
Brute Force O(poured * query_row^2) O(query_row^2) Simulates each cup; too slow for large poured values
Optimal O(query_row^2) O(query_row^2) Dynamic programming; only propagates excess

Algorithm Walkthrough

  1. Create a 2D array dp of size 100x100 initialized with zeros. Each cell dp[i][j] represents the amount of champagne in the jth glass of the ith row.
  2. Set dp[0][0] to the total poured amount.
  3. Iterate over each row i from 0 to query_row. For each glass j in row i, check if dp[i][j] exceeds 1. If it does, calculate the excess as dp[i][j] - 1.
  4. Distribute half of the excess to the glass directly below-left dp[i+1][j] and half to the glass below-right dp[i+1][j+1]. The current glass retains only 1 cup.
  5. After filling all rows up to query_row, the amount in dp[query_row][query_glass] represents how full the queried glass is. Cap the value at 1.0 using min(1.0, dp[query_row][query_glass]).
  6. Return the result.

Why it works: The DP table ensures that each glass only contains the actual amount of champagne that reaches it. By propagating only the overflow, the algorithm respects the physical behavior of champagne flowing down and never overcounts or undercounts the distribution.

Python Solution

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        dp = [[0.0] * 100 for _ in range(100)]
        dp[0][0] = float(poured)
        
        for i in range(query_row + 1):
            for j in range(i + 1):
                if dp[i][j] > 1.0:
                    excess = dp[i][j] - 1.0
                    dp[i][j] = 1.0
                    dp[i+1][j] += excess / 2.0
                    dp[i+1][j+1] += excess / 2.0
        
        return min(1.0, dp[query_row][query_glass])

The implementation initializes a 100x100 DP table because the maximum row is 99. The double loop propagates excess champagne from each glass to the next row. By capping each glass at 1.0, the algorithm prevents overfilling. Finally, we return the minimum of 1.0 and the amount in the queried glass.

Go Solution

func champagneTower(poured int, query_row int, query_glass int) float64 {
    dp := make([][]float64, 100)
    for i := range dp {
        dp[i] = make([]float64, 100)
    }
    dp[0][0] = float64(poured)
    
    for i := 0; i <= query_row; i++ {
        for j := 0; j <= i; j++ {
            if dp[i][j] > 1.0 {
                excess := dp[i][j] - 1.0
                dp[i][j] = 1.0
                dp[i+1][j] += excess / 2.0
                dp[i+1][j+1] += excess / 2.0
            }
        }
    }
    
    if dp[query_row][query_glass] > 1.0 {
        return 1.0
    }
    return dp[query_row][query_glass]
}

In Go, we explicitly create a 2D slice with size 100x100. The logic mirrors the Python implementation. Since Go does not automatically cap float values, we check the final glass and return 1.0 if necessary.

Worked Examples

Example 1: poured = 1, query_row = 1, query_glass = 1

Step 1: dp[0][0] = 1

Step 2: No excess in dp[0][0], so no propagation

Step 3: dp[1][1] = 0

Output: 0.0

Example 2: poured = 2, query_row = 1, query_glass = 1

Step 1: dp[0][0] = 2

Step 2: dp[0][0] exceeds 1, excess = 1

Step 3: Propagate: dp[1][0] += 0.5, dp[1][1] += 0.5

Step 4: dp[1][1] = 0.5

Output: 0.5

Example 3: poured = 100000009, query_row = 33, query_glass = 17

Step 1: All glasses up to row 33 will be full due to large pour

Step 2: dp[33][17] = 1

Output: 1.0

Complexity Analysis

Measure Complexity Explanation
Time O(query_row^2) Each glass in rows up to query_row is visited once
Space O(query_row^2) DP table stores champagne amounts for each glass

The algorithm avoids iterating over every poured cup, relying instead on distributing only the overflow. Since the maximum row is 99, the table has at most 100x100 entries, making the solution feasible even for the largest pours.

Test Cases

# Provided examples
assert Solution().champagneTower(1, 1, 1) == 0.0  # minimal pour
assert Solution().champagneTower(2, 1, 1) == 0.5  # overflow split
assert Solution().champagneTower(100000009, 33, 17) == 1.0  # very large pour

# Edge cases
assert Solution().champagneTower(0, 0, 0) == 0.0  # no champagne
assert Solution().champagneTower(1, 0, 0) == 1.0  # only top glass
assert Solution().champagneTower(3, 1, 0) == 1.0  # first row partially full
assert Solution().champagneTower(3, 1, 1) == 1.0  # first row partially full
assert Solution().champagneTower(4, 2, 1) == 0.5  # middle glass partially filled
Test Why
(1, 1, 1) Minimal pour, tests no overflow
(2, 1, 1) Simple overflow to second row
(100000009, 33, 17) Very large pour, ensures capping at 1.0
(0, 0, 0) No champagne, tests empty case
(1, 0, 0) Only top glass, tests 1 cup exactly
(3, 1, 0) & `(