We stack glasses in a pyramid, where the first row has 1 glass, the second row has 2 glasses, and so on until the 100th row. Each glass holds one cup of champagne.
Then, some champagne is poured into the first glass at the top. When the topmost glass is full, any excess liquid poured will fall equally to the glass immediately to the left and right of it. When those glasses become full, any excess champagne will fall equally to the left and right of those glasses, and so on. (A glass at the bottom row has its excess champagne fall on the floor.)
For example, after one cup of champagne is poured, the top most glass is full. After two cups of champagne are poured, the two glasses on the second row are half full. After three cups of champagne are poured, those two cups become full - there are 3 full glasses total now. After four cups of champagne are poured, the third row has the middle glass half full, and the two outside glasses are a quarter full, as pictured below.
Now after pouring some non-negative integer cups of champagne, return how full the jth glass in the ith row is (both i and j are 0-indexed.)
Example 1:
Input: poured = 1, query_row = 1, query_glass = 1 Output: 0.00000 Explanation: We poured 1 cup of champange to the top glass of the tower (which is indexed as (0, 0)). There will be no excess liquid so all the glasses under the top glass will remain empty.
Example 2:
Input: poured = 2, query_row = 1, query_glass = 1 Output: 0.50000 Explanation: We poured 2 cups of champange to the top glass of the tower (which is indexed as (0, 0)). There is one cup of excess liquid. The glass indexed as (1, 0) and the glass indexed as (1, 1) will share the excess liquid equally, and each will get half cup of champange.
Example 3:
Input: poured = 100000009, query_row = 33, query_glass = 17 Output: 1.00000
Constraints:
0 <= poured <= 1090 <= query_glass <= query_row < 100The key idea in #799 Champagne Tower is to simulate how champagne overflows from one glass to the next using dynamic programming. Each glass can hold at most 1 cup of champagne. Any extra amount spills equally into the two glasses directly below it. This naturally forms a triangular structure similar to Pascalās triangle.
Create a 2D DP array where dp[r][c] represents the amount of champagne reaching the glass at row r and column c. Start by pouring the total amount into dp[0][0]. For each glass, if its value exceeds 1, the overflow (value - 1) is split equally between the two glasses in the next row. Continue propagating overflow row by row until the queried row is reached.
The final amount in the target glass is the minimum of 1 and the stored value. Since we only need to simulate up to the queried row, the computation remains efficient.
Time Complexity: O(nĀ²) for processing rows up to the query. Space Complexity: O(nĀ²), which can be optimized to O(n) using a rolling array.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming Simulation | O(nĀ²) | O(nĀ²) |
| Space Optimized DP (1D Row) | O(nĀ²) | O(n) |
NeetCodeIO
In this approach, we simulate the pouring process using a 2D array, where each element represents a glass and stores the amount of champagne in it. We iterate over each row, calculating the overflow and distributing it equally to the glasses directly below the current glass.
Time Complexity: O(n^2) where n is the number of rows traversed. Space Complexity: O(n^2) for the 2D array used to simulate the champagne distribution.
1def champagneTower(poured, query_row, query_glass):
2 dp = [[0] * 101 for _ in range(101)]
3 dp[0][0] = poured
4 for i in range(100):
5 for j in range(i + 1):
6 if dp[i][j] >= 1:
7 overflow = (dp[i][j] - 1) / 2.0
8 dp[i + 1][j] += overflow
9 dp[i + 1][j + 1] += overflow
10 return min(1.0, dp[query_row][query_glass])
11
12print(f"{champagneTower(2, 1, 1):.5f}")We use a 2D list 'dp' to maintain the amount of champagne. For each glass, calculate the overflow and distribute it equally between the two glasses beneath it.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Champagne Tower is a popular medium-level problem that tests dynamic programming and simulation skills. Variants of this problem can appear in technical interviews, including those at large tech companies.
The optimal approach uses dynamic programming to simulate how champagne flows through the tower. Each glass distributes overflow equally to the two glasses below it, and the simulation continues row by row until the target glass is reached.
Yes. Instead of storing the entire 2D DP table, you can maintain only the current and next row using a 1D array. This reduces the space complexity from O(nĀ²) to O(n) while keeping the same logic.
A 2D array or DP table works best because the glasses form a triangular structure across rows and columns. Each cell stores the amount of champagne reaching that glass and helps propagate overflow to the next row.
Instead of using a 2D array, we use a single array to minimize space usage. This array tracks only the current row and is updated row-by-row in place, calculating overflows accordingly.