Hex.*

LC798 - Smallest Rotation With Highest Score

Posted on In
Leetcode: 125/2658 (52+59+14)

Discription

You are given an array nums. You can rotate it by a non-negative integer k so that the array becomes [nums[k], nums[k + 1], … nums[nums.length - 1], nums[0], nums[1], …, nums[k-1]]. Afterward, any entries that are less than or equal to their index are worth one point.

For example, if we have nums = [2,4,1,3,0], and we rotate by k = 2, it becomes [1,3,0,2,4]. This is worth 3 points because 1 > 0 [no points], 3 > 1 [no points], 0 <= 2 [one point], 2 <= 3 [one point], 4 <= 4 [one point].
Return the rotation index k that corresponds to the highest score we can achieve if we rotated nums by it. If there are multiple answers, return the smallest such index k.

Example 1:

Input: nums = [2,3,1,4,0]
Output: 3
Explanation: Scores for each k are listed below:
k = 0, nums = [2,3,1,4,0], score 2
k = 1, nums = [3,1,4,0,2], score 3
k = 2, nums = [1,4,0,2,3], score 3
k = 3, nums = [4,0,2,3,1], score 4
k = 4, nums = [0,2,3,1,4], score 3
So we should choose k = 3, which has the highest score.
Example 2:

Input: nums = [1,3,0,2,4]
Output: 0
Explanation: nums will always have 3 points no matter how it shifts.
So we will choose the smallest k, which is 0.

Constraints:

1 <= nums.length <= 105
0 <= nums[i] < nums.length

Solution

A number num, the final and coordinate difference is less than or equal to 0, there is only one range, that is, the coordinates are in [num, n-1]
, and the time difference between [0, num-1] will obviously be greater than 0.

1
2
3
4
5
6
7
8
9
10
Take nums=[2,3,1,4,0] as an example to illustrate
        i=0,nums[i]=2 To score, it needs to be adjusted to the 2~4 position, and it needs to be adjusted 1~3 steps
        i=1,nums[i]=3 To score, it needs to be adjusted to the 3~4 position, and it needs to be adjusted for 2~3 steps
        i=2,nums[i]=1 To score, you need to adjust to 1~4 position, you need to adjust 0~1 and 3~4 steps (3~1)
        i=3,nums[i]=4 To score, it needs to be adjusted to the 4~4 position, and it needs to be adjusted 4~4 steps
        i=4,nums[i]=0 To score, you need to adjust to 0~4 position, you need to adjust 0~4 steps
        To sum up, for each nums[i], the number of arguments k wants to make the upper and lower bounds of the number score: [(i+1)%n,(i+n-nums[i])%n]
        For i=2, nums[i]=1 is a special case, the upper and lower bounds 3 and 1 can also be calculated by the formula, and 0 and 4 need to be supplemented by themselves
        Finally, we count the range coverage of k corresponding to each nums[i], k represents the score in a certain coverage times, and the minimum value of k corresponding to the highest score (the most coverage times) is the answer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#O(n) time | O(n) space
class Solution:
    def bestRotation(self, nums: List[int]) -> int:
        diff = [0] * len(nums)
        for i, v in enumerate(nums):
            low = (i+1)% len(nums)
            high = (i - v + len(nums)+1)%len(nums)
            diff[low] +=1 # start 
            diff[high] -=1 # end+1 
            if low >= high:
                diff[0] +=1
        
        current = 0
        maxi = 0
        idx = 0
        for i, v in enumerate(diff):
            current += v
            if current>maxi:
                maxi = current
                idx = i
        return idx