algoadvance

Leetcode 799. Champagne Tower

Problem Statement

We stack glasses in a pyramid, where the first row has 1 glass, the second row has 2 glasses, and so on until the 100th row. Each glass holds one cup (250ml) of champagne.

We pour champagne into the first glass. When one glass overflows, any excess liquid spills equally to the glass immediately to the left and right of it on the next row. After pouring some non-negative integer cups of champagne, we want to know how full the j-th glass in the i-th row is (both i and j are 0-indexed).

Formally, return the amount of champagne in the j-th glass of the i-th row, as a float.

Example 1:

Input: poured = 1, query_row = 1, query_glass = 1
Output: 0.00000
Explanation: We poured 1 cup of champagne to the top glass of the tower (which is indexed as (0, 0)). There will be no excess liquid so all the glasses under the top glass will remain empty.

Example 2:

Input: poured = 2, query_row = 1, query_glass = 1
Output: 0.50000
Explanation: We poured 2 cups of champagne to the top glass of the tower (which is indexed as (0, 0)). The excess liquid after the first glass will be evenly distributed to the glasses in the second row.

Clarifying Questions

  1. What is the maximum number of poured cups?
    • It’s stated in the problem that poured is a non-negative integer.
  2. What are the input constraints?
    • 0 <= poured <= 10^9
    • 0 <= query_glass <= query_row < 100

Strategy

  1. Data Structure: We’ll use a 2D array (vector<vector<double>>) to keep track of the amount of champagne contained in each glass.

  2. Flow Simulation: We’ll iterate over each row and simulate the overflow from one glass to the corresponding glasses in the next row.

  3. Handling Overflow: Each glass can hold up to 1 cup. If a glass contains more than 1 cup, the excess is divided equally between the two glasses directly below it in the next row.

  4. Output: Finally, we return the amount in the requested glass, ensuring not to exceed the capacity of 1 cup.

Code

#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    double champagneTower(int poured, int query_row, int query_glass) {
        vector<vector<double>> tower(101, vector<double>(101, 0.0));
        tower[0][0] = (double)poured;
        
        for (int row = 0; row < 100; ++row) {
            for (int glass = 0; glass <= row; ++glass) {
                if (tower[row][glass] > 1.0) {
                    double overflow = tower[row][glass] - 1.0;
                    tower[row][glass] = 1.0;
                    tower[row + 1][glass] += overflow / 2.0;
                    tower[row + 1][glass + 1] += overflow / 2.0;
                }
            }
        }
        
        return min(1.0, tower[query_row][query_glass]);
    }
};

int main() {
    Solution sol;
    cout << sol.champagneTower(2, 1, 1) << endl; // Expected output: 0.5
    cout << sol.champagneTower(1, 1, 1) << endl; // Expected output: 0.0
    return 0;
}

Time Complexity

The time complexity is (O(n^2)) where (n) is the number of rows (at most 100). This is because, under the worst case, we iterate over all the glasses in the 2D array. Given the constraints, this is efficient and feasible.

The solution leverages iterative overflow simulation to ensure accurate champagne distribution to the queried glass, thoroughly processing each step without escalating computational demands unnecessarily.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI