grid47 Exploring patterns and algorithms
Aug 19, 2024
6 min read
Solution to LeetCode 799: Champagne Tower Problem
You are given a champagne tower in the shape of a pyramid. The topmost glass is filled with a specified amount of champagne. When a glass is full, the excess champagne spills equally into the two glasses directly beneath it. Given the total amount of champagne poured, determine how full a particular glass at row query_row and glass query_glass will be after the champagne has spilled.
Problem
Approach
Steps
Complexity
Input: The input consists of three values: `poured`, the total amount of champagne poured into the topmost glass, and `query_row` and `query_glass`, which specify the row and position of the glass to query.
• Explanation: After pouring 3 cups of champagne, the first row has 1 cup, the second row has 1.5 cups (with each glass receiving 0.5 cups), and the third row has the second glass with 0.5 cups (because it receives a portion of the excess from the second row).
• Explanation: Pouring 6 cups results in the first row having 1 cup, the second row having 2 cups (with each glass full), and the third row has the two outer glasses each filled to 0.5 cups.
Approach: The solution simulates the process of pouring champagne into the tower row by row, from top to bottom, and computes how much champagne remains in a given glass.
Observations:
• The amount of champagne poured can be very large, so efficient simulation is necessary to avoid excessive computations.
• We can maintain an array of glasses for each row and keep track of the overflow from each glass, distributing it to the next row.
Steps:
• Start by filling the topmost glass with the poured champagne amount.
• For each subsequent row, calculate the amount of champagne that overflows from the glasses in the previous row.
• For each glass, distribute the excess champagne evenly to the two glasses directly beneath it.
• Stop once the row of interest has been reached and return the amount of champagne in the specified glass.
Empty Inputs:
• If poured equals 0, no champagne is poured, and all glasses remain empty.
Large Inputs:
• If poured is very large (e.g., 10^9), ensure the simulation still runs efficiently within time limits.
Special Values:
• If query_row is 0, the only glass of interest is the topmost glass, which will contain all the poured champagne if it's less than 1 cup.
Constraints:
• Make sure not to exceed the maximum capacity of any glass, as each glass can hold a maximum of 1 cup.
doublechampagneTower(int poured, int query_row, int query_glass) {
This is the function definition for `champagneTower`, which takes in three arguments: `poured` (total champagne poured), `query_row` (the row of the glass to query), and `query_glass` (the specific glass in that row).
2 : Initialization
vector<double> currRow(1, poured);
Initializes a vector `currRow` to hold the current row of glasses, with the first glass containing all the poured champagne.
3 : Loop
for(int i =0; i <= query_row; i++) {
A loop that iterates through each row from the top to the queried row (`query_row`).
4 : Row Initialization
vector<double> nextrow(i +2, 0);
Creates a new row `nextrow` with `i + 2` glasses initialized to 0.0, where `i + 2` accounts for the maximum glasses at that row.
5 : Inner Loop
for(int j =0; j <= i; j++) {
A nested loop that iterates through each glass in the current row `i`.
6 : Champagne Overflow Check
if(currRow[j] >=1) {
Checks if the current glass `currRow[j]` contains more than or equal to 1 unit of champagne, indicating overflow.
7 : Champagne Redistribution
nextrow[j] += (currRow[j] -1)/2.0;
Redistributes the overflow champagne to the left glass in the next row.
8 : Champagne Redistribution
nextrow[j +1] += (currRow[j] -1)/2.0;
Redistributes the overflow champagne to the right glass in the next row.
9 : Champagne Overflow Adjustment
currRow[j] =1;
Sets the current glass to 1, as it can only hold a maximum of 1 unit of champagne.
10 : Row Transition
if(i != query_row) currRow = nextrow;
Transfers the `nextrow` as `currRow` for the next iteration, unless the queried row has been reached.
11 : Return Statement
return currRow[query_glass];
Returns the amount of champagne in the glass specified by `query_glass` in the `query_row`.
Best Case: O(query_row), as we only need to process up to the queried row.
Average Case: O(query_row), which is linear in terms of the number of rows up to the queried row.
Worst Case: O(query_row), since we must process all glasses in each row up to the queried row.
Description: The time complexity is linear with respect to the number of rows, as we process each row once.
Best Case: O(query_row), since we need space for each row's glasses.
Worst Case: O(query_row), as we need to store the glasses for each row.
Description: The space complexity is linear, as we need space to store the glasses for each row up to the queried row.
