The Petrified Watch of Dunmarrow Vale
Long ago a company of stone giants marched into Dunmarrow Vale and was turned to rock where it stood, in a single file running from west to east. The Lamplighters' Guild of Bitwick means to string signal-fires along the ridge. Before it does, it posts this commission: chart which giants each one could see if it looked east.
You are given heights, a list of positive integers. heights[0] is the westernmost giant and the last element is the easternmost. Neighbouring giants stand one place apart.
The giant at index i sees the giant at index j exactly when both of these hold:
j > i- every giant standing strictly between them has a height strictly less than the smaller of
heights[i]andheights[j].
This means a giant always sees its immediate eastern neighbour. A giant in between whose height equals that smaller height blocks the view.
Write giantSight(heights). It returns a list of integers the same length as heights, where element i is the number of giants that the giant at index i sees. If heights is empty, return an empty list.
examples
- case 1
heights of [10, 6, 8, 5, 11, 9][3, 1, 2, 1, 1, 0]. The 10 sees the 6, the 8 and the 11. It does not see the 5, because the 8 stands in the way, and it does not see the 9, because the 11 stands in the way. - case 2
heights of [4, 4, 4][1, 1, 0]. The first giant sees its neighbour, but that neighbour is not shorter than 4, so the third giant is hidden from the first. - case 3
heights of [] (an empty vale)[]
- reward
- 320 XP
- signature
giantSight
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- guild_survey_example
- empty_vale
- lone_giant
- equal_heights_block
- alternating_tall_and_short
- strictly_shrinking
- strictly_growing
- mixed_with_repeats
- twin_at_the_west