799. Champagne Tower

Time: O(query_glass²)

Space: O(query_glass²)

Intuition

Simulate champagne flow: excess liquid from cup (r,c) splits equally to (r+1,c) and (r+1,c+1). Track amount in each cup; amount in any cup is capped at 1 when queried.

Algorithm

1dp[r][c] = amount poured into cup.
2For each row r, for each cup c: overflow = max(0, dp[r][c]-1). dp[r+1][c] += overflow/2; dp[r+1][c+1] += overflow/2.
3Return min(1, dp[query_row][query_glass]).

Common Pitfalls

•Cups overflow when > 1, not >= 1. Return min(1, amount) for partial fill.

799.cs

// Approach: DP cascade row by row; any glass exceeding 1 splits the overflow equally to the two glasses below.
// Time: O(query_glass²) Space: O(query_glass²)

public class Solution
{
    public double ChampagneTower(int poured, int query_row, int query_glass)
    {
        double[,] dp = new double[query_row + 1, query_row + 1];
        dp[0, 0] = poured;

        for (int i = 0; i < query_row; ++i)
        {
            for (int j = 0; j <= i; ++j)
            {
                if (dp[i, j] > 1)
                {
                    double overflow = (dp[i, j] - 1) / 2.0;
                    dp[i + 1, j] += overflow;
                    dp[i + 1, j + 1] += overflow;
                }
            }
        }

        return Math.Min(1.0, dp[query_row, query_glass]);
    }
}

Was this solution helpful?