The Sea-Stacks of Morrowgull Bay
The Corsair-Breakers of Morrowgull Bay are a band of grapple-leapers. They hold a chain of sea-stacks, the tall rock pillars that run in a single straight line from the shore out into open water. Each breaker keeps watch from one stack. When the horn sounds, every breaker leaps seaward to the nearest stack further out that is strictly taller than their own. The Harbour Warden has posted this contract to chart those leaps before the next raid.
Input. heights is a list of non-negative integers. heights[i] is the height of the i-th stack, counted from the shore outward, so index 0 is nearest the shore. The list may be empty.
Output. Write leapDistances(heights). It returns a list of integers with the same length as heights. For each index i:
- find the smallest index
j > iwithheights[j] > heights[i], and putj - iat positioni; - if no such
jexists, put0at positioni.
A stack of equal height does not count, because the target must be strictly taller. For an empty list, return an empty list.
examples
- case 1
heights of [3, 1, 4, 1, 5, 9, 2, 6][2, 1, 2, 1, 1, 0, 1, 0]. The stack of 3 leaps 2 stacks out to the 4, and the 9 has nothing taller seaward of it. - case 2
heights of [2, 2, 3][2, 1, 0]. The first 2 skips its equal neighbour and leaps to the 3. - case 3
heights of [7][0] - case 4
heights of [][]
- reward
- 320 XP
- signature
leapDistances
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- mixed chain
- equal heights do not count
- all equal
- empty chain
- single stack
- strictly descending
- strictly ascending
- one tall stack resolves many
- zeros then rise
- zigzag