LeetCode Entry

799. Champagne Tower

24.09.2023 medium 2023 kotlin

Positional flow value in a Pascal's Triangle

799. Champagne Tower medium blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/349

Problem TLDR

Positional flow value in a Pascal’s Triangle

Intuition

Let’s treat every glass value as the total flow passed through it. Otherwise, it is a standard Pascal’s Triangle problem: reuse the previous row to compute the next.

Approach

  • if flow is less than 1.0 (full), it will contribute 0.0 to the next row. This can be written as max(0, x - 1)
  • careful with a champagne, it will beat you in a head

Complexity

  • Time complexity: \(O(n^2)\)

  • Space complexity: \(O(n)\)

Code


    fun champagneTower(poured: Int, query_row: Int, query_glass: Int): Double {
      var flow = listOf(poured.toDouble())
      repeat(query_row) {
        val middle = flow.windowed(2).map { (a, b) ->
          max(0.0, a - 1.0) / 2 + max(0.0, b - 1.0) / 2
        }
        val edge = listOf(maxOf(0.0, flow.first() - 1.0) / 2)
        flow = edge + middle + edge
      }
      return minOf(flow[query_glass], 1.0)
    }