All problems

Taller Horse Around the Carousel

Medium · monotonic-stack

A carousel has painted horses fixed in a circle. You are given a list heights where heights[i] is the height of horse i, listed in clockwise order. After the last horse, the circle continues with horse 0.

A rider on any horse looks clockwise, one horse at a time, for the first horse that is strictly taller than their own. Looking can go all the way round the circle, but never past the rider's own horse.

Return a list of the same length where entry i is the number of steps clockwise from horse i to that taller horse (the next horse is 1 step away). If no horse in the circle is taller, the entry is -1.

Examples

Example 1

Input: heights = [3, 1, 2]

Output: [-1, 1, 1]

Horse 0 is the tallest, so it never finds a taller one. Horse 1 (height 1) finds the 2 one step on. Horse 2 (height 2) wraps round to the 3, one step on.

Example 2

Input: heights = [2, 5, 1, 3, 2]

Output: [1, -1, 1, 3, 2]

Horse 3 (height 3) passes the 2 and wraps past the other 2 before reaching the 5, which is 3 steps on. Horse 4 (height 2) needs to go past the equal-height horse 0 to reach the 5, 2 steps on.

Example 3

Input: heights = [4, 4]

Output: [-1, -1]

Equal heights are not taller.

Constraints