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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Champagne Tower

Difficulty: Medium

Problem Description

We stack glasses in a pyramid, where the first row has 1 glass, the second row has 2 glasses, and so on until the 100th row. Each glass holds one cup of champagne. When champagne is poured into the top glass, any excess liquid will fall equally to the glasses immediately to the left and right. Given a number of cups poured, return how full the jth glass in the ith row is.

Key Insights

  • The glasses are arranged in a triangular pattern, with each glass potentially overflowing into two glasses below it.
  • Champagne can only fill to a maximum of one cup; any excess is distributed evenly to the glasses below.
  • The problem can be solved using a dynamic programming approach that keeps track of the amount of champagne in each glass.

Space and Time Complexity

Time Complexity: O(n^2), where n is the number of rows (up to 100). Space Complexity: O(n), to store the amount of champagne in each glass for the current row.

Solution

The problem can be approached using a dynamic programming table (or a list of lists) where each entry represents the amount of champagne in a given glass. We initialize the top glass and iterate through each row, distributing the excess champagne to the glasses below. We stop when we reach the desired row and glass.

Code Solutions

def champagneTower(poured: int, query_row: int, query_glass: int) -> float:
    # Initialize a 2D list to store the amount of champagne in each glass
    tower = [[0] * (i + 1) for i in range(100)]
    tower[0][0] = poured  # Start by pouring into the top glass

    for i in range(100):  # Iterate over each row
        for j in range(i + 1):  # Iterate over each glass in the current row
            if tower[i][j] > 1:  # Check if the glass overflows
                overflow = tower[i][j] - 1  # Calculate overflow
                tower[i][j] = 1  # Set current glass to full
                # Distribute overflow to the glasses below
                if i + 1 < 100:  # Ensure we're within bounds
                    tower[i + 1][j] += overflow / 2  # Left glass
                    tower[i + 1][j + 1] += overflow / 2  # Right glass

    return min(1, tower[query_row][query_glass])  # Return the amount in the queried glass (max 1)
← Back to All Questions