Smallest Rotation With Highest Score Problem


Description

LeetCode Problem 798.

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:

1
2
3
4
5
6
7
8
9
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:

1
2
3
4
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 <= 10^5
  • 0 <= nums[i] < nums.length


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int bestRotation(vector<int>& nums) {
        int n = size(nums); 

        vector<int> diff(n, 1); 
        for (int i = 0; i < n; ++i) 
            diff[(i + n - nums[i] + 1) % n]--; 
        
        int ans = 0, prefix = 0, mx = INT_MIN; 
        for (int i = 0; i < n; ++i) {
            prefix += diff[i]; 
            if (prefix > mx) {
                mx = prefix; 
                ans = i; 
            }
        }

        return ans; 
    }
};




Related Posts

Walking Robot Simulation Problem

LeetCode 874. A robot on an infinite XY-plane starts at...

Valid Mountain Array Problem

LeetCode 941. Given an array of integers arr, return true...

Sum Of Even Numbers After Queries Problem

LeetCode 985. You are given an integer array nums and...

Partition Array Into Disjoint Intervals Problem

LeetCode 915. Given an integer array nums, partition it into...

Monotonic Array Problem

LeetCode 896. An array is monotonic if it is either...

Maximize Distance To Closest Person Problem

LeetCode 849. You are given an array representing a row...