NeetCode #141LC-799MediumArrays & Hashing
← Back to All Problems#141 · #799 · Champagne Tower(香槟塔)
📌 Problem Statement & Constraints
Champagne is poured into the top glass of a tower. Each glass holds exactly 1 unit; excess spills equally into the two glasses below it. Given
poured, query_row and query_glass, return how full the queried glass is (capped at 1). Constraints: 0 <= poured <= 10^9, 0 <= query_glass <= query_row <= 99.💡 Core Algorithmic Approaches
- Simulate row by row, keeping only the current row's fill amounts.
- For each glass in the current row, the excess is
max(0, amount - 1), split evenly between the two glasses below. - Only rows up to
query_rowneed to be simulated, and the row length grows by one each time. - The answer is
min(1, fill[query_glass]), since a glass can hold at most 1 unit.
💻 Benchmark Python3 Implementation
class Solution:
def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
row = [float(poured)]
for _ in range(query_row):
nxt = [0.0] * (len(row) + 1)
for j, amount in enumerate(row):
overflow = (amount - 1) / 2
if overflow > 0: # only excess spills
nxt[j] += overflow
nxt[j + 1] += overflow
row = nxt
return min(1.0, row[query_glass])⚡ Complexity Deep Dive
⏱️ Time Complexity
O(query_row^2): the total number of simulated glasses is 1 + 2 + ... + query_row.
💾 Space Complexity
O(query_row) for the current row.
⚠️ Interview Pitfalls & Follow-ups
- Spilling the entire amount instead of the excess: only
amount - 1overflows, and only when positive. - Spilling negative excess:
(amount - 1) / 2is negative when the glass is not full; the> 0guard prevents negative champagne. - Forgetting to cap the result at 1: a glass cannot hold more than one unit.
- Using integers: the amounts are fractional; use floats.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.