Problem Description

You have a pyramid of champagne glasses where row 1 has 1 glass, row 2 has 2 glasses, row 3 has 3 glasses, and so on. Each glass can hold exactly 1 cup of champagne.

When you pour champagne into the top glass, the following happens:

• If a glass receives more than 1 cup, it keeps 1 cup and the excess overflows
• The overflow splits equally between the two glasses directly below it (to the left-below and right-below)
• This cascading continues down the pyramid
• Any overflow from the bottom row spills onto the floor

For example, if you pour:

• 1 cup: The top glass becomes full
• 2 cups: The top glass is full, and each glass in row 2 gets 0.5 cups (half full)
• 3 cups: The top glass and both glasses in row 2 are full
• 4 cups: Row 1 and 2 are full, the middle glass of row 3 gets 0.5 cups, and the outer glasses of row 3 each get 0.25 cups

Given:

• poured: The total number of cups poured into the top glass
• query_row: The row index (0-indexed) of the glass you want to check
• query_glass: The glass index within that row (0-indexed) you want to check

Return the amount of champagne in the specified glass (between 0 and 1).

The solution uses dynamic programming to simulate the pouring process. It creates a 2D array f where f[i][j] represents the amount of champagne that flows through glass at row i, position j. For each glass that receives more than 1 cup, it keeps 1 cup and distributes the excess equally to the two glasses below it. The final answer is the amount in the queried glass, capped at 1.

Intuition

The key insight is to simulate the actual pouring process layer by layer. Think of it like water flowing down a pyramid - we need to track how much liquid flows through each glass, not just what remains in it.

Initially, we might think to track only the final amount in each glass, but this doesn't give us enough information. When a glass overflows, we need to know exactly how much overflow there is to distribute to the glasses below. This leads us to track the total amount that "flows through" each glass.

For each glass at position (i, j):

• It receives champagne from up to two glasses above it: (i-1, j-1) and (i-1, j)
• If it receives more than 1 cup total, it keeps exactly 1 cup
• Any excess beyond 1 cup overflows and splits equally between its two children

This naturally suggests a top-down approach: start from the top glass where we pour all the champagne, then process each row to determine the overflow that reaches the next row. We use a 2D array where f[i][j] initially represents the total amount flowing through glass (i, j).

The simulation works as follows:

1. Pour all champagne into the top glass: f[0][0] = poured
2. For each glass that has more than 1 cup, calculate the overflow: overflow = f[i][j] - 1
3. Split this overflow equally: each glass below gets overflow / 2
4. Cap the current glass at 1 cup: f[i][j] = 1

We only need to process rows up to query_row since we're only interested in one specific glass. After simulation, f[query_row][query_glass] contains our answer - it will be at most 1 (full glass) or some fraction if partially filled.

Learn more about Dynamic Programming patterns.

Solution Approach

We implement a simulation using a 2D array to track the champagne flow through each glass.

Data Structure:

• Create a 2D array f of size 101×101 (sufficient for up to 100 rows)
• f[i][j] represents the amount of champagne that flows through the glass at row i, position j

Algorithm Steps:

1. Initialize the top glass:

   f[0][0] = poured

   All champagne starts at the topmost glass.

2. Simulate the cascade process:

   for i in range(query_row + 1):
       for j in range(i + 1):

   • Process each row from top to bottom, up to query_row
   • In row i, there are i + 1 glasses (row 0 has 1 glass, row 1 has 2 glasses, etc.)

3. Handle overflow for each glass:

   if f[i][j] > 1:
       half = (f[i][j] - 1) / 2
       f[i][j] = 1
       f[i + 1][j] += half
       f[i + 1][j + 1] += half

   • If a glass has more than 1 cup (f[i][j] > 1):
     • Calculate the overflow: f[i][j] - 1
     • Split the overflow equally: half = (f[i][j] - 1) / 2
     • Cap the current glass at 1: f[i][j] = 1
     • Add the overflow to the two glasses below:
       • Left child: f[i + 1][j]
       • Right child: f[i + 1][j + 1]

4. Return the result:

   return f[query_row][query_glass]

   After simulation, the value at the queried position is the answer.

Time Complexity: O(R²) where R = query_row + 1, as we process each glass in rows 0 through query_row.

Space Complexity: O(1) if we consider the array size fixed at 101×101, or O(R²) if we optimize the array size based on input.

The beauty of this solution is that it directly models the physical process - we literally simulate pouring champagne and tracking how it flows down the pyramid, making the solution intuitive and easy to verify.

Example Walkthrough

Let's trace through the algorithm with poured = 4 cups and we want to find the amount in glass at query_row = 2, query_glass = 1 (the middle glass of row 3).

Initial Setup:

f[0][0] = 4  (pour all 4 cups into top glass)
All other positions = 0

Row 0 Processing:

