Generated by Codex with GPT-5

Difficulty: MEDIUM
Problem: Champagne Tower

Problem gist

A tower of glasses is stacked in rows. Row 0 has one glass, row 1 has two glasses, and so on. Each glass can hold exactly one cup. If a glass receives more than one cup, the extra amount spills equally into the two glasses directly below it.

Given the number of cups poured into the top glass, the task is to return how full one queried glass is. The queried position is identified by query_row and query_glass, both zero-indexed.

The answer is always between 0.0 and 1.0, because a glass can be empty, partially full, or full. Extra champagne beyond one cup never stays in that glass; it only flows downward.

Optimal idea

This is a dynamic programming simulation. The amount in a glass depends only on the overflow from the two glasses above it, so the tower can be processed row by row.

The most important detail is to store the total amount that reaches a glass, not just the visible amount inside it. If a glass receives 3.5 cups, it keeps 1.0 cup and spills 2.5 cups. Each child receives 1.25 cups from that glass.

For one row:

• If a glass has amount <= 1, it contributes no overflow.
• If a glass has amount > 1, its overflow is (amount - 1) / 2.
• That overflow is added to both adjacent glasses in the next row.

Only the current row is needed to build the next row, so the solution uses O(query_row) space instead of storing the whole triangle.

How to derive the solution

Start with the top glass. It receives exactly poured cups, so row 0 is just:

[poured]

To build the next row, look at every glass in the current row and ask one local question: how much does it spill? If it spills x, then x goes to the glass below-left and x goes to the glass below-right. Repeating that process creates the exact amount that reaches every glass in the next row.

This local rule is enough because champagne only flows downward one row at a time. There is no sideways movement within a row and no future row can send liquid back upward. Once row r has been computed, it contains all information needed to compute row r + 1.

After simulating through query_row, return the queried amount capped at 1.0. The cap belongs at the answer because the row array intentionally stores total received liquid so that overflow can be computed correctly.

Python solution

from typing import List


class Solution:
    def champagneTower(
        self,
        poured: int,
        query_row: int,
        query_glass: int,
    ) -> float:
        target_row_amounts = self._simulate_until_row(poured, query_row)
        return min(1.0, target_row_amounts[query_glass])

    def _simulate_until_row(self, poured: int, target_row: int) -> List[float]:
        current_row = [float(poured)]

        for _ in range(target_row):
            next_row = [0.0] * (len(current_row) + 1)

            for glass_index, amount in enumerate(current_row):
                # Store total received liquid in each row. Only liquid above
                # capacity spills into the next row.
                overflow_to_each_child = max(0.0, amount - 1.0) / 2.0

                if overflow_to_each_child == 0.0:
                    continue

                next_row[glass_index] += overflow_to_each_child
                next_row[glass_index + 1] += overflow_to_each_child

            current_row = next_row

        return current_row

The time complexity is O(query_row^2) because row 0 has one glass, row 1 has two glasses, and so on through the queried row. Since query_row < 100, this is easily fast enough. The space complexity is O(query_row) because only one row is kept at a time.

Interview follow-ups

Can this be solved with a direct formula?

A direct binomial-style formula is tempting because each overflow splits evenly, like paths in Pascal’s triangle. That shortcut fails in the general case because every intermediate glass has a capacity limit. Once a glass reaches one cup, only the excess continues downward, so each ancestor can cap the flow before it reaches the target.

The dynamic programming simulation handles this cap naturally. Each glass computes its own overflow after applying its one-cup capacity. That makes the row-by-row method the expected interview solution even though the tower shape resembles Pascal’s triangle.

What if many queries use the same poured value?

If the interviewer asks for many glasses after the same pour, precompute the tower once up to the maximum queried row. Store every row in a triangular table, and answer each query by returning min(1.0, table[row][glass]).

This works because the amount in each glass is fixed for a given poured value. The tradeoff is space. Precomputing up to row r takes O(r^2) time and O(r^2) space, but each later query becomes O(1).

What if the tower has a much larger height?

The same recurrence still works, but O(r^2) time may become too expensive for very large r. A practical improvement is to keep the one-dimensional rolling row, as in the main solution, so space stays O(r).

If poured is small relative to the height, a sparse representation can also help. Keep only glasses that receive positive overflow in a dictionary and stop once no glass spills into the next row. This can avoid scanning long rows that are entirely empty, but in the worst case a large pour can still fill a wide triangle, so the worst-case time remains quadratic in the number of simulated rows.

What if each glass has a different capacity?

The recurrence can be adjusted by replacing the fixed 1.0 capacity with capacity[row][glass]. A glass spills max(0, amount - capacity[row][glass]) / 2 to its two children. The queried answer is then capped by that queried glass’s own capacity, or divided by the capacity if the interviewer asks for a fullness ratio.

The idea still works because each glass’s outgoing flow depends only on the amount it received and its own capacity. The complexity stays the same as the original row simulation, assuming capacity lookup is O(1).

What if the split is not exactly half and half?

Use the same flow simulation, but replace the equal split with two ratios. If the left child gets left_ratio and the right child gets right_ratio, the overflow contribution becomes overflow * left_ratio and overflow * right_ratio.

The solution remains correct as long as the split rules are local and downward-only. If the ratios add to one, all spilled liquid is conserved. If they do not, the simulation still follows the given model, but the interpretation changes because liquid is either lost or amplified at each spill.

What if exact arithmetic is required?

The LeetCode problem accepts floating-point answers, and the row limit is small, so Python float is appropriate. If an interviewer asks for exact fractional results, use fractions.Fraction instead of float.

The recurrence does not change. Each overflow is still (amount - 1) / 2, but the arithmetic becomes exact rational arithmetic. The tradeoff is performance: fractions avoid rounding error, but numerators and denominators can grow, so each operation is more expensive than normal floating-point math.