Champagne Tower - Practice Coding Problems

Champagne Tower - Problem

Dynamic Programming Medium

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 of champagne.

Then, some champagne is poured into the first glass at the top. When the topmost glass is full, any excess liquid poured will fall equally to the glass immediately to the left and right of it. When those glasses become full, any excess champagne will fall equally to the left and right of those glasses, and so on.

For example, after one cup of champagne is poured, the topmost glass is full. After two cups of champagne are poured, the two glasses on the second row are half full. After three cups of champagne are poured, those two cups become full - there are 3 full glasses total now.

Now after pouring some non-negative integer cups of champagne, return how full the jth glass in the ith row is (both i and j are 0-indexed).

Input & Output

Example 1 — Two Cups Poured

$ Input: poured = 2, query_row = 1, query_glass = 1

› Output: 0.5

💡 Note: Pour 2 cups into top glass: glass[0][0] gets 1.0 (full), remaining 1.0 overflows equally to row 1. Each glass in row 1 gets 0.5.

Example 2 — One Cup Only

$ Input: poured = 1, query_row = 1, query_glass = 1

› Output: 0.0

💡 Note: Only 1 cup poured fills the top glass completely. No overflow reaches row 1, so glass[1][1] remains empty.

Example 3 — Large Pour

$ Input: poured = 100000009, query_row = 33, query_glass = 17

› Output: 1.0

💡 Note: With 100 million cups, champagne fills many levels completely. Glass at row 33, position 17 will be completely full.

Constraints

0 ≤ poured ≤ 10⁹
0 ≤ query_glass ≤ query_row < 100

Visualization

Tap to expand

Understanding the Visualization

Input

2 cups poured, query glass at row 1, position 1

Process

Pour into top glass, overflow splits equally to row below

Output

Target glass contains 0.5 cups

Key Takeaway

🎯 Key Insight: Simulate the overflow process level by level, where each glass overflow splits equally between two glasses below

Asked in

G Google 12 f Facebook 8 M Microsoft 6

The key insight is to simulate the champagne pouring process level by level, where overflow from each glass splits equally between the two glasses directly below it. The simulation approach creates a 2D tower array and processes overflow row by row until reaching the target. Best approach is the space-optimized version that only tracks current and next rows. Time: O(n²), Space: O(n) for optimized version.

Common Approaches

Approach	Time	Space	Notes
✓ Simulation Approach	O(n²)	O(n²)	Simulate the pouring process row by row, tracking overflow
Optimized Row Processing	O(n²)	O(n)	Process only two rows at a time to reduce space complexity

Simulation Approach — Algorithm Steps

Create 2D array for the tower up to query_row
Pour all champagne into top glass (0,0)
For each row, calculate overflow and distribute to glasses below
Return the amount in the target glass

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Create tower array and pour all champagne into top glass

Overflow

Process each row, distributing overflow equally to glasses below

Result

Return the amount in target glass (capped at 1.0)

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

double solution(int poured, int query_row, int query_glass) {
    // Allocate tower array - each row i has i+1 glasses
    double** tower = (double**)malloc((query_row + 1) * sizeof(double*));
    for (int i = 0; i <= query_row; i++) {
        tower[i] = (double*)calloc(i + 1, sizeof(double));
    }
    
    // Pour all champagne into the top glass
    tower[0][0] = poured;
    
    // Simulate the overflow process row by row
    for (int row = 0; row < query_row; row++) {
        for (int glass = 0; glass <= row; glass++) {
            // If current glass has more than 1 cup, it overflows
            if (tower[row][glass] > 1.0) {
                double overflow = tower[row][glass] - 1.0;
                tower[row][glass] = 1.0;  // Current glass becomes full
                
                // Distribute overflow equally to two glasses below
                tower[row + 1][glass] += overflow / 2.0;
                tower[row + 1][glass + 1] += overflow / 2.0;
            }
        }
    }
    
    // Get result and free memory
    double result = fmin(1.0, tower[query_row][query_glass]);
    
    for (int i = 0; i <= query_row; i++) {
        free(tower[i]);
    }
    free(tower);
    
    return result;
}

int main() {
    int poured, query_row, query_glass;
    scanf("%d", &poured);
    scanf("%d", &query_row);
    scanf("%d", &query_glass);
    
    double result = solution(poured, query_row, query_glass);
    printf("%f\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

We process each glass in rows 0 to query_row, which is roughly query_row² glasses total

⚠ Quadratic Growth

Space Complexity

O(n²)

We store a 2D array with query_row rows, requiring query_row² space

⚠ Quadratic Space

125.0K Views

Medium Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Simulation Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler