Champagne Tower

How it works

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.

Steps

1. Create a single array dp of size (query_row + 1), initialized with poured at index 0.
2. 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).
3. Return min(1, dp[query_glass]).

Complexity

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

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

Things to watch for

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.

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.

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).

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])

class Solution {
public:
    double champagneTower(int poured, int query_row, int query_glass) {
        vector<double> dp(query_row + 1, 0);
        dp[0] = poured;

        for (int row = 1; row <= query_row; row++) {
            for (int i = row - 1; i >= 0; i--) {
                double 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.0, dp[query_glass]);
    }
};