#799

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Champagne Tower

Compute champagne levels in a pyramid of glasses using state transition dynamic programming for accurate distribution tracking.

dynamic programming

Problem Statement

You have a pyramid of glasses with the first row containing 1 glass, the second row 2 glasses, up to 100 rows. Each glass can hold one cup of champagne. When champagne is poured into the top glass, any overflow spills equally to the two glasses immediately below it. This continues down the pyramid, with excess from glasses in the bottom row falling to the floor.

Given the amount of champagne poured and a specific glass at (query_row, query_glass), return the amount of champagne in that glass. For example, pouring one cup fills the top glass only, pouring two cups splits the excess between the second row, and larger amounts cascade through multiple rows. Implement the solution efficiently, keeping track of overflow distributions.

Examples

Example 1

Input: poured = 1, query_row = 1, query_glass = 1

Output: 0.00000

We poured 1 cup of champange to the top glass of the tower (which is indexed as (0, 0)). There will be no excess liquid so all the glasses under the top glass will remain empty.

Example 2

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

Output: 0.50000

We poured 2 cups of champange to the top glass of the tower (which is indexed as (0, 0)). There is one cup of excess liquid. The glass indexed as (1, 0) and the glass indexed as (1, 1) will share the excess liquid equally, and each will get half cup of champange.

Example 3

Input: poured = 100000009, query_row = 33, query_glass = 17

Output: 1.00000

Example details omitted.

Constraints

0 <= poured <= 109
0 <= query_glass <= query_row < 100

Solution Approach

Use a 2D DP table to track overflow

Create a DP array where dp[r][c] represents the champagne in row r, column c. Initialize the top glass with poured amount and iterate row by row, computing the overflow to the left and right glasses below, capped at 1 cup per glass.

Iterate row by row for state transitions

For each glass, calculate the excess champagne above 1 cup. Distribute half of the excess to the glass directly below-left and half to the glass below-right. Continue this until reaching the query row, ensuring each DP cell reflects the correct amount from prior state transitions.

Retrieve and cap the queried glass

After processing all rows, the value in dp[query_row][query_glass] may exceed 1 due to overflow calculations. Return the minimum of this value and 1.0, giving the actual champagne amount in the queried glass.

Complexity Analysis

Metric	Value
Time	O(R^2)
Space	O(R^2)

Time complexity is O(R^2) since every glass up to the query row is processed once. Space complexity is O(R^2) to store DP states for all glasses up to the query row.

What Interviewers Usually Probe

Emphasize using dynamic programming to track cascading state transitions in the pyramid.
Look for correct handling of overflow splitting exactly half to each child glass.
Notice if the candidate caps values at 1 per glass instead of summing total overflow incorrectly.

Common Pitfalls or Variants

Common pitfalls

Failing to distribute overflow correctly, leading to inaccurate amounts in lower glasses.
Not capping the queried glass at 1, returning more than the glass can hold.
Attempting a recursive solution without memoization, causing excessive computation.

Follow-up variants

Compute total full glasses after pouring a given amount, leveraging the same DP overflow approach.
Determine the first glass to overflow beyond 1 cup in a large poured scenario using DP simulation.
Optimize space by using a single-row rolling DP array for large query_row values.

FAQ

What is the main algorithm pattern used in Champagne Tower?

This problem is solved using state transition dynamic programming, tracking overflow from each glass to the next row.

How do I handle a glass that receives more than 1 cup?

Always cap the amount at 1 for the queried glass and propagate any excess to the two glasses below it equally.

Can I optimize space usage for large query rows?

Yes, using a rolling 1D DP array per row reduces space from O(R^2) to O(R) while maintaining correct overflow calculations.

Why does pouring a small amount sometimes leave lower glasses empty?

Because champagne only flows when the glass above exceeds 1 cup, so insufficient poured amounts don’t reach deeper rows.

Is recursion a good approach for Champagne Tower?

Pure recursion without memoization is inefficient; using iterative DP with state transitions is the preferred method.

terminal

Solution

Solution 1: Simulation

We directly simulate the process of pouring champagne.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        f = [[0] * 101 for _ in range(101)]
        f[0][0] = poured
        for i in range(query_row + 1):
            for j in range(i + 1):
                if f[i][j] > 1:
                    half = (f[i][j] - 1) / 2
                    f[i][j] = 1
                    f[i + 1][j] += half
                    f[i + 1][j + 1] += half
        return f[query_row][query_glass]

Solution 2: Simulation (Space Optimization)

Since the amount of champagne in each layer only depends on the amount in the previous layer, we can use a rolling array approach to optimize space complexity, converting the 2D array to a 1D array.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        f = [[0] * 101 for _ in range(101)]
        f[0][0] = poured
        for i in range(query_row + 1):
            for j in range(i + 1):
                if f[i][j] > 1:
                    half = (f[i][j] - 1) / 2
                    f[i][j] = 1
                    f[i + 1][j] += half
                    f[i + 1][j + 1] += half
        return f[query_row][query_glass]

Continue Practicing

#801 minimum swaps to make sequences increasing #805 split array with same average #792 number of matching subsequences