We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Champagne Tower

Number: 815

Difficulty: Medium

Paid? No

Companies: Google, TikTok, National Instruments, Amazon

Problem Description

We have a pyramid of glasses where the i(th) row contains i+1 glasses. When champagne is poured into the top glass, any overflow (amount beyond 1 cup per glass) spills equally into the two glasses immediately below. Given the number of cups poured and a specific glass identified by its row and position (both 0-indexed), compute how full that glass will be.

Key Insights

  • Use dynamic programming to simulate the flow of champagne row-by-row.
  • Each glass can hold at most 1 cup; any excess over 1 is equally distributed to the two glasses directly below.
  • Only the rows from 0 up to query_row need to be simulated, and the answer is the minimum of 1 and the computed value for the target glass.
  • The simulation process is efficient since query_row is limited to less than 100.

Space and Time Complexity

Time Complexity: O(query_row²)
Space Complexity: O(query_row²)

Solution

We solve the problem with dynamic programming by constructing a 2D array (dp) where dp[i][j] holds the amount of champagne in the j(th) glass of row i.

  1. Initialize dp[0][0] with the number of cups poured.
  2. Iterate over each row up to query_row. For each glass in the current row, if its content is greater than 1 cup, compute the overflow (amount - 1). Distribute the overflow equally to the two glasses in the next row (i.e., add half of the overflow to dp[i+1][j] and dp[i+1][j+1]).
  3. After processing all rows, the answer for the target glass is min(1, dp[query_row][query_glass]), as a glass can at most be full (i.e., 1 cup).

Code Solutions

# Define the solution class with the function to compute the champagne tower status.
class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        # Create a 2D list for storing the amount of champagne in each glass.
        dp = [[0.0] * (i + 1) for i in range(query_row + 1)]
        dp[0][0] = poured  # Pour all champagne into the top glass.
        
        # Process rows from 0 to query_row - 1.
        for row in range(query_row):
            for glass in range(len(dp[row])):
                # If the current glass overflows.
                overflow = dp[row][glass] - 1.0 if dp[row][glass] > 1.0 else 0.0
                if overflow > 0:
                    # Distribute the overflow equally to the two glasses below.
                    dp[row + 1][glass] += overflow / 2.0
                    dp[row + 1][glass + 1] += overflow / 2.0
        # Return the minimum of 1 and the computed amount in the target glass.
        return min(1.0, dp[query_row][query_glass])
← Back to All Questions