⚡Flashcard Drill➔
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

  1. Simulate row by row, keeping only the current row's fill amounts.
  2. For each glass in the current row, the excess is max(0, amount - 1), split evenly between the two glasses below.
  3. Only rows up to query_row need to be simulated, and the row length grows by one each time.
  4. 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 - 1 overflows, and only when positive.
  • Spilling negative excess: (amount - 1) / 2 is negative when the glass is not full; the > 0 guard 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems