Champagne Tower: Simulation with Dynamic Programming

You have a pyramid of champagne glasses. The top row has 1 glass, the second row has 2, the third has 3, and so on. You pour poured cups of champagne into the very top glass. When a glass is full (holds 1 cup), any extra champagne overflows equally to the two glasses directly below it, one to the left and one to the right. Given poured, query_row, and query_glass, return how full the glass at that position is (capped at 1.0).

This is LeetCode 799: Champagne Tower, and it is a great example of simulation-style dynamic programming on a triangular grid. The trick is not complicated, but the way the problem maps onto a 2D DP table is something you will see again in other grid and triangle problems.

Why this problem matters

Champagne Tower teaches you two things at once:

• Simulation as DP. Instead of finding an optimal value, you are simulating a physical process. But the technique is the same: process elements in order and propagate values forward.
• DP on triangular grids. The glass pyramid is structurally identical to problems like Pascal's Triangle and Triangle. Each cell receives contributions from one or two cells in the row above. Once you see this shared structure, you can reuse the same row-by-row iteration approach across all of them.

The problem also tests your ability to handle floating-point values and boundary conditions cleanly. It is a medium-difficulty problem that rewards careful thinking over clever tricks.

The approach: simulate row by row

The key insight is to track how much liquid each glass receives, not just how much it holds. A glass might receive far more than 1 cup if a lot of champagne is poured. Once you know the total amount that flows into a glass, you can figure out two things:

1. How full is it? That is min(1.0, amount).
2. How much overflows? That is max(0, amount - 1.0).

The overflow from one glass splits equally between the two glasses directly below it. So the algorithm is:

1. Create a 2D array dp where dp[row][col] is the total liquid poured into that glass.
2. Set dp[0][0] = poured.
3. For each glass from top to bottom, if it has more than 1 cup, compute the excess and add half to each of the two children below.
4. Return min(1.0, dp[query_row][query_glass]).

You only need to process rows up to query_row. Anything below that does not affect the answer.

The solution

def champagne_tower(poured, query_row, query_glass):
    dp = [[0.0] * (i + 1) for i in range(query_row + 1)]
    dp[0][0] = poured

    for row in range(query_row):
        for col in range(row + 1):
            excess = dp[row][col] - 1.0
            if excess > 0:
                dp[row][col] = 1.0
                dp[row + 1][col] += excess / 2.0
                dp[row + 1][col + 1] += excess / 2.0

    return min(1.0, dp[query_row][query_glass])

The inner loop looks at each glass in the current row. If it overflowed, it caps the glass at 1.0 and pushes half of the excess to each child. By the time you reach query_row, every glass in that row has its correct total amount. You return the minimum of that amount and 1.0 because a glass cannot be more than full.

Walking through an example

Let's trace through the algorithm with poured = 4, querying glass at row 2, column 1.

The simulation proceeds top-down, row by row. Each glass receives contributions from at most two parents above it. The middle glass in row 2 gets overflow from both glass(1,0) and glass(1,1), which is why it ends up with 0.5 instead of 0.25.

Complexity analysis

The number of glasses through query_row rows is 1 + 2 + ... + (query_row + 1), which is O(query_row^2). You visit each glass once, so the time is O(query_row^2).

For space, the full 2D table uses O(query_row^2). But since each row only depends on the row directly above it, you can optimize to O(query_row) by keeping only two rows at a time. The solution above uses the full table for clarity, but the optimization follows the same pattern you see in Triangle and Minimum Path Sum.

The building blocks

This problem is built on simulation DP on a triangular grid. The core idea is to propagate values downward through a triangle, where each cell contributes to its children below. This is a push-based DP pattern: instead of pulling values from dependencies, each cell pushes its excess forward.

The same structural pattern appears in several other problems:

• Pascal's Triangle (LeetCode 118): each cell is the sum of the two cells above it. Same triangle, different transition.
• Triangle (LeetCode 120): find the minimum path sum from top to bottom. Same row-by-row processing, but you minimize instead of summing.
• Minimum Path Sum (LeetCode 64): rectangular grid instead of triangular, but the same idea of propagating values through a 2D structure.

The difference in Champagne Tower is that you push excess forward (overflow simulation) rather than pulling optimal values backward. But the grid traversal and the dependency structure are the same building block.

Edge cases to watch for

• poured = 0: every glass is empty. Return 0.0 for any query.
• Query the top glass: if query_row = 0 and query_glass = 0, the answer is min(1.0, poured). The simulation loop does not execute, and you return the value directly.
• Very large poured value: say poured = 1000000000. The algorithm still works correctly because you are just doing arithmetic on floats. The 2D table stays the same size (determined by query_row, not by poured).
• Query a glass that receives no overflow: if poured = 1, only glass(0,0) is full and nothing overflows. Any glass below row 0 holds 0.

From understanding to recall

You have walked through the simulation step by step and the logic is clear. But in an interview, nobody hands you the diagram. You need to reconstruct the overflow rule, set up the 2D table, and handle the min(1.0, ...) cap on your own.

Spaced repetition bridges that gap. You revisit the champagne tower simulation at increasing intervals, each time setting up the DP table from scratch, writing the overflow logic, and verifying your edge cases. After a few reps, the push-based simulation pattern is automatic.

This triangular grid DP pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is a far more effective strategy than grinding problems randomly and hoping the patterns stick.

Related posts

• Pascal's Triangle - The foundational triangular grid problem where each cell sums two parents above
• Triangle - Find the minimum path sum from top to bottom of a triangle, same grid structure with optimization
• Minimum Path Sum - DP on a rectangular grid, showing how the same propagation idea extends to different shapes