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.
1function champagneTower(poured, query_row, query_glass) {
2 let tower = Array.from({ length: 101 }, () => Array(101).fill(0));
3 tower[0][0] = poured;
4 for (let i = 0; i < 100; i++) {
5 for (let j = 0; j <= i; j++) {
6 if (tower[i][j] >= 1) {
7 let overflow = (tower[i][j] - 1) / 2;
8 tower[i + 1][j] += overflow;
9 tower[i + 1][j + 1] += overflow;
10 }
11 }
12 }
13 return Math.min(1.0, tower[query_row][query_glass]);
14}
15
16console.log(champagneTower(2, 1, 1).toFixed(5));In this JavaScript implementation, a 2D array 'tower' is used to model the pyramid of glasses. The code iteratively checks each glass, calculating overflows and updating the respective glasses below.
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.
1function champagneTower
Using an array 'dp', we track champagne amount in each current row glass, utilizing a space-efficient strategy to update and handle overflows across rows sequentially.