Smallest Rotation with Highest Score - Solution & Explanation
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 worth3points 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.
Constraints:
1 <= nums.length <= 1050 <= nums[i] < nums.length
Approach Overview
Problem Overview: You are given an array nums. For every rotation k, the array shifts left by k positions. A position scores a point if the value at that index is less than or equal to the index after rotation. The task is to find the rotation k that produces the maximum score. If multiple rotations produce the same score, return the smallest k.
Approach 1: Brute Force Simulation (O(n²) time, O(1) space)
The direct method is to simulate every possible rotation from 0 to n-1. For each rotation, compute where each element ends up and check whether nums[i] ≤ newIndex. This requires iterating through the entire array for every rotation and counting how many positions satisfy the scoring condition. The maximum score and corresponding rotation are tracked during the process. While simple to implement, this approach performs n checks for each of the n rotations, giving O(n²) time complexity. It is mainly useful for understanding the scoring behavior before optimizing.
Approach 2: Circular Shift Difference Array (O(n) time, O(n) space)
The optimized approach avoids recomputing the score for every rotation. Instead, determine for which rotations each element contributes a point. For an element nums[i], calculate the rotation interval where it becomes valid after shifting. Each element contributes +1 score for a continuous range of rotations. This allows you to treat the problem as a range update problem using a difference array. By marking where a score interval starts and ends, you accumulate contributions from all elements.
After processing all elements, compute a prefix sum over the difference array to obtain the total score for every rotation. The rotation with the highest accumulated score is the answer. This transformation converts repeated scoring checks into simple range updates and a single prefix scan. The algorithm runs in O(n) time and uses O(n) auxiliary space for the difference array.
This technique relies heavily on understanding cyclic index movement and range contribution tracking. If you want to strengthen the fundamentals behind this solution, review concepts such as array manipulation and prefix sum, which frequently appear in rotation and interval problems.
Recommended for interviews: The circular difference array solution is the expected answer because it reduces the problem from quadratic to linear time. Interviewers often want to see the reasoning that converts element scoring into rotation intervals. Explaining the brute force approach first shows understanding of the scoring rule, while deriving the prefix-sum based optimization demonstrates strong algorithmic insight.
Approach 1: Brute Force Approach
In this approach, we simulate rotating the array for each possible k (0 to n-1) and calculate the score for each rotation. We keep track of the maximum score and the corresponding k.
This C program iterates over all possible rotations and calculates the score for each one, keeping the maximum score and its corresponding index.
Complexity
Time Complexity: O(n^2), where n is the length of the array. Space Complexity: O(1).
Approach 2: Optimized Circular Shift Difference
This approach utilizes an optimized method. It calculates a score difference array to avoid recomputing scores from scratch for every rotation. By maintaining a running tally of scores, it adjusts the scores based on how the indices shift as the array is rotated.
This solution leverages an array 'change' to track score changes over rotations, only modifying the score based on differences from one rotation to the next without recalculating entire scores.
Complexity
Time Complexity: O(n), where n is the length of the array. Space Complexity: O(n), used for the 'change' array.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2), where n is the length of the array. Space Complexity: O(1). |
| Optimized Circular Shift Difference | Time Complexity: O(n), where n is the length of the array. Space Complexity: O(n), used for the 'change' array. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n²) | O(1) | Useful for understanding the scoring rule or validating correctness for small inputs |
| Circular Shift Difference Array | O(n) | O(n) | Best for large arrays and interview settings where optimal linear-time solutions are expected |
Video Solution
【每日一题】798. Smallest Rotation with Highest Score, 6/1/2021 • Huifeng Guan • 1,541 views views
Watch 4 more video solutions →Frequently Asked Questions
Is Smallest Rotation with Highest Score easy or hard?
Smallest Rotation with Highest Score Python/Java solution
How to solve Smallest Rotation with Highest Score in O(n)?
What is the best approach for Smallest Rotation with Highest Score?
Is Smallest Rotation with Highest Score asked at Google/Amazon/Meta?
What data structure is used in Smallest Rotation with Highest Score?
What is the time complexity of Smallest Rotation with Highest Score?
Ready to solve this problem?
Practice Smallest Rotation with Highest Score with our built-in code editor and test cases.
Practice on FleetCode