Leet code 799. Champagne Tower (Medium) : NileshBlog.Tech %

Leetcode 799. Champagne Tower: Hey there, coding enthusiasts! Welcome back to another exciting coding session. Today’s problem is a treat—literally! We’re going to solve the “Champagne Tower” problem.

Table of Contents

Problem Explanation :

In summary, LeetCode 799 Champagne Tower is a coding problem that involves pouring champagne into a tower of glasses and calculating how much champagne a specific glass will contain after the distribution. A code solution can be implemented using mathematical logic.

Leet code 799 problem explaian — Leet code 799 problem explain

Find the Longest Substring Without Repeating Characters: Solution and Algorithm(Opens in a new browser tab)

Approach: Matrix Approach Leet code 799 Champagne Tower

Step 1 – Setting the Stage: In this problem, we imagine a tower of champagne glasses, where each glass can hold some amount of champagne.

Step 2 – Pouring Champagne: Initially, you pour a certain amount of champagne into the top glass.
Step 3 – Flow of Champagne: Champagne flows from overfilled glasses to the glasses below, evenly distributing itself.
Step 4 – Reaching a Glass: Your goal is to determine how much champagne a specific glass in a certain row will contain after the pouring and distribution.

Step 5 – Code Implementation: To solve this problem, you can implement code in your preferred programming language.
Step 6 – Mathematical Logic: The code utilizes mathematical logic to calculate the champagne distribution, considering that if a glass is full, it overflows equally into the glasses below it.
- Logic: each glass has two sides to pour, Left and Right, to calculate the spilled amount be for both calculated using formula : left or right= (X-1)/2 .. X value at previous level glass

Step 7 – Final Result: The code provides the amount of champagne in the glass at the specified row and column, as per the input values.

DRY and RUN :

Leet Code 1658. Minimum Operations to Reduce X to Zero (Medium)

Complexities: Sequential and Parallel Computational Complexity, Anomalies in Parallel Algorithms ?

Leet Code 1048. Longest String Chain (Medium)

C++: Matrix Approach Leet code 799 Champagne Tower

class Solution {
public:
    double champagneTower(int poured, int query_row, int query_glass) {
        
        double res[101][101]={0.0};
        res[0][0]=poured;
        for(int i=0;i<100;i++){
            for(int j=0;j<=i;j++){
                
                if(res[i][j]>=1){
                    res[i+1][j]+=(res[i][j]-1)/2.0;
                    res[i+1][j+1]+=(res[i][j]-1)/2.0;
                    res[i][j]=1;

                }
            }
            
        }
        return res[query_row][query_glass];
    }
};

Java: Matrix Approach Leet code 799

class Solution {
    public double champagneTower(int poured, int query_row, int query_glass) {
        double[][] res = new double[101][101];
        res[0][0] = poured;

        for (int i = 0; i < 100; i++) {
            for (int j = 0; j <= i; j++) {
                if (res[i][j] >= 1) {
                    res[i + 1][j] += (res[i][j] - 1) / 2.0;
                    res[i + 1][j + 1] += (res[i][j] - 1) / 2.0;
                    res[i][j] = 1;
                }
            }
        }

        return res[query_row][query_glass];
    }
}

Python: Matrix Approach Champagne Tower

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        res = [[0.0] * 101 for _ in range(101)]
        res[0][0] = poured

        for i in range(100):
            for j in range(i + 1):
                if res[i][j] >= 1:
                    res[i + 1][j] += (res[i][j] - 1) / 2.0
                    res[i + 1][j + 1] += (res[i][j] - 1) / 2.0
                    res[i][j] = 1

        return res[query_row][query_glass]

JavaScript: Matrix Approach

var champagneTower = function(poured, query_row, query_glass) {
    let res = new Array(101);
    for (let i = 0; i < 101; i++) {
        res[i] = new Array(101).fill(0);
    }

    res[0][0] = poured;

    for (let i = 0; i < 100; i++) {
        for (let j = 0; j <= i; j++) {
            if (res[i][j] >= 1) {
                res[i + 1][j] += (res[i][j] - 1) / 2.0;
                res[i + 1][j + 1] += (res[i][j] - 1) / 2.0;
                res[i][j] = 1;
            }
        }
    }

    return res[query_row][query_glass];
};

List of Some important Leet code Question: