Domain 2MediumMEDIUM

Champagne Tower

LeetCode problem 799: Champagne Tower (medium).

Domain: medium•Updated: 2026-09-01
#Dynamic Programming

Problem Breakdown

We need to simulate the flow of champagne through a pyramid-shaped stack of glasses. The structure is defined such that row i contains i + 1 glasses (0-indexed). Liquid poured into (0, 0) overflows equally to its two children below: left child at (r+1, c-1) and right child at (r+1, c). Each glass has a capacity of exactly 1. Any amount exceeding 1 flows down; anything less or equal stays in the glass (capped at 1).

Inputs:

  • poured: Total volume poured into the top glass (int).
  • query_row: The row index we are interested in (int, 0≤query_row<1000 \le query\_row < 100).
  • query_glass: The column index within that row (0≤query_glass≤query_row0 \le query\_glass \le query\_row).

Output:

  • A float representing the fill level of the specific glass, capped at 1.0.

Implicit Constraints & Edge Cases:

  • Capacity Capping: We must never return a value >1.0> 1.0. The “excess” calculation is only relevant if current amount >1> 1.
  • Boundary Conditions: Glasses on the left edge (j=0j=0) or right edge of a row do not have children in those directions (e.g., (r+1, -1) doesn’t exist). We must handle these indices carefully.
  • Large Inputs: poured can be up to 10910^9. While this is large for volume, the number of glasses grows linearly with row index (O(R)O(R)), and we only care about propagation depth limited by query_row. The complexity depends on rows processed, not poured amount.
  • Zero Pour: If poured is 0 or small enough to fill nothing beyond capacity, all queried values should be 0 (unless the top glass itself holds it).

Intuition

A brute-force simulation of pouring cup-by-cup would require iterating 10910^9 times if we treat each unit as a discrete event. Even simulating row by row with individual cups is inefficient (O(P)O(P) where P is poured amount) because poured can be very large.

However, the flow logic is deterministic and additive. The state of any glass depends only on the excess from its parents above it. This suggests a Dynamic Programming (DP) or simulation approach based on volume propagation rather than discrete cups. Since we only need to know how much liquid reaches row query_row, we can propagate the total flow downwards layer by layer until we reach that depth.

Key Insight: Instead of tracking “how many full glasses,” track “total amount arriving at this glass.” If a glass receives XX units, and its capacity is 1:

  • Stored value = min⁡(1.0,X)\min(1.0, X) (for the answer).
  • Excess to pass down = max⁡(0.0,X−1)\max(0.0, X - 1).

We iterate through rows from top (0) up to query_row. For each glass in row rr, if it has excess liquid, we distribute half of that excess to its children in row r+1r+1. We stop processing once we reach the target row because flow beyond that doesn’t affect our answer.

Approach

  1. Initialize Grid: Create a DP table (2D array) representing the champagne tower up to query_row. Since constraints limit rows < 100, we can allocate space for roughly (query_row + 2) x (query_row + 2) or handle boundaries dynamically. A square matrix of size sufficient for max constraint is safe and simple (O(R2)O(R^2)).

    • Initialize all cells to 0.
    • Set the top glass (0, 0) to poured.
  2. Propagate Flow: Iterate through rows rr from 0 up to query_row - 1. (We don’t need to propagate overflow FROM row query_row, only TO it).

    • For each column cc in current row:
      • If the amount at (r, c) is greater than 1:
        • Calculate excess = amount - 1.
        • Add excess / 2 to child left (r+1, c-1).
        • Add excess / 2 to child right (r+1, c).
  3. Retrieve Result: After propagation stops at the row above our target (or after processing all relevant rows), read the value from dp[query_row][query_glass]. Cap it at 1.0 just in case logic didn’t cap during flow (though we should ensure storage reflects actual fill).

  4. Return: Return the capped float value.

Complexity Analysis

  • Time Complexity: O(R2)O(R^2), where RR is query_row. We iterate through every cell up to row query_row - 1 and push flow down. Since max rows ≈100\approx 100, this is roughly 50×100=O(1)50 \times 100 = O(1) effectively (constant relative to input size constraints), but formally quadratic in terms of the query depth.
  • Space Complexity: O(R2)O(R^2). We store a grid proportional to the square of the row index. Given query_row < 100, this is negligible memory usage (≈10,000\approx 10,000 floats).

Solution

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        # Initialize DP table. 
        # We need enough rows to reach 'query_row'. 
        # Width needs to accommodate the max column index in that row (which is equal to row index).
        # Using a fixed size slightly larger than constraints for safety and simplicity,
        # or dynamic sizing based on query_row + 1. Let's use min(102) logic implicitly via loop bounds 
        # but allocate dynamically per row width i+2 to handle children indices safely without checks?
        # Actually, standard approach: dp[r][c] where r goes up to query_row.
        
        n = query_row + 1
        # Create a grid with sufficient columns for the max index in any processed row. 
        # Row 'i' has glasses from col 0 to i. Children are at c-1 and c.
        # To avoid boundary checks, we can pad or check bounds. Checking bounds is cleaner logic-wise.
        dp = [[0] * (n + 2) for _ in range(n)] 
        
        # Pour into top glass
        dp[0][0] = float(poured)
        
        # Propagate flow row by row up to query_row - 1 
        # We don't need to process overflow FROM the target row itself.
        for r in range(query_row):
            for c in range(r + 2): # Iterate through valid glasses in current row (0..r)
                if dp[r][c] > 1:
                    excess = dp[r][c] - 1
                    
                    # Distribute to left child and right child below
                    # Left child is at r+1, c-1. Right child is at r+1, c.
                    
                    # Add half overflow to children (if they exist within bounds)
                    if c > 0: 
                        dp[r + 1][c - 1] += excess / 2
                    
                    dp[r + 1][c] += excess / 2
        
        return min(1.0, float(dp[query_row][query_glass]))

Edge Cases Handled

  • Zero Pour (poured = 0): The grid initializes to 0. No overflow occurs. Returns min(1.0, 0), which is 0.0. Correct.
  • Small Pour: If poured fills only top glass or partially second row, the logic correctly caps at 1.0 and passes correct excess (or zero if full).
  • Boundary Columns (query_glass = 0): The loop condition if c > 0 prevents accessing index -1. This handles left-edge glasses which only have a right child below them in the pyramid structure logic, or rather, they push to (r+1, -1) (invalid) and (r+1, 0). My code checks c > 0 before pushing to c-1, effectively ignoring non-existent left children.
  • Large Pour (poured = 1e9): Python handles large floats accurately enough for this problem’s tolerance (double precision). The logic caps values at 1.0 immediately upon storage, preventing overflow of the float variable itself beyond capacity limits.