The Stone-Giant Muster of Kolvaren Fells
On the high moor of Kolvaren Fells, a column of stone giants stands in single file, running west to east, frozen mid-stride since the last age. The Fellwardens' Guild expects the spring thaw to wake them. When they wake, each giant will open its eyes and look east along the column. The Guild has posted a bounty for a full reckoning of how many of its kin each giant will see.
You are given heights, a list of positive integers. heights[i] is the height of the i-th giant, counting from the west end (index 0 is the westernmost giant).
The sight rule is as follows:
- Giants look only east, toward higher indices.
- Giant
ican see giantj, wherej > i, exactly when every giant standing strictly between them is strictly shorter than both giantiand giantj. - Neighbouring giants always see each other, because no one stands between them.
- Heights may repeat. A giant in between whose height is equal to either endpoint's height blocks the view.
Write visibleKin(heights). It returns a list of integers with the same length as heights, where entry i is the number of giants that giant i can see. An empty column returns an empty list.
The column may hold up to 100,000 giants.
examples
- case 1
heights = [10, 6, 8, 5, 11, 9][3, 1, 2, 1, 1, 0]. The first giant (10) sees 6, then 8 over the shorter 6, then 11 over everyone between; nothing lies beyond the 11 for it. - case 2
heights = [3, 1, 3, 2, 3][2, 1, 2, 1, 0]. Giant 0 sees the 1 and the 3 behind it, but that equal 3 blocks the 2 and the last 3. - case 3
heights = [5, 5, 5][1, 1, 0]. Each giant sees only its neighbour, because an equal-height giant blocks the view. - case 4
heights = [7][0]. A lone giant sees no one.
- reward
- 320 XP
- signature
visibleKin
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- bounty_example
- all_equal_heights
- equal_endpoints_see_over_valley
- equal_short_pair_blocks
- empty_column
- single_giant
- strictly_increasing
- strictly_decreasing
- tall_giant_over_rising_slope
- mixed_with_repeats