• Glass (0,0): Has 4 cups (> 1)
  • Overflow = 4 - 1 = 3 cups
  • Keep 1 cup: f[0][0] = 1
  • Split overflow: 3/2 = 1.5 cups each
  • f[1][0] += 1.5 → f[1][0] = 1.5
  • f[1][1] += 1.5 → f[1][1] = 1.5

State after Row 0:

      1
   1.5  1.5
  0   0   0

Row 1 Processing:

• Glass (1,0): Has 1.5 cups (> 1)

  • Overflow = 1.5 - 1 = 0.5 cups
  • Keep 1 cup: f[1][0] = 1
  • Split overflow: 0.5/2 = 0.25 cups each
  • f[2][0] += 0.25 → f[2][0] = 0.25
  • f[2][1] += 0.25 → f[2][1] = 0.25

• Glass (1,1): Has 1.5 cups (> 1)

  • Overflow = 1.5 - 1 = 0.5 cups
  • Keep 1 cup: f[1][1] = 1
  • Split overflow: 0.5/2 = 0.25 cups each
  • f[2][1] += 0.25 → f[2][1] = 0.5 (now has 0.25 + 0.25)
  • f[2][2] += 0.25 → f[2][2] = 0.25

State after Row 1:

        1
     1     1
  0.25  0.5  0.25

Row 2 Processing:

• Glass (2,0): Has 0.25 cups (≤ 1) - No overflow, stays at 0.25
• Glass (2,1): Has 0.5 cups (≤ 1) - No overflow, stays at 0.5
• Glass (2,2): Has 0.25 cups (≤ 1) - No overflow, stays at 0.25

Final Answer: f[2][1] = 0.5

The middle glass of row 3 contains 0.5 cups of champagne.

Solution Implementation

Time and Space Complexity

Time Complexity: O(query_row²) or O(n²) where n = query_row

The algorithm uses nested loops where:

• The outer loop runs from i = 0 to i = query_row (inclusive), giving us query_row + 1 iterations
• The inner loop runs from j = 0 to j = i (inclusive), giving us i + 1 iterations for each value of i

The total number of operations is: 1 + 2 + 3 + ... + (query_row + 1) = (query_row + 1) × (query_row + 2) / 2

This simplifies to O(query_row²) time complexity.

Space Complexity: O(1) or O(10,201)

The algorithm allocates a fixed 2D array f of size 101 × 101 = 10,201 elements, regardless of the input values. Since this is a constant amount of space that doesn't scale with the input parameters, the space complexity is O(1).

However, if we consider the absolute space used rather than asymptotic complexity, we could also express this as O(101²) or O(10,201), which still reduces to O(1) since it's constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Capping the Final Result

The most common mistake is forgetting that each glass can only hold a maximum of 1 cup, even though during simulation a glass might temporarily hold more than 1 cup before overflow distribution.

Incorrect:

return tower[query_row][query_glass]  # Wrong! Could return values > 1

Correct:

return min(1.0, tower[query_row][query_glass])  # Ensures result is between 0 and 1

2. Processing Rows Beyond What's Necessary

Processing all 101 rows when you only need to reach query_row wastes computation and can cause index out of bounds errors when distributing overflow.

Incorrect:

for row in range(101):  # Processes unnecessary rows
    for col in range(row + 1):
        if tower[row][col] > 1.0:
            # This will cause index error when row = 100
            tower[row + 1][col] += overflow / 2.0

Correct:

for row in range(query_row + 1):  # Only process up to query_row
    for col in range(row + 1):
        # Safe to access row + 1 since we stop at query_row

3. Incorrect Overflow Calculation

Mixing up the order of operations when handling overflow - you must calculate overflow before capping the current glass.

Incorrect:

if tower[row][col] > 1.0:
    tower[row][col] = 1.0  # Cap first (wrong!)
    overflow = tower[row][col] - 1.0  # This will always be 0
    # No overflow gets distributed!

Correct:

if tower[row][col] > 1.0:
    overflow = tower[row][col] - 1.0  # Calculate overflow first
    tower[row][col] = 1.0  # Then cap the glass
    # Now distribute the overflow

4. Using Integer Division Instead of Float Division

In Python 2 or when using integer types, division might truncate to integers, causing incorrect overflow distribution.

Incorrect:

tower[row + 1][col] += (tower[row][col] - 1) // 2  # Integer division loses precision

Correct:

tower[row + 1][col] += (tower[row][col] - 1.0) / 2.0  # Float division preserves decimals

5. Off-by-One Errors in Loop Bounds

Remember that row i has i + 1 glasses (row 0 has 1 glass, row 1 has 2 glasses, etc.).

Incorrect:

for col in range(row):  # Missing the last glass in each row

Correct:

for col in range(row + 1):  # Correctly iterates through all glasses in the row