Problem Description

The "Champagne Tower" problem describes a scenario where you pour a certain number of cups of champagne into the top glass of a pyramid-shaped tower of glasses. Each glass can hold exactly one cup of champagne. When a glass overflows, the excess champagne spills equally to the two glasses immediately below it (to the left and right). This process continues down the tower.

Given three inputs:

• poured: the number of cups poured into the top glass (at row 0, glass 0)
• query_row: the row of the glass you are interested in (0-indexed)
• query_glass: the position of the glass in the row (0-indexed)

Key constraints:

• Each glass holds at most one cup.
• Overflow splits equally to the two glasses below.
• You must return the amount in the target glass, capped at 1.

Thought Process

At first glance, it seems you might need to simulate the pouring process for every glass in the tower, tracking how much champagne each receives and overflows. This brute-force approach would involve iterating through every row and glass, simulating the champagne flow step by step.

However, we can observe that only the glasses above and to the left or right of the target glass can affect its fill level. Also, since overflow is split equally, we can use an array to track the amount in each glass row by row, updating only the relevant glasses.

The challenge is to efficiently model how overflow propagates, avoid unnecessary computation, and ensure we do not exceed the glass's capacity.

Solution Approach

To solve the problem efficiently, we use a dynamic programming approach, where we simulate the flow of champagne row by row.

1. Initialize a 2D array: Create a 2D array (or list of lists) where dp[i][j] represents the amount of champagne in the glass at row i and glass j.
2. Pour champagne: Set dp[0][0] to poured, representing all champagne poured into the top glass.
3. Simulate overflow: For each glass in each row, if it contains more than 1 cup, compute the overflow ((dp[i][j] - 1) / 2). Add this overflow to the two glasses directly below (dp[i+1][j] and dp[i+1][j+1]).
4. Iterate only as far as needed: Only simulate up to query_row, since glasses below do not affect the result.
5. Return capped value: The target glass may have more than 1 cup, but we return min(1, dp[query_row][query_glass]) as the answer.

This approach is efficient because it only tracks the glasses that could possibly be affected, and ignores all others.

Example Walkthrough

Suppose poured = 4, query_row = 2, query_glass = 1.

Step 1 (Initial State):

• Row 0: [4]

Step 2 (Row 1):

• Glass (0,0) overflows: (4 - 1) / 2 = 1.5 to each below
• Row 1: [1.5, 1.5]

Step 3 (Row 2):

• Glass (1,0) overflows: (1.5 - 1) / 2 = 0.25 to (2,0)
• Glass (1,1) overflows: (1.5 - 1) / 2 = 0.25 to (2,1)
• Row 2: [0.25 from (1,0), 0.25 from (1,0) + 0.25 from (1,1) = 0.5, 0.25 from (1,1)]
• Row 2: [0.25, 0.5, 0.25]

Result: The glass at row 2, glass 1 has 0.5 cups of champagne.

Time and Space Complexity

Brute-force approach:

• Time: O(2ⁿ), since each glass could potentially overflow to two below, leading to exponential growth.
• Space: O(2ⁿ), as you might try to track all possible paths.

• Time: O(n²), where n is query_row, since we only fill glasses up to that row.
• Space: O(n²), as we store each glass up to query_row.

In practice, you can optimize space to O(n) by only keeping two rows at a time, but the standard 2D DP solution is clear and simple.

Summary

The Champagne Tower problem is elegantly solved using dynamic programming by simulating the flow of champagne row by row. By modeling only the relevant glasses and tracking overflow efficiently, we avoid unnecessary computations. The key insight is that each glass's overflow only affects the two glasses directly below, and we only need to simulate up to the row of interest. This results in a clear, efficient, and scalable solution.

Code Implementation

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        dp = [[0] * (k + 1) for k in range(query_row + 2)]
        dp[0][0] = poured
        for row in range(query_row + 1):
            for col in range(row + 1):
                overflow = max(0.0, (dp[row][col] - 1) / 2)
                if overflow > 0:
                    dp[row + 1][col] += overflow
                    dp[row + 1][col + 1] += overflow
        return min(1, dp[query_row][query_glass])
      

class Solution {
public:
    double champagneTower(int poured, int query_row, int query_glass) {
        vector<vector<double>> dp(query_row + 2, vector<double>(query_row + 2, 0.0));
        dp[0][0] = poured;
        for (int row = 0; row <= query_row; ++row) {
            for (int col = 0; col <= row; ++col) {
                double overflow = max(0.0, (dp[row][col] - 1) / 2.0);
                if (overflow > 0) {
                    dp[row + 1][col] += overflow;
                    dp[row + 1][col + 1] += overflow;
                }
            }
        }
        return min(1.0, dp[query_row][query_glass]);
    }
};
      

class Solution {
    public double champagneTower(int poured, int query_row, int query_glass) {
        double[][] dp = new double[query_row + 2][query_row + 2];
        dp[0][0] = poured;
        for (int row = 0; row <= query_row; row++) {
            for (int col = 0; col <= row; col++) {
                double overflow = Math.max(0, (dp[row][col] - 1) / 2.0);
                if (overflow > 0) {
                    dp[row + 1][col] += overflow;
                    dp[row + 1][col + 1] += overflow;
                }
            }
        }
        return Math.min(1, dp[query_row][query_glass]);
    }
}
      

var champagneTower = function(poured, query_row, query_glass) {
    let dp = Array.from({length: query_row + 2}, (_, i) => Array(i + 1).fill(0));
    dp[0][0] = poured;
    for (let row = 0; row <= query_row; row++) {
        for (let col = 0; col <= row; col++) {
            let overflow = Math.max(0, (dp[row][col] - 1) / 2);
            if (overflow > 0) {
                dp[row + 1][col] += overflow;
                dp[row + 1][col + 1] += overflow;
            }
        }
    }
    return Math.min(1, dp[query_row][query_glass]);
};