799. Champagne Tower - Explanation

Description

A tower has 100 rows of glasses. Row r contains glasses numbered 0 through r, and each glass holds one cup. Pour poured cups into glass (0,0). A glass keeps up to one cup and divides any excess equally between glasses (r+1,c) and (r+1,c+1) directly below it. Excess below the last row is discarded. Return the amount in glass (query_row,query_glass) after the liquid settles, as a number from 0 to 1. Rows and columns are zero-indexed.

Hatching shows how full each glass is; the dashed box marks the queried glass.

Example 1:

Champagne Tower, example 1: illustration of the example

Input: poured = 4
query_row = 2
query_glass = 1

Output: 0.5

Explanation: The top glass keeps 1 cup and sends 1.5 cups to each glass in row 1. Each of those glasses sends 0.25 cups to the middle glass in row 2, giving it 0.5 cups.

Example 2:

Champagne Tower, example 2: illustration of the example

Input: poured = 4
query_row = 2
query_glass = 0

Output: 0.25

Explanation: Each glass in row 1 receives 1.5 cups. The leftmost glass in row 2 receives half of the left parent's 0.5-cup excess, so it contains 0.25 cups.

Example 3:

Champagne Tower, example 3: illustration of the example

Input: poured = 0
query_row = 0
query_glass = 0

Output: 0.0

Explanation: No liquid is poured, so the top glass stays empty.

Constraints:

0 <= poured <= 1000000000
0 <= query_glass <= query_row < 100

Topics

Dynamic Programming

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Recursion with Memoization - Avoiding redundant calculations by caching subproblem results
Dynamic Programming - Building solutions bottom-up from smaller subproblems
Space Optimization - Reducing DP space complexity by using rolling arrays

1. Recursion

Intuition

Each glass receives champagne from the two glasses directly above it (its "parents"). When a glass overflows, half of the excess spills to each child below. We can recursively compute how much champagne flows into any glass by summing the overflow from its two parent glasses. The base case is the top glass, which receives all the poured champagne.

Algorithm

Define a recursive function that returns the total champagne flowing into glass (row, glass).
Base case: if we are out of bounds, return 0. If at position (0, 0), return the total poured amount.
For any other glass, compute the overflow from the left parent (row-1, glass-1) and right parent (row-1, glass).
Each parent contributes half of its excess (amount - 1) if positive.
The final answer is the minimum of 1 and the computed flow for the queried glass.

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        def rec(row, glass):
            if row < 0 or glass < 0 or glass > row:
                return 0

            if row == 0 and glass == 0:
                return poured

            left_parent = max(0, rec(row - 1, glass - 1) - 1)
            right_parent = max(0, rec(row - 1, glass) - 1)

            return (left_parent + right_parent) / 2

        return min(1, rec(query_row, query_glass))

public class Solution {
    public double champagneTower(int poured, int query_row, int query_glass) {
        return Math.min(1, rec(poured, query_row, query_glass));
    }

    private double rec(int poured, int row, int glass) {
        if (row < 0 || glass < 0 || glass > row) {
            return 0;
        }

        if (row == 0 && glass == 0) {
            return poured;
        }

        double leftParent = Math.max(0, rec(poured, row - 1, glass - 1) - 1);
        double rightParent = Math.max(0, rec(poured, row - 1, glass) - 1);

        return (leftParent + rightParent) / 2;
    }
}

class Solution {
public:
    double champagneTower(int poured, int query_row, int query_glass) {
        return min(1.0, rec(poured, query_row, query_glass));
    }

private:
    double rec(int poured, int row, int glass) {
        if (row < 0 || glass < 0 || glass > row) {
            return 0;
        }

        if (row == 0 && glass == 0) {
            return poured;
        }

        double leftParent = max(0.0, rec(poured, row - 1, glass - 1) - 1);
        double rightParent = max(0.0, rec(poured, row - 1, glass) - 1);

        return (leftParent + rightParent) / 2;
    }
};

class Solution {
    /**
     * @param {number} poured
     * @param {number} query_row
     * @param {number} query_glass
     * @return {number}
     */
    champagneTower(poured, query_row, query_glass) {
        const rec = (row, glass) => {
            if (row < 0 || glass < 0 || glass > row) {
                return 0;
            }

            if (row === 0 && glass === 0) {
                return poured;
            }

            const leftParent = Math.max(0, rec(row - 1, glass - 1) - 1);
            const rightParent = Math.max(0, rec(row - 1, glass) - 1);

            return (leftParent + rightParent) / 2;
        };

        return Math.min(1, rec(query_row, query_glass));
    }
}

public class Solution {
    public double ChampagneTower(int poured, int query_row, int query_glass) {
        return Math.Min(1, Rec(poured, query_row, query_glass));
    }

    private double Rec(int poured, int row, int glass) {
        if (row < 0 || glass < 0 || glass > row) {
            return 0;
        }

        if (row == 0 && glass == 0) {
            return poured;
        }

        double leftParent = Math.Max(0, Rec(poured, row - 1, glass - 1) - 1);
        double rightParent = Math.Max(0, Rec(poured, row - 1, glass) - 1);

        return (leftParent + rightParent) / 2;
    }
}

func champagneTower(poured int, query_row int, query_glass int) float64 {
    var rec func(row, glass int) float64
    rec = func(row, glass int) float64 {
        if row < 0 || glass < 0 || glass > row {
            return 0
        }

        if row == 0 && glass == 0 {
            return float64(poured)
        }

        leftParent := math.Max(0, rec(row-1, glass-1)-1)
        rightParent := math.Max(0, rec(row-1, glass)-1)

        return (leftParent + rightParent) / 2
    }

    return math.Min(1, rec(query_row, query_glass))
}

class Solution {
    fun champagneTower(poured: Int, query_row: Int, query_glass: Int): Double {
        fun rec(row: Int, glass: Int): Double {
            if (row < 0 || glass < 0 || glass > row) {
                return 0.0
            }

            if (row == 0 && glass == 0) {
                return poured.toDouble()
            }

            val leftParent = maxOf(0.0, rec(row - 1, glass - 1) - 1)
            val rightParent = maxOf(0.0, rec(row - 1, glass) - 1)

            return (leftParent + rightParent) / 2
        }

        return minOf(1.0, rec(query_row, query_glass))
    }
}

class Solution {
    func champagneTower(_ poured: Int, _ query_row: Int, _ query_glass: Int) -> Double {
        func rec(_ row: Int, _ glass: Int) -> Double {
            if row < 0 || glass < 0 || glass > row {
                return 0
            }

            if row == 0 && glass == 0 {
                return Double(poured)
            }

            let leftParent = max(0, rec(row - 1, glass - 1) - 1)
            let rightParent = max(0, rec(row - 1, glass) - 1)

            return (leftParent + rightParent) / 2
        }

        return min(1, rec(query_row, query_glass))
    }
}

impl Solution {
    pub fn champagne_tower(poured: i32, query_row: i32, query_glass: i32) -> f64 {
        fn rec(poured: i32, row: i32, glass: i32) -> f64 {
            if row < 0 || glass < 0 || glass > row {
                return 0.0;
            }
            if row == 0 && glass == 0 {
                return poured as f64;
            }
            let left_parent = (rec(poured, row - 1, glass - 1) - 1.0).max(0.0);
            let right_parent = (rec(poured, row - 1, glass) - 1.0).max(0.0);
            (left_parent + right_parent) / 2.0
        }

        (rec(poured, query_row, query_glass)).min(1.0)
    }
}

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n)$

Where $n$ is the given $queryRow$ .

2. Dynamic Programming (Top-Down)

Intuition

The recursive solution recalculates the same glasses many times. By storing computed values in a memoization table, we avoid redundant work. Each glass only needs to be computed once since its inflow depends only on the glasses above it.

Algorithm

Create a memo table to store the champagne flow for each (row, glass) position.
Initialize memo[0][0] with the poured amount.
Use the same recursive logic as before, but check the memo before computing.
Store computed results in the memo table before returning.
Return min(1, memo[query_row][query_glass]).

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        memo = { (0, 0) : poured }

        def rec(row, glass):
            if row < 0 or glass < 0 or glass > row:
                return 0
            if (row, glass) in memo:
                return memo[(row, glass)]

            left_parent = max(0, rec(row - 1, glass - 1) - 1)
            right_parent = max(0, rec(row - 1, glass) - 1)

            memo[(row, glass)] = (left_parent + right_parent) / 2
            return memo[(row, glass)]

        return min(1, rec(query_row, query_glass))

public class Solution {
    public double champagneTower(int poured, int query_row, int query_glass) {
        double[][] memo = new double[query_row + 5][];
        for (int i = 0; i < query_row + 5; i++) {
            memo[i] = new double[i + 1];
            Arrays.fill(memo[i], -1);
        }
        memo[0][0] = poured;

        return Math.min(1, rec(memo, query_row, query_glass));
    }

    private double rec(double[][] memo, int row, int glass) {
        if (row < 0 || glass < 0 || glass > row) {
            return 0;
        }

        if (memo[row][glass] != -1) {
            return memo[row][glass];
        }

        double leftParent = Math.max(0, rec(memo, row - 1, glass - 1) - 1);
        double rightParent = Math.max(0, rec(memo, row - 1, glass) - 1);

        memo[row][glass] = (leftParent + rightParent) / 2;
        return memo[row][glass];
    }
}

class Solution {
public:
    double champagneTower(int poured, int query_row, int query_glass) {
        vector<vector<double>> memo(query_row + 5);
        for (int i = 0; i <= query_row + 4; i++) {
            memo[i].resize(i + 1, -1);
        }

        memo[0][0] = poured;
        return min(1.0, rec(memo, query_row, query_glass));
    }

private:
    double rec(vector<vector<double>>& memo, int row, int glass) {
        if (row < 0 || glass < 0 || glass > row) {
            return 0;
        }

        if (memo[row][glass] != -1) {
            return memo[row][glass];
        }

        double leftParent = max(0.0, rec(memo, row - 1, glass - 1) - 1);
        double rightParent = max(0.0, rec(memo, row - 1, glass) - 1);

        memo[row][glass] = (leftParent + rightParent) / 2;
        return memo[row][glass];
    }
};

class Solution {
    /**
     * @param {number} poured
     * @param {number} query_row
     * @param {number} query_glass
     * @return {number}
     */
    champagneTower(poured, query_row, query_glass) {
        const memo = Array.from({ length: query_row + 5 }, (_, i) =>
            Array(i + 1).fill(-1),
        );
        memo[0][0] = poured;

        const rec = (row, glass) => {
            if (row < 0 || glass < 0 || glass > row) {
                return 0;
            }

            if (memo[row][glass] != -1) {
                return memo[row][glass];
            }

            const leftParent = Math.max(0, rec(row - 1, glass - 1) - 1);
            const rightParent = Math.max(0, rec(row - 1, glass) - 1);

            memo[row][glass] = (leftParent + rightParent) / 2;
            return memo[row][glass];
        };

        return Math.min(1, rec(query_row, query_glass));
    }
}

public class Solution {
    private double[][] memo;

    public double ChampagneTower(int poured, int query_row, int query_glass) {
        memo = new double[query_row + 5][];
        for (int i = 0; i < query_row + 5; i++) {
            memo[i] = new double[i + 1];
            Array.Fill(memo[i], -1);
        }
        memo[0][0] = poured;

        return Math.Min(1, Rec(query_row, query_glass));
    }

    private double Rec(int row, int glass) {
        if (row < 0 || glass < 0 || glass > row) {
            return 0;
        }

        if (memo[row][glass] != -1) {
            return memo[row][glass];
        }

        double leftParent = Math.Max(0, Rec(row - 1, glass - 1) - 1);
        double rightParent = Math.Max(0, Rec(row - 1, glass) - 1);

        memo[row][glass] = (leftParent + rightParent) / 2;
        return memo[row][glass];
    }
}

func champagneTower(poured int, query_row int, query_glass int) float64 {
    memo := make([][]float64, query_row+5)
    for i := 0; i <= query_row+4; i++ {
        memo[i] = make([]float64, i+1)
        for j := range memo[i] {
            memo[i][j] = -1
        }
    }
    memo[0][0] = float64(poured)

    var rec func(row, glass int) float64
    rec = func(row, glass int) float64 {
        if row < 0 || glass < 0 || glass > row {
            return 0
        }

        if memo[row][glass] != -1 {
            return memo[row][glass]
        }

        leftParent := math.Max(0, rec(row-1, glass-1)-1)
        rightParent := math.Max(0, rec(row-1, glass)-1)

        memo[row][glass] = (leftParent + rightParent) / 2
        return memo[row][glass]
    }

    return math.Min(1, rec(query_row, query_glass))
}

class Solution {
    fun champagneTower(poured: Int, query_row: Int, query_glass: Int): Double {
        val memo = Array(query_row + 5) { i -> DoubleArray(i + 1) { -1.0 } }
        memo[0][0] = poured.toDouble()

        fun rec(row: Int, glass: Int): Double {
            if (row < 0 || glass < 0 || glass > row) {
                return 0.0
            }

            if (memo[row][glass] != -1.0) {
                return memo[row][glass]
            }

            val leftParent = maxOf(0.0, rec(row - 1, glass - 1) - 1)
            val rightParent = maxOf(0.0, rec(row - 1, glass) - 1)

            memo[row][glass] = (leftParent + rightParent) / 2
            return memo[row][glass]
        }

        return minOf(1.0, rec(query_row, query_glass))
    }
}

class Solution {
    func champagneTower(_ poured: Int, _ query_row: Int, _ query_glass: Int) -> Double {
        var memo = [[Double]]()
        for i in 0..<(query_row + 5) {
            memo.append([Double](repeating: -1, count: i + 1))
        }
        memo[0][0] = Double(poured)

        func rec(_ row: Int, _ glass: Int) -> Double {
            if row < 0 || glass < 0 || glass > row {
                return 0
            }

            if memo[row][glass] != -1 {
                return memo[row][glass]
            }

            let leftParent = max(0, rec(row - 1, glass - 1) - 1)
            let rightParent = max(0, rec(row - 1, glass) - 1)

            memo[row][glass] = (leftParent + rightParent) / 2
            return memo[row][glass]
        }

        return min(1, rec(query_row, query_glass))
    }
}

impl Solution {
    pub fn champagne_tower(poured: i32, query_row: i32, query_glass: i32) -> f64 {
        let qr = query_row as usize;
        let mut memo: Vec<Vec<f64>> = (0..qr + 5)
            .map(|i| vec![-1.0; i + 1])
            .collect();
        memo[0][0] = poured as f64;

        fn rec(memo: &mut Vec<Vec<f64>>, row: i32, glass: i32) -> f64 {
            if row < 0 || glass < 0 || glass > row {
                return 0.0;
            }
            let (r, g) = (row as usize, glass as usize);
            if memo[r][g] != -1.0 {
                return memo[r][g];
            }
            let left_parent = (rec(memo, row - 1, glass - 1) - 1.0).max(0.0);
            let right_parent = (rec(memo, row - 1, glass) - 1.0).max(0.0);
            memo[r][g] = (left_parent + right_parent) / 2.0;
            memo[r][g]
        }

        rec(&mut memo, query_row, query_glass).min(1.0)
    }
}

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n * m)$

Where $n$ is the given $queryRow$ and $m$ is the given $queryGlass$ .

3. Dynamic Programming (Bottom-Up)

Intuition

Instead of working backwards from the query position, we can simulate the pouring process from top to bottom. We track how much champagne flows into each glass. When a glass overflows (has more than 1 unit), we distribute the excess equally to the two glasses below it.

Algorithm

Create a 2D array where dp[row][glass] represents the total flow into that glass.
Set dp[0][0] = poured.
For each row from 0 to query_row - 1:
- For each glass in that row, if the flow exceeds 1, compute the excess.
- Add half the excess to each of the two glasses below.
Return min(1, dp[query_row][query_glass]).

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        dp = [[0] * (i + 1) for i in range(query_row + 5)]
        dp[0][0] += poured

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

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

public class Solution {
    public double champagneTower(int poured, int query_row, int query_glass) {
        double[][] dp = new double[query_row + 5][];
        for (int i = 0; i < query_row + 5; i++) {
            dp[i] = new double[i + 1];
        }

        dp[0][0] += poured;

        for (int row = 0; row < Math.min(99, query_row + 1); row++) {
            for (int glass = 0; glass <= row; glass++) {
                double excess = (dp[row][glass] - 1.0) / 2.0;
                if (excess > 0) {
                    dp[row + 1][glass] += excess;
                    dp[row + 1][glass + 1] += excess;
                }
            }
        }

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

class Solution {
public:
    double champagneTower(int poured, int query_row, int query_glass) {
        vector<vector<double>> dp(query_row + 5);
        for (int i = 0; i <= query_row + 4; i++) {
            dp[i].resize(i + 1, 0);
        }

        dp[0][0] += poured;

        for (int row = 0; row < min(99, query_row + 1); row++) {
            for (int glass = 0; glass <= row; glass++) {
                double excess = (dp[row][glass] - 1.0) / 2.0;
                if (excess > 0) {
                    dp[row + 1][glass] += excess;
                    dp[row + 1][glass + 1] += excess;
                }
            }
        }

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

class Solution {
    /**
     * @param {number} poured
     * @param {number} query_row
     * @param {number} query_glass
     * @return {number}
     */
    champagneTower(poured, query_row, query_glass) {
        const dp = Array.from({ length: query_row + 5 }, (_, i) =>
            Array(i + 1).fill(0),
        );
        dp[0][0] += poured;

        for (let row = 0; row < Math.min(99, query_row + 1); row++) {
            for (let glass = 0; glass <= row; glass++) {
                const excess = (dp[row][glass] - 1.0) / 2.0;
                if (excess > 0) {
                    dp[row + 1][glass] += excess;
                    dp[row + 1][glass + 1] += excess;
                }
            }
        }

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

public class Solution {
    public double ChampagneTower(int poured, int query_row, int query_glass) {
        double[][] dp = new double[query_row + 5][];
        for (int i = 0; i < query_row + 5; i++) {
            dp[i] = new double[i + 1];
        }

        dp[0][0] = poured;

        for (int row = 0; row < Math.Min(99, query_row + 1); row++) {
            for (int glass = 0; glass <= row; glass++) {
                double excess = (dp[row][glass] - 1.0) / 2.0;
                if (excess > 0) {
                    dp[row + 1][glass] += excess;
                    dp[row + 1][glass + 1] += excess;
                }
            }
        }

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

func champagneTower(poured int, query_row int, query_glass int) float64 {
    dp := make([][]float64, query_row+5)
    for i := 0; i <= query_row+4; i++ {
        dp[i] = make([]float64, i+1)
    }

    dp[0][0] = float64(poured)

    limit := 99
    if query_row+1 < limit {
        limit = query_row + 1
    }
    for row := 0; row < limit; row++ {
        for glass := 0; glass <= row; glass++ {
            excess := (dp[row][glass] - 1.0) / 2.0
            if excess > 0 {
                dp[row+1][glass] += excess
                dp[row+1][glass+1] += excess
            }
        }
    }

    if dp[query_row][query_glass] < 1.0 {
        return dp[query_row][query_glass]
    }
    return 1.0
}

class Solution {
    fun champagneTower(poured: Int, query_row: Int, query_glass: Int): Double {
        val dp = Array(query_row + 5) { i -> DoubleArray(i + 1) }
        dp[0][0] = poured.toDouble()

        for (row in 0 until minOf(99, query_row + 1)) {
            for (glass in 0..row) {
                val excess = (dp[row][glass] - 1.0) / 2.0
                if (excess > 0) {
                    dp[row + 1][glass] += excess
                    dp[row + 1][glass + 1] += excess
                }
            }
        }

        return minOf(1.0, dp[query_row][query_glass])
    }
}

class Solution {
    func champagneTower(_ poured: Int, _ query_row: Int, _ query_glass: Int) -> Double {
        var dp = [[Double]]()
        for i in 0..<(query_row + 5) {
            dp.append([Double](repeating: 0, count: i + 1))
        }

        dp[0][0] = Double(poured)

        for row in 0..<min(99, query_row + 1) {
            for glass in 0...row {
                let excess = (dp[row][glass] - 1.0) / 2.0
                if excess > 0 {
                    dp[row + 1][glass] += excess
                    dp[row + 1][glass + 1] += excess
                }
            }
        }

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

impl Solution {
    pub fn champagne_tower(poured: i32, query_row: i32, query_glass: i32) -> f64 {
        let qr = query_row as usize;
        let mut dp: Vec<Vec<f64>> = (0..qr + 5)
            .map(|i| vec![0.0; i + 1])
            .collect();
        dp[0][0] = poured as f64;

        for row in 0..99.min(qr + 1) {
            for glass in 0..=row {
                let excess = (dp[row][glass] - 1.0) / 2.0;
                if excess > 0.0 {
                    dp[row + 1][glass] += excess;
                    dp[row + 1][glass + 1] += excess;
                }
            }
        }

        dp[qr][query_glass as usize].min(1.0)
    }
}

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n * m)$

Where $n$ is the given $queryRow$ and $m$ is the given $queryGlass$ .

4. Dynamic Programming (Space Optimized)

Intuition

Since each row only depends on the row directly above it, we do not need to store the entire 2D table. We can use two 1D arrays: one for the previous row and one for the current row being computed. After processing each row, the current row becomes the previous row for the next iteration.

Algorithm

Initialize prev_row with the poured amount at index 0.
For each row from 1 to query_row:
- Create a new cur_row array of appropriate size.
- For each glass in the previous row, if it overflows, distribute half the excess to cur_row[i] and cur_row[i+1].
- Set prev_row = cur_row for the next iteration.
Return min(1, prev_row[query_glass]).

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        prev_row = [poured]  # Flow

        for row in range(1, query_row + 1):
            cur_row = [0] * (row + 1)
            for i in range(row):
                extra = prev_row[i] - 1
                if extra > 0:
                    cur_row[i] += 0.5 * extra
                    cur_row[i + 1] += 0.5 * extra
            prev_row = cur_row

        return min(1, prev_row[query_glass])

public class Solution {
    public double champagneTower(int poured, int query_row, int query_glass) {
        double[] prev_row = new double[] { poured };  // Flow

        for (int row = 1; row <= query_row; row++) {
            double[] cur_row = new double[row + 1];
            for (int i = 0; i < row; i++) {
                double extra = prev_row[i] - 1;
                if (extra > 0) {
                    cur_row[i] += 0.5 * extra;
                    cur_row[i + 1] += 0.5 * extra;
                }
            }
            prev_row = cur_row;
        }

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

class Solution {
public:
    double champagneTower(int poured, int query_row, int query_glass) {
        vector<double> prev_row = {double(poured)};  // Flow

        for (int row = 1; row <= query_row; row++) {
            vector<double> cur_row(row + 1, 0);
            for (int i = 0; i < row; i++) {
                double extra = prev_row[i] - 1;
                if (extra > 0) {
                    cur_row[i] += 0.5 * extra;
                    cur_row[i + 1] += 0.5 * extra;
                }
            }
            prev_row = cur_row;
        }

        return min(1.0, prev_row[query_glass]);
    }
};

class Solution {
    /**
     * @param {number} poured
     * @param {number} query_row
     * @param {number} query_glass
     * @return {number}
     */
    champagneTower(poured, query_row, query_glass) {
        let prev_row = [poured]; // Flow

        for (let row = 1; row <= query_row; row++) {
            let cur_row = new Array(row + 1).fill(0);
            for (let i = 0; i < row; i++) {
                let extra = prev_row[i] - 1;
                if (extra > 0) {
                    cur_row[i] += 0.5 * extra;
                    cur_row[i + 1] += 0.5 * extra;
                }
            }
            prev_row = cur_row;
        }

        return Math.min(1, prev_row[query_glass]);
    }
}

public class Solution {
    public double ChampagneTower(int poured, int query_row, int query_glass) {
        double[] prev_row = new double[] { poured };

        for (int row = 1; row <= query_row; row++) {
            double[] cur_row = new double[row + 1];
            for (int i = 0; i < row; i++) {
                double extra = prev_row[i] - 1;
                if (extra > 0) {
                    cur_row[i] += 0.5 * extra;
                    cur_row[i + 1] += 0.5 * extra;
                }
            }
            prev_row = cur_row;
        }

        return Math.Min(1.0, prev_row[query_glass]);
    }
}

func champagneTower(poured int, query_row int, query_glass int) float64 {
    prevRow := []float64{float64(poured)}

    for row := 1; row <= query_row; row++ {
        curRow := make([]float64, row+1)
        for i := 0; i < row; i++ {
            extra := prevRow[i] - 1
            if extra > 0 {
                curRow[i] += 0.5 * extra
                curRow[i+1] += 0.5 * extra
            }
        }
        prevRow = curRow
    }

    if prevRow[query_glass] < 1.0 {
        return prevRow[query_glass]
    }
    return 1.0
}

class Solution {
    fun champagneTower(poured: Int, query_row: Int, query_glass: Int): Double {
        var prevRow = doubleArrayOf(poured.toDouble())

        for (row in 1..query_row) {
            val curRow = DoubleArray(row + 1)
            for (i in 0 until row) {
                val extra = prevRow[i] - 1
                if (extra > 0) {
                    curRow[i] += 0.5 * extra
                    curRow[i + 1] += 0.5 * extra
                }
            }
            prevRow = curRow
        }

        return minOf(1.0, prevRow[query_glass])
    }
}

class Solution {
    func champagneTower(_ poured: Int, _ query_row: Int, _ query_glass: Int) -> Double {
        var prevRow = [Double(poured)]

        for row in 1...query_row {
            var curRow = [Double](repeating: 0, count: row + 1)
            for i in 0..<row {
                let extra = prevRow[i] - 1
                if extra > 0 {
                    curRow[i] += 0.5 * extra
                    curRow[i + 1] += 0.5 * extra
                }
            }
            prevRow = curRow
        }

        return min(1, prevRow[query_glass])
    }
}

impl Solution {
    pub fn champagne_tower(poured: i32, query_row: i32, query_glass: i32) -> f64 {
        let qr = query_row as usize;
        let mut prev_row = vec![poured as f64];

        for row in 1..=qr {
            let mut cur_row = vec![0.0; row + 1];
            for i in 0..row {
                let extra = prev_row[i] - 1.0;
                if extra > 0.0 {
                    cur_row[i] += 0.5 * extra;
                    cur_row[i + 1] += 0.5 * extra;
                }
            }
            prev_row = cur_row;
        }

        prev_row[query_glass as usize].min(1.0)
    }
}

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n)$

Where $n$ is the given $queryRow$ and $m$ is the given $queryGlass$ .

5. Dynamic Programming (Optimal)

Intuition

We can further optimize by using a single 1D array, processing from right to left within each row. This ensures we do not overwrite values we still need. Each position updates itself with half its excess, while contributing the other half to the next position.

Algorithm

Create a single array dp of size (query_row + 1), initialized with poured at index 0.
For each row from 1 to query_row:
- Iterate from right to left (from index row-1 down to 0).
- If dp[i] > 1, set dp[i] = 0.5 * (dp[i] - 1) and add the same to dp[i+1].
- If dp[i] <= 1, set dp[i] = 0 (it does not overflow).
Return min(1, dp[query_glass]).

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        dp = [poured] + [0] * query_row

        for row in range(1, query_row + 1):
            for i in range(row - 1, -1, -1):
                extra = dp[i] - 1
                if extra > 0:
                    dp[i] = 0.5 * extra
                    dp[i + 1] += 0.5 * extra
                else:
                    dp[i] = 0

        return min(1, dp[query_glass])

public class Solution {
    public double champagneTower(int poured, int query_row, int query_glass) {
        double[] dp = new double[query_row + 1];
        dp[0] = poured;

        for (int row = 1; row <= query_row; row++) {
            for (int i = row - 1; i >= 0; i--) {
                double extra = dp[i] - 1;
                if (extra > 0) {
                    dp[i] = 0.5 * extra;
                    dp[i + 1] += 0.5 * extra;
                } else {
                    dp[i] = 0;
                }
            }
        }

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

class Solution {
public:
    double champagneTower(int poured, int query_row, int query_glass) {
        vector<double> dp(query_row + 1, 0);
        dp[0] = poured;

        for (int row = 1; row <= query_row; row++) {
            for (int i = row - 1; i >= 0; i--) {
                double extra = dp[i] - 1;
                if (extra > 0) {
                    dp[i] = 0.5 * extra;
                    dp[i + 1] += 0.5 * extra;
                } else {
                    dp[i] = 0;
                }
            }
        }

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

class Solution {
    /**
     * @param {number} poured
     * @param {number} query_row
     * @param {number} query_glass
     * @return {number}
     */
    champagneTower(poured, query_row, query_glass) {
        let dp = new Array(query_row + 1).fill(0);
        dp[0] = poured;

        for (let row = 1; row <= query_row; row++) {
            for (let i = row - 1; i >= 0; i--) {
                let extra = dp[i] - 1;
                if (extra > 0) {
                    dp[i] = 0.5 * extra;
                    dp[i + 1] += 0.5 * extra;
                } else {
                    dp[i] = 0;
                }
            }
        }

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

public class Solution {
    public double ChampagneTower(int poured, int query_row, int query_glass) {
        double[] dp = new double[query_row + 1];
        dp[0] = poured;

        for (int row = 1; row <= query_row; row++) {
            for (int i = row - 1; i >= 0; i--) {
                double extra = dp[i] - 1;
                if (extra > 0) {
                    dp[i] = 0.5 * extra;
                    dp[i + 1] += 0.5 * extra;
                } else {
                    dp[i] = 0;
                }
            }
        }

        return Math.Min(1, dp[query_glass]);
    }
}

func champagneTower(poured int, query_row int, query_glass int) float64 {
    dp := make([]float64, query_row+1)
    dp[0] = float64(poured)

    for row := 1; row <= query_row; row++ {
        for i := row - 1; i >= 0; i-- {
            extra := dp[i] - 1
            if extra > 0 {
                dp[i] = 0.5 * extra
                dp[i+1] += 0.5 * extra
            } else {
                dp[i] = 0
            }
        }
    }

    if dp[query_glass] < 1.0 {
        return dp[query_glass]
    }
    return 1.0
}

class Solution {
    fun champagneTower(poured: Int, query_row: Int, query_glass: Int): Double {
        val dp = DoubleArray(query_row + 1)
        dp[0] = poured.toDouble()

        for (row in 1..query_row) {
            for (i in row - 1 downTo 0) {
                val extra = dp[i] - 1
                if (extra > 0) {
                    dp[i] = 0.5 * extra
                    dp[i + 1] += 0.5 * extra
                } else {
                    dp[i] = 0.0
                }
            }
        }

        return minOf(1.0, dp[query_glass])
    }
}

class Solution {
    func champagneTower(_ poured: Int, _ query_row: Int, _ query_glass: Int) -> Double {
        var dp = [Double](repeating: 0, count: query_row + 1)
        dp[0] = Double(poured)

        for row in 1...query_row {
            for i in stride(from: row - 1, through: 0, by: -1) {
                let extra = dp[i] - 1
                if extra > 0 {
                    dp[i] = 0.5 * extra
                    dp[i + 1] += 0.5 * extra
                } else {
                    dp[i] = 0
                }
            }
        }

        return min(1, dp[query_glass])
    }
}

impl Solution {
    pub fn champagne_tower(poured: i32, query_row: i32, query_glass: i32) -> f64 {
        let qr = query_row as usize;
        let mut dp = vec![0.0f64; qr + 1];
        dp[0] = poured as f64;

        for row in 1..=qr {
            for i in (0..row).rev() {
                let extra = dp[i] - 1.0;
                if extra > 0.0 {
                    dp[i] = 0.5 * extra;
                    dp[i + 1] += 0.5 * extra;
                } else {
                    dp[i] = 0.0;
                }
            }
        }

        dp[query_glass as usize].min(1.0)
    }
}

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n)$

Where $n$ is the given $queryRow$ and $m$ is the given $queryGlass$ .

Common Pitfalls

Forgetting to Clamp the Final Result to 1

A glass can receive more champagne than it can hold, but the answer should only report how full it is (max 1.0). Returning the raw flow value without capping it at 1 gives incorrect results for glasses that overflow.

# Wrong: returns overflow amount
return dp[query_row][query_glass]
# Correct: cap at 1.0 (glass can't be more than full)
return min(1, dp[query_row][query_glass])

Distributing Total Flow Instead of Excess

Each glass holds 1 unit before overflowing. A common mistake is distributing the total champagne received to children instead of only the excess (amount - 1). This incorrectly empties glasses that should remain full.

# Wrong: distributes everything
dp[row + 1][glass] += dp[row][glass] / 2
# Correct: only distribute the excess
excess = dp[row][glass] - 1
if excess > 0:
    dp[row + 1][glass] += excess / 2

Incorrect Parent Glass Indices

When computing flow from parent glasses, using wrong indices for left and right parents causes incorrect champagne distribution. The left parent is at (row-1, glass-1) and right parent is at (row-1, glass).

# Wrong: both parents at same index
left_parent = rec(row - 1, glass)
right_parent = rec(row - 1, glass)
# Correct: different parent positions
left_parent = rec(row - 1, glass - 1)
right_parent = rec(row - 1, glass)