Leetcode 799. Champagne Tower
Understanding the problem
The problem is to return how much liquid will be collected by any glass within a pyramid stacked in such a way that the first row contains 1 glass, the second contains 2, and so on up to the 100th row. Each glass holds one cup (250ml) of champagne.
The way the liquid distribution works is that champagne is poured into the top glass, and once it's full, any excessive champagne is equally split into the two glasses underneath. This process keeps on happening continuously such that the glasses underneath keep on filling until they are full and their excess also gets divided amongst the two glasses under them.
We are given three inputs: poured
, query_glass
, and query_row
. poured
tells us the amount of champagne being poured into the top glass. query_glass
and query_row
tell us the index of the glass whose fill level we need to find out.
Example
Let's take a simple example to understand the problem better. Let say poured = 2
, query_glass = 1
, and query_row = 1
. Here, we are pouring two cups of champagne into the top glass (index 0,0), so after pouring, the top glass would be full and the excess one cup would split equally and pour into the two glasses in the second row (indexed as 1,0 and 1,1). And since both these glasses were initially empty, they would now be half full. And hence the fill level of any glass in the first row would be 0.5.
Approach
The solution for this problem uses a 2D dynamic programming approach.
-
Initialize a 2D DP array with dimensions
query_row+1
on both rows and columns. For the first row and the first column, fill them with the providedpoured
value. The rest of the elements will be filled with 0 initially. -
Loop
i
from 0 throughquery_row-1
. Within this loop, loopj
from 0 throughi
.i
represents the current row andj
represents the current glass. -
For every glass in the row, if the amount of champagne in it is more than 1 cup, take the excess champagne and split it equally and add it to the two glasses in the next row. These two glasses are represented by
dp[i+1][j]
anddp[i+1][j+1]
in the DP array. -
Repeat this process for all the rows up to
query_row
. -
The amount of champagne in the
query_glass
of thequery_row
will bedp[query_row][query_glass]
. Since no glass can hold more than 1 cup of champagne, if the fill level of the queried glass is more than one, return 1, else return the fill level.
C++ Solution
1 2cpp 3class Solution { 4 public: 5 double champagneTower(int poured, int query_row, int query_glass) { 6 vector<vector<double>> dp(query_row + 1, vector<double>(query_row + 1)); 7 dp[0][0] = poured; 8 9 for (int i = 0; i < query_row; ++i) 10 for (int j = 0; j <= i; ++j) 11 if (dp[i][j] > 1) { 12 dp[i + 1][j] += (dp[i][j] - 1) / 2.0; 13 dp[i + 1][j + 1] += (dp[i][j] - 1) / 2.0; 14 } 15 16 return min(1.0, dp[query_row][query_glass]); 17 } 18};
Java Solution
1 2java 3class Solution { 4 public double champagneTower(int poured, int query_row, int query_glass) { 5 double[][] dp = new double[query_row+1][query_row+1]; 6 dp[0][0] = poured; 7 8 for (int i = 0; i < query_row; i++) { 9 for (int j = 0; j <= i; j++) { 10 if (dp[i][j] > 1) { 11 double excess = (dp[i][j] - 1) / 2; 12 dp[i+1][j] += excess; 13 dp[i+1][j+1] += excess; 14 } 15 } 16 } 17 18 return Math.min(1, dp[query_row][query_glass]); 19 } 20}
Python Solution
1 2python 3class Solution: 4 def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float: 5 dp = [[0.0 for _ in range(query_row + 1)] for _ in range(query_row + 1)] 6 dp[0][0] = poured 7 8 for i in range(query_row): 9 for j in range(i+1): 10 excess = (dp[i][j] - 1) / 2 11 if excess > 0: 12 dp[i+1][j] += excess 13 dp[i+1][j+1] += excess 14 15 return min(1, dp[query_row][query_glass])
JavaScript Solution
1
2javascript
3class Solution {
4 champagneTower(poured, query_row, query_glass) {
5 let dp = Array.from({length: query_row + 1}, () => Array(query_row + 1).fill(0));
6 dp[0][0] = poured;
7
8 for(let i=0; i<query_row; i++){
9 for(let j=0; j<=i; j++){
10 if(dp[i][j] > 1){
11 let excess = (dp[i][j]-1)/2;
12 dp[i+1][j] += excess;
13 dp[i+1][j+1] += excess;
14 }
15 }
16 }
17
18 return Math.min(1, dp[query_row][query_glass]);
19 }
20}
These solutions implement the same approach discussed above in different programming languages: C++, Java, Python, and JavaScript. They all use a 2D dynamic programming approach.
The algorithm first initializes a 2D array with the quantity of champagne poured in. Then, it checks if there is excess champagne in each glass and distributes the excess equally to the two next glasses below it. The process continues until we reach our target glass. While implementing, special care is taken to handle the edge cases and prevent out of bound array errors.
The return value is the champagne quantity in the target glass, with an upper limit of 1 glass of champagne as no glass can hold more than 1 cup of champagne.
Lastly, let's discuss the time complexity of these solutions. The outer loop runs query_row
times, and the inner loop runs i
times for each i
in query_row
. Therefore, the overall time complexity of this solution is O(nยฒ) where n is query_row
. This is acceptable because the maximum value of query_row
is limited (<= 100).
Follow this approach if you want to solve more complex problems involving splitting or sharing something (not necessarily champagne!) into a pyramid or similar structures. The key is to figure out how to divide and distribute the quantities and check whether they exceed some capacity or not.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.