How to Solve the Champagne Tower Problem on LeetCode with Linear DP

ByteDance English Exam

ByteDance recently expanded its internal English proficiency test. The first round in March targeted the international e‑commerce team with vocabulary, listening and speaking tasks. Employees who failed were required to join a daily‑check‑in study group. The new round covers more staff, including non‑mainland lines, and sets a minimum score of TOEFL 72 or IELTS 5.5.

Some colleagues view the requirement as a bargaining chip for salary negotiations, while others see it as a necessary skill investment.

Problem Description

LeetCode problem 799 “Champagne Tower” asks: given a pyramid of glasses where each glass holds 250 ml, pour poured cups of champagne into the top glass. When a glass contains more than 1 cup, the excess is split equally to the two glasses below. Return the amount of champagne in the glass at row query_row and column query_glass (both 0‑indexed).

Example 1: poured = 1, query_row = 1, query_glass = 1 → 0.0 (no overflow). Example 2: poured = 2, query_row = 1, query_glass = 1 → 0.5. Example 3: poured = 100000009, query_row = 33, query_glass = 17 → 1.0.

Linear DP Solution

We model the flow of liquid with a DP array f[i][j] representing the amount of champagne that passes through the glass at row i, column j. Initialize f[0][0] = poured. For each glass, if f[i][j] > 1, the overflow (f[i][j] - 1) / 2 is added to f[i+1][j] and f[i+1][j+1]. The answer is min(1, f[query_row][query_glass]).

Time complexity is O(n²) where n is query_row, and space complexity is O(n²) as well.

Java implementation

class Solution {
    public double champagneTower(int k, int n, int m) {
        double[][] f = new double[n + 10][n + 10];
        f[0][0] = k;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                if (f[i][j] <= 1) continue;
                f[i + 1][j] += (f[i][j] - 1) / 2;
                f[i + 1][j + 1] += (f[i][j] - 1) / 2;
            }
        }
        return Math.min(f[n][m], 1);
    }
}

C++ implementation

class Solution {
public:
    double champagneTower(int k, int n, int m) {
        vector<vector<double>> f(n + 10, vector<double>(n + 10, 0));
        f[0][0] = k;
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= i; ++j) {
                if (f[i][j] <= 1) continue;
                f[i + 1][j] += (f[i][j] - 1.0) / 2.0;
                f[i + 1][j + 1] += (f[i][j] - 1.0) / 2.0;
            }
        }
        return min(f[n][m], 1.0);
    }
};

Python implementation

class Solution:
    def champagneTower(self, k: int, n: int, m: int) -> float:
        f = [[0] * (n + 10) for _ in range(n + 10)]
        f[0][0] = k
        for i in range(n + 1):
            for j in range(i + 1):
                if f[i][j] <= 1:
                    continue
                f[i + 1][j] += (f[i][j] - 1) / 2
                f[i + 1][j + 1] += (f[i][j] - 1) / 2
        return min(f[n][m], 1)

TypeScript implementation

function champagneTower(k: number, n: number, m: number): number {
    const f: number[][] = Array.from({ length: n + 10 }, () => Array(n + 10).fill(0));
    f[0][0] = k;
    for (let i = 0; i <= n; i++) {
        for (let j = 0; j <= i; j++) {
            if (f[i][j] <= 1) continue;
            f[i + 1][j] += (f[i][j] - 1) / 2;
            f[i + 1][j + 1] += (f[i][j] - 1) / 2;
        }
    }
    return Math.min(f[n][m], 1);
}