How do you solve Champagne Tower on LeetCode?

Champagne Tower (LeetCode #799) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Champagne flows downwards and splits equally between two glasses below.

What is the brute force solution for Champagne Tower?

The brute force approach for Champagne Tower is Brute Force, with O(n²) time complexity and O(1) space complexity. We can simulate the pouring of champagne into the glasses row by row. Each glass will hold its champagne and distribute any overflow to the glasses below it. This approach is straightforward but inefficient for larger inputs. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Champagne Tower?

Champagne Tower uses the following concepts: Dynamic Programming. The recommended patterns to study are: Dynamic Programming, 2D Arrays.

What are the interview tips for Champagne Tower?

Clarify the problem statement and constraints before diving into coding. Think about edge cases, such as pouring 0 cups or querying the bottom row. Explain your thought process clearly while coding, as it shows your understanding.

What are common mistakes when solving Champagne Tower?

Not considering the maximum capacity of each glass. Failing to correctly distribute excess champagne to both left and right glasses.

#799

Champagne Tower

Medium

Dynamic ProgrammingDynamic Programming2D Arrays

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

Instead of simulating the entire pouring process, we can use a dynamic programming approach to calculate the amount of champagne in each glass directly. This avoids unnecessary computations and reduces time complexity.

⚙️

Algorithm

3 steps

1Step 1: Create a 2D array to hold the amount of champagne in each glass.
2Step 2: Pour champagne into the top glass and iterate through each row.
3Step 3: For each glass, if it overflows, distribute the excess to the glasses below.

solution.py13 lines

1# Full working Python code
2class Solution:
3    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
4        glasses = [[0] * (i + 1) for i in range(101)]
5        glasses[0][0] = poured
6        for i in range(100):
7            for j in range(i + 1):
8                if glasses[i][j] > 1:
9                    excess = glasses[i][j] - 1
10                    glasses[i][j] = 1
11                    glasses[i + 1][j] += excess / 2
12                    glasses[i + 1][j + 1] += excess / 2
13        return min(1, glasses[query_row][query_glass])

ℹ

Complexity note: The time complexity is O(n) because we only need to iterate through the rows until we reach the query row. The space complexity is O(n) due to the storage of the glasses array.

1Champagne flows downwards and splits equally between two glasses below.
2Each glass can hold a maximum of 1 cup; any excess is distributed.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.