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.
1using System;
2
3public class Solution {
4 public double ChampagneTower(int poured, int query_row, int query_glass) {
5 double[,] tower = new double[101, 101];
6 tower[0, 0] = poured;
7 for (int i = 0; i < 100; i++) {
8 for (int j = 0; j <= i; j++) {
9 if (tower[i, j] >= 1) {
10 double overflow = (tower[i, j] - 1) / 2.0;
11 tower[i + 1, j] += overflow;
12 tower[i + 1, j + 1] += overflow;
13 }
14 }
15 }
16 return Math.Min(1.0, tower[query_row, query_glass]);
17 }
18
19 public static void Main(string[] args) {
20 Solution s = new Solution();
21 Console.WriteLine("{0:F5}", s.ChampagneTower(2, 1, 1));
22 }
23}This approach uses a 2D array 'tower' to record the champagne quantities in each glass. The overflow is computed and propagated to the next row of glasses.
We use a linear array 'dp' to hold the champagne amounts for each glass in the current row, updating in place to manage the overflow process effectively as we advance through the rows.