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.

1. 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 provided poured value. The rest of the elements will be filled with 0 initially.

2. Loop i from 0 through query_row-1. Within this loop, loop j from 0 through i. i represents the current row and j represents the current glass.

3. 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] and dp[i+1][j+1] in the DP array.

4. Repeat this process for all the rows up to query_row.

5. The amount of champagne in the query_glass of the query_row will be dp[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.