🥂 Beginner-Friendly Guide ‘Champagne Tower’ – Problem 799 (C++, Python, JavaScript)

Imagine a wedding reception where a tower of champagne glasses is stacked in a pyramid. If you pour too much into the top glass, it beautifully overflows into the ones below, creating a cascading effect. This problem asks us to mathematically simulate that flow to determine exactly how much liquid ends up in a specific glass.

Problem Summary

You’re given:

• An integer poured, representing the total number of cups of champagne poured into the top glass.
• Two integers, query_row and query_glass, which act as the coordinates for the specific glass we are checking.

Your goal:

• Return a decimal value representing how full that specific glass is. A glass can hold a maximum of 1 cup, so any value returned will be between 0 and 1.

Intuition

The core logic revolves around overflow. A glass only starts sharing liquid with its neighbors once it has exceeded its capacity of 1 cup.

When a glass at row i and position j overflows, the excess amount is split exactly in half. One half falls into the glass directly below it to the left at , and the other half falls into the glass below it to the right at .

Instead of simulating every single drop, we can use a Dynamic Programming approach. We track the total amount of liquid that passes through each glass. By iterating row by row, we can calculate how much “excess” from the current row will contribute to the next row. Even if a glass receives 10 cups, we only care about the 9 cups of overflow it passes down.

Walkthrough: Understanding the Examples

Example 2: poured = 2, query_row = 1, `query_glass = 1`

1. Row 0: We pour 2 cups into the top glass (0, 0).
2. Overflow Calculation: The top glass holds 1 cup and has 1 cup of excess ().
3. Distribution: The 1 cup of excess is split. 0.5 cups go to glass (1, 0) and 0.5 cups go to glass (1, 1).
4. Result: Glass (1, 1) contains 0.5 cups.

Example 1: poured = 1, query_row = 1, `query_glass = 1`

1. Row 0: We pour 1 cup into the top glass.
2. Overflow Calculation: The glass is full, but there is 0 excess ().
3. Result: No liquid falls to the second row. Glass (1, 1) is empty (0.0).

Code Blocks

C++

class Solution {
public:
    double champagneTower(int poured, int query_row, int query_glass) {
        // We use a DP array to store the amount of champagne in each glass of the current row
        vector<double> dp(query_row + 2, 0.0);
        dp[0] = (double)poured;

        for (int i = 0; i < query_row; i++) {
            // Iterate backwards to update the row in-place or use a temporary row
            for (int j = i; j >= 0; j--) {
                // Calculate overflow: (current amount - 1) divided by 2
                double overflow = max(0.0, (dp[j] - 1.0) / 2.0);
                // The current glass only keeps 1.0 if it was full, but for 
                // processing, we send the overflow to the next row's children
                dp[j + 1] += overflow;
                dp[j] = overflow;
            }
        }
        // The value in the glass cannot exceed 1.0
        return min(1.0, dp[query_glass]);
    }
};

Python

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        # Initialize DP array with the initial pour at the first glass
        dp = [0.0] * (query_row + 2)
        dp[0] = float(poured)

        for i in range(query_row):
            # We process from the end of the row to the start to update in-place
            for j in range(i, -1, -1):
                # Calculate the amount that overflows from the current glass
                overflow = max(0.0, (dp[j] - 1.0) / 2.0)
                # Split the overflow between the two glasses below
                dp[j + 1] += overflow
                dp[j] = overflow

        return min(1.0, dp[query_glass])

JavaScript

/**
 * @param {number} poured
 * @param {number} query_row
 * @param {number} query_glass
 * @return {number}
 */
var champagneTower = function(poured, query_row, query_glass) {
    // Create a DP array to track liquid flow through the rows
    let dp = new Array(query_row + 2).fill(0.0);
    dp[0] = poured;

    for (let i = 0; i < query_row; i++) {
        for (let j = i; j >= 0; j--) {
            // Determine how much spills over to the next level
            let overflow = Math.max(0, (dp[j] - 1) / 2);
            // Current glass contributes half its overflow to j and half to j+1
            dp[j + 1] += overflow;
            dp[j] = overflow;
        }
    }

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

Key Takeaways

• Simulation via DP: Problems involving flow or cascades are often best solved by simulating the state of one “level” and using it to calculate the next.
• Space Optimization: Instead of a 2D grid of , we used a 1D array to save memory, updating it iteratively for each row.
• Boundary Handling: Understanding that a glass at index overflows into and of the next row is the “Aha!” moment for this problem.

Final Thoughts

This problem is a fantastic introduction to how simple rules (like splitting overflow) can create complex distributions. In real-world software engineering, these types of “flow” algorithms are used in load balancing, where network traffic must be distributed across multiple servers, or in financial systems to calculate how tax or interest cascades through different account tiers. Mastering the ability to model a physical process with code is a core skill for any senior developer.