The Mirror-Towers of Vashtel Escarpment
The Heliograph Wardens of Vashtel Escarpment keep a single line of mirror-towers along the cliff edge, running from west to east. When raiders come down from the high passes, the towers flash warnings to one another. Before the raiding season, the Wardens want a reckoning of how many towers each tower can flash to.
You are given heights, a list of positive integers. heights[i] is the height of the tower at index i, and the list runs from west to east.
A tower at index i can flash to a tower at index j exactly when both of these hold:
j > i, and- every tower strictly between them is strictly shorter than both tower
iand towerj.
Adjacent towers have nothing between them, so they can always flash to each other. Towers may share the same height.
Write signalReach(heights). It returns a list of integers with the same length as heights, where entry i is the number of towers east of tower i that tower i can flash to. If heights is empty, return an empty list.
The line may hold up to 100,000 towers.
examples
- case 1
heights of [10, 6, 8, 5, 11, 9][3, 1, 2, 1, 1, 0]. The 10 reaches the 6, the 8 and the 11, but the 5 is screened by the 8. - case 2
heights of [4, 2, 4, 4, 1][2, 1, 1, 1, 0]. The first 4 reaches the 2 and the second 4. The third 4 is hidden behind the second, which is not strictly shorter. - case 3
heights of [5, 5, 5, 5][1, 1, 1, 0]. Each tower reaches only its equal neighbour.
- reward
- 320 XP
- signature
signalReach
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- worked example
- empty line
- single tower
- equal heights hide farther ones
- all equal
- strictly rising
- strictly falling
- valley between giants
- alternating peaks