Tools: 🥂 Beginner-Friendly Guide 'Champagne Tower' - Problem 799 (C++, Python, JavaScript)

Problem Summary ## Intuition ## Walkthrough: Understanding the Examples ## Code Blocks ## Python ## JavaScript ## Key Takeaways ## Final Thoughts Imagine a wedding reception where a tower of champagne glasses is stacked in a pyramid. If you pour too much into the top glass, it beautifully overflows into the ones below, creating a cascading effect. This problem asks us to mathematically simulate that flow to determine exactly how much liquid ends up in a specific glass. The core logic revolves around overflow. A glass only starts sharing liquid with its neighbors once it has exceeded its capacity of 1 cup. When a glass at row i and position j overflows, the excess amount is split exactly in half. One half falls into the glass directly below it to the left at , and the other half falls into the glass below it to the right at . Instead of simulating every single drop, we can use a Dynamic Programming approach. We track the total amount of liquid that passes through each glass. By iterating row by row, we can calculate how much "excess" from the current row will contribute to the next row. Even if a glass receives 10 cups, we only care about the 9 cups of overflow it passes down. Example 2: poured = 2, query_row = 1, `query_glass = 1` Example 1: poured = 1, query_row = 1, `query_glass = 1` This problem is a fantastic introduction to how simple rules (like splitting overflow) can create complex distributions. In real-world software engineering, these types of "flow" algorithms are used in load balancing, where network traffic must be distributed across multiple servers, or in financial systems to calculate how tax or interest cascades through different account tiers. Mastering the ability to model a physical process with code is a core skill for any senior developer. Templates let you quickly answer FAQs or store snippets for re-use. Are you sure you want to hide this comment? It will become hidden in your post, but will still be visible via the comment's permalink. Hide child comments as well For further actions, you may consider blocking this person and/or reporting abuse COMMAND_BLOCK: class Solution { public: double champagneTower(int poured, int query_row, int query_glass) { // We use a DP array to store the amount of champagne in each glass of the current row vector<double> dp(query_row + 2, 0.0); dp[0] = (double)poured; for (int i = 0; i < query_row; i++) { // Iterate backwards to update the row in-place or use a temporary row for (int j = i; j >= 0; j--) { // Calculate overflow: (current amount - 1) divided by 2 double overflow = max(0.0, (dp[j] - 1.0) / 2.0); // The current glass only keeps 1.0 if it was full, but for // processing, we send the overflow to the next row's children dp[j + 1] += overflow; dp[j] = overflow; } } // The value in the glass cannot exceed 1.0 return min(1.0, dp[query_glass]); } }; Enter fullscreen mode Exit fullscreen mode COMMAND_BLOCK: class Solution { public: double champagneTower(int poured, int query_row, int query_glass) { // We use a DP array to store the amount of champagne in each glass of the current row vector<double> dp(query_row + 2, 0.0); dp[0] = (double)poured; for (int i = 0; i < query_row; i++) { // Iterate backwards to update the row in-place or use a temporary row for (int j = i; j >= 0; j--) { // Calculate overflow: (current amount - 1) divided by 2 double overflow = max(0.0, (dp[j] - 1.0) / 2.0); // The current glass only keeps 1.0 if it was full, but for // processing, we send the overflow to the next row's children dp[j + 1] += overflow; dp[j] = overflow; } } // The value in the glass cannot exceed 1.0 return min(1.0, dp[query_glass]); } }; COMMAND_BLOCK: class Solution { public: double champagneTower(int poured, int query_row, int query_glass) { // We use a DP array to store the amount of champagne in each glass of the current row vector<double> dp(query_row + 2, 0.0); dp[0] = (double)poured; for (int i = 0; i < query_row; i++) { // Iterate backwards to update the row in-place or use a temporary row for (int j = i; j >= 0; j--) { // Calculate overflow: (current amount - 1) divided by 2 double overflow = max(0.0, (dp[j] - 1.0) / 2.0); // The current glass only keeps 1.0 if it was full, but for // processing, we send the overflow to the next row's children dp[j + 1] += overflow; dp[j] = overflow; } } // The value in the glass cannot exceed 1.0 return min(1.0, dp[query_glass]); } }; COMMAND_BLOCK: class Solution: def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float: # Initialize DP array with the initial pour at the first glass dp = [0.0] * (query_row + 2) dp[0] = float(poured) for i in range(query_row): # We process from the end of the row to the start to update in-place for j in range(i, -1, -1): # Calculate the amount that overflows from the current glass overflow = max(0.0, (dp[j] - 1.0) / 2.0) # Split the overflow between the two glasses below dp[j + 1] += overflow dp[j] = overflow return min(1.0, dp[query_glass]) Enter fullscreen mode Exit fullscreen mode COMMAND_BLOCK: class Solution: def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float: # Initialize DP array with the initial pour at the first glass dp = [0.0] * (query_row + 2) dp[0] = float(poured) for i in range(query_row): # We process from the end of the row to the start to update in-place for j in range(i, -1, -1): # Calculate the amount that overflows from the current glass overflow = max(0.0, (dp[j] - 1.0) / 2.0) # Split the overflow between the two glasses below dp[j + 1] += overflow dp[j] = overflow return min(1.0, dp[query_glass]) COMMAND_BLOCK: class Solution: def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float: # Initialize DP array with the initial pour at the first glass dp = [0.0] * (query_row + 2) dp[0] = float(poured) for i in range(query_row): # We process from the end of the row to the start to update in-place for j in range(i, -1, -1): # Calculate the amount that overflows from the current glass overflow = max(0.0, (dp[j] - 1.0) / 2.0) # Split the overflow between the two glasses below dp[j + 1] += overflow dp[j] = overflow return min(1.0, dp[query_glass]) CODE_BLOCK: /** * @param {number} poured * @param {number} query_row * @param {number} query_glass * @return {number} */ var champagneTower = function(poured, query_row, query_glass) { // Create a DP array to track liquid flow through the rows let dp = new Array(query_row + 2).fill(0.0); dp[0] = poured; for (let i = 0; i < query_row; i++) { for (let j = i; j >= 0; j--) { // Determine how much spills over to the next level let overflow = Math.max(0, (dp[j] - 1) / 2); // Current glass contributes half its overflow to j and half to j+1 dp[j + 1] += overflow; dp[j] = overflow; } } return Math.min(1.0, dp[query_glass]); }; Enter fullscreen mode Exit fullscreen mode CODE_BLOCK: /** * @param {number} poured * @param {number} query_row * @param {number} query_glass * @return {number} */ var champagneTower = function(poured, query_row, query_glass) { // Create a DP array to track liquid flow through the rows let dp = new Array(query_row + 2).fill(0.0); dp[0] = poured; for (let i = 0; i < query_row; i++) { for (let j = i; j >= 0; j--) { // Determine how much spills over to the next level let overflow = Math.max(0, (dp[j] - 1) / 2); // Current glass contributes half its overflow to j and half to j+1 dp[j + 1] += overflow; dp[j] = overflow; } } return Math.min(1.0, dp[query_glass]); }; CODE_BLOCK: /** * @param {number} poured * @param {number} query_row * @param {number} query_glass * @return {number} */ var champagneTower = function(poured, query_row, query_glass) { // Create a DP array to track liquid flow through the rows let dp = new Array(query_row + 2).fill(0.0); dp[0] = poured; for (let i = 0; i < query_row; i++) { for (let j = i; j >= 0; j--) { // Determine how much spills over to the next level let overflow = Math.max(0, (dp[j] - 1) / 2); // Current glass contributes half its overflow to j and half to j+1 dp[j + 1] += overflow; dp[j] = overflow; } } return Math.min(1.0, dp[query_glass]); }; - An integer poured, representing the total number of cups of champagne poured into the top glass. - Two integers, query_row and query_glass, which act as the coordinates for the specific glass we are checking. - Return a decimal value representing how full that specific glass is. A glass can hold a maximum of 1 cup, so any value returned will be between 0 and 1. - Row 0: We pour 2 cups into the top glass (0, 0). - Overflow Calculation: The top glass holds 1 cup and has 1 cup of excess (). - Distribution: The 1 cup of excess is split. 0.5 cups go to glass (1, 0) and 0.5 cups go to glass (1, 1). - Result: Glass (1, 1) contains 0.5 cups. - Row 0: We pour 1 cup into the top glass. - Overflow Calculation: The glass is full, but there is 0 excess (). - Result: No liquid falls to the second row. Glass (1, 1) is empty (0.0). - Simulation via DP: Problems involving flow or cascades are often best solved by simulating the state of one "level" and using it to calculate the next. - Space Optimization: Instead of a 2D grid of , we used a 1D array to save memory, updating it iteratively for each row. - Boundary Handling: Understanding that a glass at index overflows into and of the next row is the "Aha!" moment for this problem.