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.
1import java.util.Arrays;
2
3public class ChampagneTower {
4 public static double champagneTower(int poured, int query_row, int query_glass) {
5 double[][] dp = new double[101][101];
6 dp[0][0] = poured;
7 for (int i = 0; i < 100; i++) {
8 for (int j = 0; j <= i; j++) {
9 if (dp[i][j] >= 1) {
10 double overflow = (dp[i][j] - 1) / 2.0;
11 dp[i + 1][j] += overflow;
12 dp[i + 1][j + 1] += overflow;
13 }
14 }
15 }
16 return Math.min(1.0, dp[query_row][query_glass]);
17 }
18
19 public static void main(String[] args) {
20 System.out.printf("%.5f\n", champagneTower(2, 1, 1));
21 }
22}Using a 2D array 'dp', we simulate the champagne pouring process, distributing overflow champagne to subsequent rows. Each element stores the amount of champagne in a corresponding glass.
This Java implementation uses an optimized single-dimensional array 'dp' to keep track of the current row's champagne levels. We iterate through the rows and manage overflow using the same array.