LeetCode 799: Champagne Tower Solution

Master LeetCode problem 799 (Champagne Tower), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

799. Champagne Tower

Medium

Dynamic Programming

Problem Explanation

Explanation:

To solve this problem, we can simulate the pouring of champagne through the glasses pyramid. We start by pouring champagne into the top glass (0, 0), and then simulate the flow of excess champagne to the glasses below.

For each glass, we keep track of the amount of champagne it currently holds. When a glass overflows, we distribute the excess evenly to the glasses directly below it. We repeat this process until we reach the desired row and glass position.

The key idea is to maintain a 2D array to represent the champagne in each glass of the pyramid and update the contents accordingly.

Time complexity: O(100^2) = O(1) since the pyramid has at most 100 rows.
Space complexity: O(100^2) = O(1) for the 2D array representing the pyramid.

: :

Solution Code

class Solution {
    public double champagneTower(int poured, int query_row, int query_glass) {
        double[][] glasses = new double[100][100];
        glasses[0][0] = poured;
        
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j <= i; j++) {
                double overflow = Math.max(0, glasses[i][j] - 1);
                glasses[i][j] = Math.min(1, glasses[i][j]);
                glasses[i + 1][j] += overflow / 2;
                glasses[i + 1][j + 1] += overflow / 2;
            }
        }
        
        return glasses[query_row][query_glass];
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 799 (Champagne Tower)?

This page provides optimized solutions for LeetCode problem 799 (Champagne Tower) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 799 (Champagne Tower)?

The time complexity for LeetCode 799 (Champagne Tower) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 799 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 799 in Java, C++, or Python.

Back to LeetCode Solutions