799. Champagne Tower
Problem Description
This problem presents a scenario where glasses are stacked in a pyramid fashion to form a champagne tower. Each row in the pyramid has a number of glasses equal to the row number, starting from 1 for the first row, 2 for the second row, and continuing up to the 100th row. Each glass can hold one cup of champagne. When we pour champagne into the top glass, it fills glasses below it in the following manner: once the current glass is full, any extra champagne splits equally between the two glasses directly below it. This process continues down the pyramid until the champagne either fills glasses or spills on the floor if it reaches the last row.
The actual problem is to determine how full a specific glass, given by its row (query_row
) and position in the row (query_glass
), is after pouring a certain number of cups (poured
) of champagne into the top glass of the tower.
Intuition
To solve this problem, we can use a dynamic programming approach where we simulate the pouring process. We will create a 2D array that represents the champagne glasses and track the amount of champagne in each glass. When we pour champagne into the glass at the top, we continue to distribute it down the rows. If a glass receives more than one cup of champagne, it overflows, and the excess amount is shared equally between the two glasses directly below it.
We're only interested in the distribution of champagne up to and including the query_row
, so we can limit the simulation to that. By initializing the overflow process from the top and proceeding row by row, we can efficiently calculate how much champagne is in each glass when the overflow process ceases - either when we reach the desired row or when no more champagne can overflow.
When representing the overflow, any glass that has more than one cup of champagne will distribute the excess. This is calculated by subtracting 1 cup (the glass's capacity) from its champagne amount, dividing the remainder by 2, and adding the result to the two glasses below. This is iterated for each row until we get to the row we need to query, which contains the glass of interest.
Finally, we query the amount of champagne in the specific glass. If the glass is full, it will have one cup of champagne; if it is not full, it will have an amount equal to whatever was poured into it through the overflow process. Since glasses can't hold more than one cup, the answer will be 1 if the calculated amount is over 1 cup, or the calculated amount itself if it's less than or equal to 1 cup.
Learn more about Dynamic Programming patterns.
Solution Approach
The solution uses dynamic programming to solve the problem efficiently. Here's how the implementation goes:
-
Create a 2D Array: We initialize a 2D array
f
with dimensions 101x101, which represents the champagne glasses. We use a size of 101 because that accounts for the 100th row potentially overflowing into an additional row below it. -
Base Condition: We set the champagne in the top glass
f[0][0]
to be equal to thepoured
amount. -
Simulate Pouring Process: We iterate through the rows up to
query_row + 1
. For each rowi
, we iterate through the glassesj
in that row up toi + 1
, because the number of glasses in each row is equal to the row number. -
Check for Overflow: Inside the nested loop, we check if a glass has more than one cup of champagne by checking if
f[i][j]
is greater than1
. -
Distribute Excess Champagne: If the glass overflows, we calculate the excess amount that will flow to the glasses below by subtracting one cup and dividing the remainder by two (this is
half
). -
Update Adjacent Glasses: We update the two glasses below the current glass (positions
[i + 1][j]
and[i + 1][j + 1]
in thef
array) by adding thehalf
to both. This represents the flow of excess champagne to lower-level glasses. -
Cap Glass Fullness: We set the current glass
f[i][j]
to1
because a glass can't hold more than one cup of champagne. -
Query Result: After completing the simulation up to the
query_row
, we simply return the value atf[query_row][query_glass]
. If it's more than1
, it means the glass is overflowing, and we return1
. Otherwise, we return the actual value since that's how full the glass is.
The patterns used in the solution are dynamic programming (memoization of intermediate results to avoid recomputation) and simulation (simulating the behavior of champagne pouring over the glasses).
The algorithm iteratively updates the state of the champagne tower as champagne is poured until it reaches the query condition. This allows us to only perform necessary calculations and retrieve the exact fullness of the requested glass in an efficient manner. The dynamic programming pattern reduces the overall time complexity as compared to a naive recursive approach.
Here's the code snippet that performs these steps:
1class Solution:
2 def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
3 f = [[0] * 101 for _ in range(101)]
4 f[0][0] = poured
5 for i in range(query_row + 1):
6 for j in range(i + 1):
7 if f[i][j] > 1:
8 half = (f[i][j] - 1) / 2
9 f[i][j] = 1
10 f[i + 1][j] += half
11 f[i + 1][j + 1] += half
12 return f[query_row][query_glass]
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Suppose we pour 3
cups of champagne into the top glass of a tower and want to find out how full the glass at row 2
, position 1
(zero-indexed) is.
Here's how the process works step-by-step:
-
Step 1 (Initialization): We create the 2D array
f
to represent our glasses, all initially with0
champagne. -
Step 2 (Top Glass): We pour
3
cups into the top glassf[0][0]
, so it becomes3
. -
Step 3 (First Row): As there is an overflow (since
3
>1
), we calculate the excess champagne, which is3 - 1 = 2
cups. We then divide this by2
, so each glass below will receive1
cup.At this point, the array will look like this:
1Row 0: 3 2Row 1: 1 1 3Row 2: 0 0 0
-
Step 4 (Second Row): Now we look at each glass in the first row. Each glass has
1
cup, so no overflow occurs.The array now:
1Row 0: 1 2Row 1: 1 1 3Row 2: 0 0 0
-
Step 5 (Third Row): Since there's no overflow from the first row, the second row's glasses remain as they are.
The final state of the array up to row
2
:1Row 0: 1 2Row 1: 1 1 3Row 2: 0 0 0
-
Step 6 (Result Query): Now we query the fullness of the glass at row
2
, position1
, which corresponds tof[2][1]
. As we can see, it is0
, meaning no champagne has reached this glass. Therefore, the return value would be0
.
In conclusion, after pouring 3
cups of champagne, the glass at row 2
, position 1
is empty. The code provided efficiently simulates the entire pouring process, accounts for any overflows, and gives us the correct amount of champagne in any given glass.
Solution Implementation
1class Solution:
2 def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
3 # Initialize a Pascal's triangle with 101 rows and columns as the champagne tower, and only 0 is filled.
4 tower = [[0.0] * 101 for _ in range(101)]
5
6 # The champagne poured into the top glass.
7 tower[0][0] = poured
8
9 # Simulating the pouring process up to the query_row + 1 because we need values from the given query row.
10 for row in range(query_row + 1):
11 for col in range(row + 1):
12 # If there's an overflow in the current glass...
13 if tower[row][col] > 1:
14 # Calculate the champagne that flows to each glass below.
15 overflow = (tower[row][col] - 1) / 2.0
16 # Reset the current glass to full after overflow.
17 tower[row][col] = 1
18 # Distribute the overflowed champagne to the two glasses below.
19 tower[row + 1][col] += overflow
20 tower[row + 1][col + 1] += overflow
21
22 # Return the amount of champagne in the glass at query_row and query_glass, capped at 1.
23 return min(1, tower[query_row][query_glass])
24
1class Solution {
2
3 // Computes the amount of champagne in a glass located at (queryRow, queryGlass)
4 // after pouring a certain amount into the top glass of the tower.
5 public double champagneTower(int poured, int queryRow, int queryGlass) {
6 // Initialize a 2D array to hold the quantity of champagne in each glass
7 double[][] champagneLevel = new double[101][101];
8
9 // Pour champagne into the top glass
10 champagneLevel[0][0] = poured;
11
12 // Fill the glasses for each row till the queried row
13 for (int row = 0; row <= queryRow; row++) {
14 for (int glass = 0; glass <= row; glass++) {
15 // Check if the current glass is overflowing
16 if (champagneLevel[row][glass] > 1) {
17 // Calculate the amount of champagne that overflows, to be divided between the two glasses below
18 double overflow = (champagneLevel[row][glass] - 1) / 2.0;
19
20 // Current glass should not have more than 1 unit of champagne after overflowing
21 champagneLevel[row][glass] = 1;
22
23 // Distribute the overflowing champagne to the two glasses below it
24 champagneLevel[row + 1][glass] += overflow;
25 champagneLevel[row + 1][glass + 1] += overflow;
26 }
27 }
28 }
29
30 // Return the amount of champagne in the queried glass
31 // (it will be at most 1 since any excess would have overflowed)
32 return champagneLevel[queryRow][queryGlass];
33 }
34}
35
1class Solution {
2public:
3 double champagneTower(int poured, int queryRow, int queryGlass) {
4 // Initialize the array that will store the quantity of champagne in each glass.
5 // Only need 100 rows according to the problem statement.
6 double glasses[100][100] = {0.0};
7
8 // Pour the champagne into the top glass.
9 glasses[0][0] = poured;
10
11 // Start from the top and fill down to the queried row.
12 for (int row = 0; row <= queryRow; ++row) {
13 for (int glass = 0; glass <= row; ++glass) {
14 // Check if there is any overflow in the current glass.
15 if (glasses[row][glass] > 1) {
16 // Calculate the amount of champagne that flows to the glasses below.
17 double overflow = (glasses[row][glass] - 1.0) / 2.0;
18 // Ensure the current glass is filled to its capacity.
19 glasses[row][glass] = 1;
20 // Distribute the overflow to the two glasses below equally.
21 glasses[row + 1][glass] += overflow;
22 glasses[row + 1][glass + 1] += overflow;
23 }
24 }
25 }
26 // Return the amount of champagne in the queried glass.
27 // If the glass is full or under, it will contain the exact amount.
28 // If it did not receive enough champagne, it will contain the remaining amount.
29 return glasses[queryRow][queryGlass];
30 }
31};
32
1// Defines a function to simulate pouring champagne into a tower and queries the amount of champagne
2// in a specific glass at a specific row after the champagne is poured.
3function champagneTower(poured: number, queryRow: number, queryGlass: number): number {
4 // Initialize the first row with the amount of champagne poured into the first glass
5 let currentRow = [poured];
6
7 // Iterate over the rows of the champagne tower until the specified query row is reached
8 for (let rowIndex = 1; rowIndex <= queryRow; rowIndex++) {
9 // Initialize the next row with zeros which will represent the empty glasses
10 const nextRow = new Array(rowIndex + 1).fill(0);
11
12 // Iterate over each glass in the current row
13 for (let glassIndex = 0; glassIndex < rowIndex; glassIndex++) {
14 // If the current glass has more than one unit of champagne, it overflows
15 if (currentRow[glassIndex] > 1) {
16 // Calculate the amount of champagne that overflows from the current glass and distribute it
17 // equally to the two glasses below it in the next row
18 const overflow = (currentRow[glassIndex] - 1) / 2;
19 nextRow[glassIndex] += overflow;
20 nextRow[glassIndex + 1] += overflow;
21 }
22 }
23 // Set the nextRow to be the currentRow for the next iteration
24 currentRow = nextRow;
25 }
26
27 // Return the amount of champagne in the specified glass, capped at 1 because glasses can't hold
28 // more than one unit of champagne
29 return Math.min(1, currentRow[queryGlass]);
30}
31
Time and Space Complexity
Time Complexity
The time complexity of the code is primarily determined by the nested for loops. In the worst case, the loop runs for query_row + 1
iterations, and for each iteration i
, it runs i + 1
times, because the inner loop ranges up to the current row number. Thus, the number of operations can be approximated as a sum of an arithmetic series, which calculates to roughly 1 + 2 + ... + (query_row + 1)
, which is ((query_row + 1) * (query_row + 2)) / 2
. Simplifying this arithmetic series results in O(query_row^2). Hence, the time complexity is O(query_row^2)
.
Space Complexity
The space complexity is determined by the size of the 2D list f
, which is created to store the quantity of champagne in each glass. Since the list is initialized with dimensions 101x101, this is essentially a constant space allocation, not varying with the size of the input. Therefore, the space complexity is O(1)
in terms of the input poured
, query_row
, and query_glass
; however, if considering the size of the grid as part of the complexity, it would be O(101 * 101)
which simplifies to O(1)
under Big O notation since 101 is a constant.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used in a depth first search?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.