Sponsored
Sponsored
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.
This approach optimizes the space complexity by using only a single array to store the champagne volumes, representing only two rows at a time.
Time Complexity: O(n^2). Space Complexity: O(n) due to the use of the single array.
1using System;
2
public class Solution {
public double ChampagneTower(int poured, int query_row, int query_glass) {
double[] dp = new double[101];
dp[0] = poured;
for (int i = 0; i < query_row; i++) {
for (int j = i; j >= 0; j--) {
double overflow = (dp[j] - 1.0) / 2.0;
if (overflow > 0) {
dp[j + 1] += overflow;
dp[j] = 1.0;
}
}
}
return Math.Min(1.0, dp[query_glass]);
}
public static void Main(string[] args) {
Solution s = new Solution();
Console.WriteLine("{0:F5}", s.ChampagneTower(2, 1, 1));
}
}By making use of a single-dimensional array 'dp', this C# solution conserves space. It models the champagne flow by sequentially processing and updating the array for each row.