798. Smallest Rotation with Highest Score LeetCode Solution
In this guide, you will get 798. Smallest Rotation with Highest Score LeetCode Solution with the best time and space complexity. The solution to Smallest Rotation with Highest Score problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Smallest Rotation with Highest Score solution in C++
- Smallest Rotation with Highest Score solution in Java
- Smallest Rotation with Highest Score solution in Python
- Additional Resources

Problem Statement of Smallest Rotation with Highest Score
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
Complexity Analysis
- Time Complexity: O(n)
- Space Complexity: O(1)
798. Smallest Rotation with Highest Score LeetCode Solution in C++
class Solution {
public:
int bestRotation(vector<int>& nums) {
const int n = nums.size();
// rotate[i] := the number of points lost after rotating left i times
vector<int> rotate(n);
// Rotating i - nums[i] times makes nums[i] == its new index.
// So, rotating i - nums[i] + 1 times will "start" to make nums[i] > its
// index, which is the starting index to lose point.
for (int i = 0; i < n; ++i)
--rotate[(i - nums[i] + 1 + n) % n];
// Each time of the rotation, make index 0 to index n - 1 to get 1 point.
for (int i = 1; i < n; ++i)
rotate[i] += rotate[i - 1] + 1;
return distance(rotate.begin(), ranges::max_element(rotate));
}
};
/* code provided by PROGIEZ */
798. Smallest Rotation with Highest Score LeetCode Solution in Java
class Solution {
public int bestRotation(int[] nums) {
final int n = nums.length;
// rotate[i] := the number of points lost after rotating left i times
int[] rotate = new int[n];
// Rotating i - nums[i] times makes nums[i] == its new index.
// So, rotating i - nums[i] + 1 times will "start" to make nums[i] > its
// index, which is the starting index to lose point.
for (int i = 0; i < n; ++i)
--rotate[(i - nums[i] + 1 + n) % n];
// Each time of the rotation, make index 0 to index n - 1 to get 1 point.
for (int i = 1; i < n; ++i)
rotate[i] += rotate[i - 1] + 1;
int mx = Integer.MIN_VnumsLUE;
int maxIndex = 0;
for (int i = 0; i < n; ++i)
if (rotate[i] > mx) {
mx = rotate[i];
maxIndex = i;
}
return maxIndex;
}
}
// code provided by PROGIEZ
798. Smallest Rotation with Highest Score LeetCode Solution in Python
N/A
# code by PROGIEZ
Additional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.