Problem Breakdown
We need to simulate the flow of champagne through a pyramid-shaped stack of glasses. The structure is defined such that row i contains i + 1 glasses (0-indexed). Liquid poured into (0, 0) overflows equally to its two children below: left child at (r+1, c-1) and right child at (r+1, c). Each glass has a capacity of exactly 1. Any amount exceeding 1 flows down; anything less or equal stays in the glass (capped at 1).
Inputs:
poured: Total volume poured into the top glass (int).query_row: The row index we are interested in (int, ).query_glass: The column index within that row ().
Output:
- A float representing the fill level of the specific glass, capped at
1.0.
Implicit Constraints & Edge Cases:
- Capacity Capping: We must never return a value . The “excess” calculation is only relevant if current amount .
- Boundary Conditions: Glasses on the left edge () or right edge of a row do not have children in those directions (e.g.,
(r+1, -1)doesn’t exist). We must handle these indices carefully. - Large Inputs:
pouredcan be up to . While this is large for volume, the number of glasses grows linearly with row index (), and we only care about propagation depth limited byquery_row. The complexity depends on rows processed, not poured amount. - Zero Pour: If
pouredis 0 or small enough to fill nothing beyond capacity, all queried values should be 0 (unless the top glass itself holds it).
Intuition
A brute-force simulation of pouring cup-by-cup would require iterating times if we treat each unit as a discrete event. Even simulating row by row with individual cups is inefficient ( where P is poured amount) because poured can be very large.
However, the flow logic is deterministic and additive. The state of any glass depends only on the excess from its parents above it. This suggests a Dynamic Programming (DP) or simulation approach based on volume propagation rather than discrete cups. Since we only need to know how much liquid reaches row query_row, we can propagate the total flow downwards layer by layer until we reach that depth.
Key Insight: Instead of tracking “how many full glasses,” track “total amount arriving at this glass.” If a glass receives units, and its capacity is 1:
- Stored value = (for the answer).
- Excess to pass down = .
We iterate through rows from top (0) up to query_row. For each glass in row , if it has excess liquid, we distribute half of that excess to its children in row . We stop processing once we reach the target row because flow beyond that doesn’t affect our answer.
Approach
-
Initialize Grid: Create a DP table (2D array) representing the champagne tower up to
query_row. Since constraints limit rows < 100, we can allocate space for roughly(query_row + 2)x(query_row + 2)or handle boundaries dynamically. A square matrix of size sufficient for max constraint is safe and simple ().- Initialize all cells to
0. - Set the top glass
(0, 0)topoured.
- Initialize all cells to
-
Propagate Flow: Iterate through rows from
0up toquery_row - 1. (We don’t need to propagate overflow FROM rowquery_row, only TO it).- For each column in current row:
- If the amount at
(r, c)is greater than1:- Calculate excess =
amount - 1. - Add
excess / 2to child left(r+1, c-1). - Add
excess / 2to child right(r+1, c).
- Calculate excess =
- If the amount at
- For each column in current row:
-
Retrieve Result: After propagation stops at the row above our target (or after processing all relevant rows), read the value from
dp[query_row][query_glass]. Cap it at1.0just in case logic didn’t cap during flow (though we should ensure storage reflects actual fill). -
Return: Return the capped float value.
Complexity Analysis
- Time Complexity: , where is
query_row. We iterate through every cell up to rowquery_row - 1and push flow down. Since max rows , this is roughly effectively (constant relative to input size constraints), but formally quadratic in terms of the query depth. - Space Complexity: . We store a grid proportional to the square of the row index. Given
query_row < 100, this is negligible memory usage ( floats).
Solution
class Solution:
def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
# Initialize DP table.
# We need enough rows to reach 'query_row'.
# Width needs to accommodate the max column index in that row (which is equal to row index).
# Using a fixed size slightly larger than constraints for safety and simplicity,
# or dynamic sizing based on query_row + 1. Let's use min(102) logic implicitly via loop bounds
# but allocate dynamically per row width i+2 to handle children indices safely without checks?
# Actually, standard approach: dp[r][c] where r goes up to query_row.
n = query_row + 1
# Create a grid with sufficient columns for the max index in any processed row.
# Row 'i' has glasses from col 0 to i. Children are at c-1 and c.
# To avoid boundary checks, we can pad or check bounds. Checking bounds is cleaner logic-wise.
dp = [[0] * (n + 2) for _ in range(n)]
# Pour into top glass
dp[0][0] = float(poured)
# Propagate flow row by row up to query_row - 1
# We don't need to process overflow FROM the target row itself.
for r in range(query_row):
for c in range(r + 2): # Iterate through valid glasses in current row (0..r)
if dp[r][c] > 1:
excess = dp[r][c] - 1
# Distribute to left child and right child below
# Left child is at r+1, c-1. Right child is at r+1, c.
# Add half overflow to children (if they exist within bounds)
if c > 0:
dp[r + 1][c - 1] += excess / 2
dp[r + 1][c] += excess / 2
return min(1.0, float(dp[query_row][query_glass]))
Edge Cases Handled
- Zero Pour (
poured = 0): The grid initializes to0. No overflow occurs. Returnsmin(1.0, 0), which is0.0. Correct. - Small Pour: If poured fills only top glass or partially second row, the logic correctly caps at
1.0and passes correct excess (or zero if full). - Boundary Columns (
query_glass = 0): The loop conditionif c > 0prevents accessing index-1. This handles left-edge glasses which only have a right child below them in the pyramid structure logic, or rather, they push to(r+1, -1)(invalid) and(r+1, 0). My code checksc > 0before pushing toc-1, effectively ignoring non-existent left children. - Large Pour (
poured = 1e9): Python handles large floats accurately enough for this problem’s tolerance (double precision). The logic caps values at1.0immediately upon storage, preventing overflow of the float variable itself beyond capacity limits.