24.09.2023
799. Champagne Tower medium
blog post
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 contribute0.0
to the next row. This can be written asmax(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)
}