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.
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 <= 1050 <= nums[i] < nums.lengthProblem 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.
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.
Time Complexity: O(n^2), where n is the length of the array. Space Complexity: O(1).
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.
Time Complexity: O(n), where n is the length of the array. Space Complexity: O(n), used for the 'change' array.
| 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 | — |
| 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 |
798. Smallest Rotation with Highest Score (Leetcode Hard) • Programming Live with Larry • 842 views views
Watch 6 more video solutions →Practice Smallest Rotation with Highest Score with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor