Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A glass retains one cup and sends only its excess to the next row, half to each child. Since liquid flows only downward, we can accumulate all incoming liquid row by row. Storing total inflow, rather than immediately capping each cell, preserves the amount that must overflow.

Approach

Allocate the triangular rows through query_row and place poured in the top cell.
For each glass before the queried row, calculate (inflow - 1) / 2. If positive, add that amount to both children; otherwise it has no overflow. Contributions from both parents add together.
Return the queried glass's accumulated inflow capped at one. No rows below it are needed, and zero poured champagne naturally leaves every glass empty.

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

        for r in range(query_row):
            for c in range(r + 1):
                next = (levels[r][c] - 1) / 2
                if next > 0:
                    levels[r + 1][c] += next
                    levels[r + 1][c + 1] += next

        # print(levels)
        return min(1, levels[query_row][query_glass])

Complexity analysis

Let r = query_row. The triangular table contains Θ(r²) glasses and each is processed once, so time and auxiliary space are both O(r²).