A relay network is laid out as a binary tree rooted at the base station. Each tower has an integer height. A tower is visible if, along the unique path from the base station down to that tower, no earlier tower on the path is strictly taller than it. Equivalently, a tower is visible when its height is greater than or equal to the maximum height among its ancestors. The base station itself is always visible.
Report how many towers are visible.
Line 1: an integer k, the number of tokens on line 2.
Line 2: k space-separated tokens giving the tree in level order. The first token is the root; each subsequent token is an integer height or null for a missing child. Children of null nodes are omitted.
A single integer: the number of visible towers.
Example 1
Input
7 3 1 4 3 null 1 5
Expected
4
Explanation
Visible: root 3; node 4 (>= 3); the 3 under node 1 (its ancestors are 3 and 1, max 3, and 3 >= 3); and 5 (>= 4). The two 1's are each blocked by a taller ancestor. Total 4.
Example 2
Input
3 2 null 3
Expected
2
Explanation
The base station (2) is visible, and 3 >= 2 so it is visible too. Total 2.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →