Problem Statement in English

You’re given a certain amount of champagne poured into the top glass of a tower.

Each glass holds one cup of champagne.

When the top glass is full, any excess liquid poured will spill equally to the left and right glasses of the next row.

This process continues until there is no more excess liquid.

Given the amount of champagne poured and the position of a specific glass in the tower, return how full that glass is (as a fraction of 1).

Approach

We can simulate the pouring process using a 2D array to represent the tower of glasses. We will iterate through each row of the tower and distribute the excess champagne to the next row until we reach the desired row and glass.

We could actually optimize the space complexity by using a 1D array to represent the current row of glasses, but for clarity, we will use a 2D array in this solution.

Simply start with the top glass and pour all the given champagne.

For each glass, if it has more than 1 cup of champagne, calculate the excess and distribute it to the next row.

Then move to the next row and repeat the process until we reach the query_row.

Finally, return the amount of champagne in the query_glass of the query_row, ensuring that it does not exceed 1.

Solution in Python


class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        tower = [[0 for _ in range(101)] for _ in range(query_row + 2)]

        tower[0][0] = poured

        for i in range(query_row + 1):
            for j in range(i + 1):
                volume = tower[i][j]

                if volume > 1:
                    volume -= 1
                    excess = volume / 2
                    tower[i + 1][j] += excess
                    tower[i + 1][j + 1] += excess

                    tower[i][j] = 1

        return tower[query_row][query_glass]

Complexity

  • Time: $O(N^2)$
    Where $N$ = query_row since we are iterating through the tower up to query_row.

  • Space: $O(N ^ 2)$
    Where $N$ = query_row since we are storing the tower up to query_row.

Mistakes I Made

I was overcomplicating the approach a lot and had to look at the solution.

And we are done.