Last updated on January 29th, 2025 at 02:16 am
Here, we see the Smallest Rotation with Highest Score LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Array, Math
Level of Question
Hard

Smallest Rotation with Highest Score LeetCode Solution
Table of Contents
1. Problem Statement
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 byk = 2
, it becomes[1,3,0,2,4]
. This is worth3
points because1 > 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.
2. Coding Pattern Used in Solution
The coding pattern used in this problem is “Prefix Sum with Range Updates”. This pattern involves using an auxiliary array to efficiently calculate the effect of range updates and then iterating over the array to determine the optimal result.
3. Code Implementation in Different Languages
3.1 Smallest Rotation with Highest Score C++
class Solution { public: int bestRotation(vector<int>& nums) { const int N = nums.size(); vector<int> tmp(N+1, 0); for (int i(0); i < N; ++i) { if (nums[i] <= i) { tmp[0] += 1; tmp[i-nums[i]+1] -= 1; tmp[i+1] += 1; tmp[N] -= 1; } else { tmp[i+1] += 1; tmp[N-nums[i]+i+1] -= 1; } } int maxc = INT_MIN; int maxK = -1; int cur = 0; for (int i(0); i < N; ++i) { cur += tmp[i]; if (cur > maxc) { maxc = cur; maxK = i; } } return maxK; } };
3.2 Smallest Rotation with Highest Score Java
class Solution { public int bestRotation(int[] nums) { final int size = nums.length; int[] rsc = new int[size]; for(int i = 0; i < size - 1; i++) { int value = nums[i]; int downPos = (i + 1 + size - value) % size; rsc[downPos]--; } int value = nums[size-1]; if( value != 0 ) rsc[size - value]--; int bestk = 0; int bestscore = rsc[0]; int score = rsc[0]; for(int i = 1; i < nums.length; i++) { score += rsc[i] + 1; if( score > bestscore ) { bestk = i; bestscore = score; } } return bestk; } }
3.3 Smallest Rotation with Highest Score JavaScript
var bestRotation = function (nums) { let acc = new Uint32Array(100001); let n = nums.length; acc.fill(0, 0, n + 1); for (let i = 0; i < n; ++i) { ++acc[Math.min(i + 1, Math.max(0, i - nums[i] + 1))]; } let bestInd = 0; let bestCnt = n - acc[0]; let currCnt = bestCnt; for (let i = 1; i < n; ++i) { currCnt -= acc[i]; if (nums[i - 1] < n) { ++currCnt; let exp = i + n - nums[i - 1]; if (exp < n) ++acc[exp]; } if (currCnt > bestCnt) { bestCnt = currCnt; bestInd = i; } } return bestInd; };
3.4 Smallest Rotation with Highest Score Python
class Solution(object): def bestRotation(self, nums): n = len(nums) change = [1] * n for i, num in enumerate(nums): change[(i - num + 1) % n] -= 1 for i in range(1, n): change[i] += change[i - 1] return change.index(max(change))
4. Time and Space Complexity
Time Complexity | Space Complexity | |
C++ | O(n) | O(n) |
Java | O(n) | O(n) |
JavaScript | O(n) | O(n) |
Python | O(n) | O(n) |
- The problem uses the Prefix Sum with Range Updates pattern to efficiently calculate the optimal rotation.
- The time complexity is O(n) because the operations involve iterating through the array and calculating the prefix sum.
- The space complexity is O(n) due to the use of an auxiliary array for range updates.