Watch 7 video solutions for Smallest Rotation with Highest Score, a hard level problem involving Array, Prefix Sum. This walkthrough by Programming Live with Larry has 842 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |