Link: https://leetcode.com/problems/champagne-tower/
Solution:
Topics: simulation
Intuition
The idea here is to create a model of this tower and pour the excess at each cup down a level (except at the final level), and then return the value at tower[query_row][query_col]
. There are two edge cases to watch out for.
- The value in a cup can never go negative.
- The value in a cup can never be greater than one.
Note that this is NOT a tree, its the diagonal of a matrix…levels don’t double, they increment by one. Similar to the matrix traversal we do for transposing (see Rotate image)
Implementation
Visual