The Champagne Tower Problem

You're at a wedding. Glasses are stacked in a pyramid, and the server pours champagne from the top. When a glass fills up and overflows, the champagne spills to the glasses below.

Here's the question: if you know how much champagne was poured, can you figure out how full a specific glass is?

Let's start simple. Forget about the pyramid for now. What happens with just one glass?

A single glass

The glass can hold exactly 1 unit of champagne. Pour less than 1, and the glass is partially full. Pour exactly 1, and it's full. Try it:

So far, so good. But what if you pour more than 1 unit?

Running into overflow

Pour 1.5 units. The glass holds 1 unit and fills completely. The extra 0.5 units has nowhere to go—it overflows.

In a single glass sitting alone, that overflow just spills onto the table. But in a pyramid, there are glasses below to catch it.

Where does the overflow go?

Overflow splits between two glasses

Picture the pyramid structure. Each glass sits above two glasses in the row below, one to the left and one to the right:

    (0,0)
   /    \
(1,0)  (1,1)

When glass (0,0) overflows, the champagne doesn't all go to one side. It splits equally: half flows to the left glass below, half flows to the right.

The top glass keeps 1 unit. The overflow splits 50/50 to the two glasses below. Pour 2 units into the top, and each bottom glass receives 0.5.

This gives us the rule: when a glass has more than 1 unit, it keeps 1, and the rest divides equally between its two children.

What about many rows?

Now we can extend this to a full pyramid. Each row has one more glass than the row above:

         (0,0)
       /      \
    (1,0)    (1,1)
   /    \    /    \
(2,0) (2,1) (2,2)

The champagne cascades down level by level. Glasses in the middle receive overflow from two parents above, while edge glasses only have one parent.

Pour different amounts and click any glass to see how full it is. Notice how center glasses tend to fill up faster—they're catching overflow from multiple paths.

Following the flow

Let's walk through what happens step by step when you pour champagne into the top:

The champagne flows down row by row. Each glass processes its overflow in turn, passing the excess to the next level. This cascade continues until either the champagne runs out or it reaches the bottom row and spills to the floor.

This step-through reveals something: we don't need to calculate anything recursively. We can just simulate the pouring process.

The algorithm emerges

Here's what we discovered by watching the champagne flow:

Start with all glasses empty. Pour the champagne into the top glass. Then go row by row from top to bottom. For each glass, if it has more than 1 unit, cap it at 1 and split the overflow equally to the two glasses below.

That's the entire algorithm. It's just a simulation of what happens physically.

def champagne_tower(poured, query_row, query_glass):
    # Create a 2D array to track champagne in each glass
    tower = [[0] * (i + 1) for i in range(query_row + 1)]
 
    # Pour all champagne into the top glass
    tower[0][0] = poured
 
    # Process each row, splitting overflow as we go
    for row in range(query_row):
        for col in range(row + 1):
            if tower[row][col] > 1:
                overflow = tower[row][col] - 1
                tower[row][col] = 1
 
                # Split overflow to the two glasses below
                tower[row + 1][col] += overflow / 2
                tower[row + 1][col + 1] += overflow / 2
 
    # Return the amount in the queried glass, capped at 1.0
    return min(1, tower[query_row][query_glass])

We process each glass exactly once, in order. No recursion, no memoization, no backtracking. Just follow the champagne as it flows down.

Step through the code yourself

Modify the inputs and step through the execution line by line. Watch how the variables change and see the tower update in real time:

Why not recursion?

You might think a recursive approach would be more natural. After all, the amount in glass (r, c) depends on overflow from glasses (r-1, c-1) and (r-1, c).

The recursive version would compute how much champagne reaches a specific glass by calculating the overflow from its parents, which in turn depends on their parents, and so on back to the top:

def champagne_tower(poured, query_row, query_glass):
    memo = {}
 
    def flow(row, col, amount):
        if row < 0 or col < 0 or col > row:
            return 0
        if row == 0 and col == 0:
            return amount
 
        key = (row, col)
        if key in memo:
            return memo[key]
 
        # Calculate inflow from parent glasses
        left_parent = flow(row - 1, col - 1, amount)
        right_parent = flow(row - 1, col, amount)
 
        total = 0
        if left_parent > 1:
            total += (left_parent - 1) / 2
        if right_parent > 1:
            total += (right_parent - 1) / 2
 
        memo[key] = total
        return total
 
    return min(1, flow(query_row, query_glass, poured))

This works and has the same O(R²) complexity with memoization. But simulation is cleaner because it follows the natural flow of the problem. You're literally implementing what happens when champagne pours down a pyramid. The recursive version requires you to think backwards from the target glass up to the source.

When the physics of the problem suggests an obvious order of operations, following that order is usually the simplest solution.

How fast is this?

The time complexity is O(R²) where R is query_row. We process every glass in rows 0 through query_row. Row r has r + 1 glasses, so the total is 1 + 2 + 3 + ... + (R + 1) = (R + 1)(R + 2) / 2, which simplifies to O(R²).

The space complexity is also O(R²) since we store the champagne amount for each glass up to the query row.

Could we do better? Not really. Even if we only care about one specific glass, we can't know how much champagne reaches it without computing all the glasses in the rows above it. The champagne has to flow through every glass on its way down.

Edge cases

A few things to watch for when implementing this:

If poured = 0, every glass stays empty. The algorithm handles this correctly since no overflow occurs.

If poured = 1, only the top glass fills to exactly 1.0. Nothing reaches the lower levels.

Glasses in the bottom row can overflow too, but that champagne falls to the floor. Make sure to cap their values at 1.0 when returning your answer.

In a complete implementation, you'd also validate that query_glass <= query_row since glasses are 0-indexed within each row and you can't query glass 5 in row 2.

The lesson

Sometimes the straightforward simulation is the best approach. The champagne tower problem looks like it might need dynamic programming or clever recursion, but it unravels elegantly when you just model what happens physically.

Pour the champagne, let it overflow, split it between the glasses below. Process everything in order. That's it.

The algorithm isn't something you discover by being clever—it's something you discover by watching what happens and writing down the steps.