Smallest Rotation with Highest Score

Hard

#0752Time: O(N^2), where N is the length of `nums`. The outer loop runs N times for each possible rotation `k`, and the inner loop also runs N times to calculate the score for that rotation.Space: O(1) extra space, as we only need a few variables to store the current state (scores and best k).

Patterns

Prefix Sum

Data structures

Array

Prompt

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 <= 10⁵
0 <= nums[i] < nums.length

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We test every possible rotation k from 0 to N-1. For each rotation, we calculate its score by iterating through the conceptually rotated array and counting how many elements A[i] satisfy the condition A[i] <= i. We maintain a variable to track the highest score seen so far and the corresponding rotation index k. Since we iterate k from 0 upwards and only update the result for strictly greater scores, we are guaranteed to find the smallest k in case of a tie.

Algorithm

Initialize maxScore to -1 and bestK to 0.
Iterate through each possible rotation index k from 0 to N-1, where N is the length of the array.
For each k, initialize a currentScore to 0.
Iterate through each index i from 0 to N-1 of the (conceptually) rotated array.
The element at index i in the array rotated by k is nums[(i + k) % N].
Check if this element's value is less than or equal to its new index: nums[(i + k) % N] <= i.
If the condition is true, increment currentScore.
After iterating through all i's, compare currentScore with maxScore.
If currentScore > maxScore, update maxScore = currentScore and bestK = k.
After the outer loop finishes, bestK will hold the smallest rotation index with the highest score. Return bestK.

Walkthrough

The brute-force method involves a straightforward simulation. We use two nested loops. The outer loop iterates through all possible rotation values k, from 0 to N-1. The inner loop calculates the score for that specific rotation k. To find the value at a new index i after rotating by k, we can map it back to the original array. An element at new index i was originally at index (i + k) % N. We check if nums[(i + k) % N] <= i. We sum up the points for a given k and compare it with the maximum score found so far. This process is repeated for all k, and the k that yields the highest score is the answer.

1class Solution {2    public int bestRotation(int[] nums) {3        int n = nums.length;4        int maxScore = -1;5        int bestK = 0;6 7        for (int k = 0; k < n; k++) {8            int currentScore = 0;9            for (int i = 0; i < n; i++) {10                // The original index of the element at new index i is (i + k) % n11                int originalIndex = (i + k) % n;12                if (nums[originalIndex] <= i) {13                    currentScore++;14                }15            }16            if (currentScore > maxScore) {17                maxScore = currentScore;18                bestK = k;19            }20        }21        return bestK;22    }23}

Complexity

Time

O(N^2), where N is the length of `nums`. The outer loop runs N times for each possible rotation `k`, and the inner loop also runs N times to calculate the score for that rotation.

Space

O(1) extra space, as we only need a few variables to store the current state (scores and best k).

Trade-offs

Pros

Simple to understand and implement.
Requires no extra space other than a few variables.

Cons

Highly inefficient due to its nested loops.
Will result in a 'Time Limit Exceeded' (TLE) error for large input sizes as specified in the constraints.

A more efficient approach avoids recalculating the score from scratch for each rotation. Instead, we can determine, for each element nums[i], the range of rotations k for which it will contribute a point. An element nums[i] scores a point for rotation k if its value is less than or equal to its new index, i.e., nums[i] <= (i - k + N) % N.

This inequality defines one or two contiguous intervals of k values that are 'good' for nums[i]. We can use a difference array (a technique related to sweep-line algorithms) to efficiently calculate the total score for every k. For each scoring interval [start, end], we increment a change array at start and decrement it at end + 1. After processing all elements, a single pass over the change array, computing prefix sums, gives us the score for each k. We can then find the k with the maximum score in this pass.

Algorithm

Let N be the length of nums. Create a difference array change of size N, initialized to zeros.
Iterate through each element nums[i] from i = 0 to N-1. Let val = nums[i].
For each element, determine the range(s) of rotation index k for which it will score a point. The condition is val <= (i - k + N) % N.
If i >= val, the scoring k intervals are [0, i - val] and [i + 1, N - 1]. Update the change array: change[0]++, change[i - val + 1]--, and change[i + 1]++.
If i < val, the scoring k interval is [i + 1, i - val + N]. Update the change array: change[i + 1]++ and change[i - val + N + 1]--.
After processing all elements, compute the actual scores by taking a running prefix sum of the change array. Initialize currentScore = 0, maxScore = -1, bestK = 0.
Iterate k from 0 to N-1. Update currentScore += change[k]. If currentScore > maxScore, update maxScore = currentScore and bestK = k.
Return bestK.

Walkthrough

Let's analyze the scoring condition nums[i] <= (i - k + N) % N for a fixed element nums[i] and a variable rotation k.

Case 1: i >= nums[i] The element nums[i] scores a point for k in two disjoint intervals: [0, i - nums[i]] and [i + 1, N - 1]. For the first interval, we do change[0]++ and change[i - nums[i] + 1]--. For the second, change[i + 1]++.
Case 2: i < nums[i] The element nums[i] scores a point for k in a single interval: [i + 1, i - nums[i] + N]. We update change[i + 1]++ and change[i - nums[i] + N + 1]--.

After populating the change array by iterating through all nums[i], we can find the final scores. The score for rotation k is the sum of all change[j] for j from 0 to k. We can compute this with a running sum and find the k that maximizes this sum.

1class Solution {2    public int bestRotation(int[] nums) {3        int n = nums.length;4        int[] change = new int[n];5 6        for (int i = 0; i < n; i++) {7            int val = nums[i];8            // For each element nums[i], find the intervals of k where it scores.9            // A point is scored if val <= new_index, where new_index = (i - k + n) % n.10            if (i >= val) {11                // Good intervals for k: [0, i - val] and [i + 1, n - 1]12                // Interval [0, i - val]13                change[0]++;14                if (i - val + 1 < n) {15                    change[i - val + 1]--;16                }17                // Interval [i + 1, n - 1]18                if (i + 1 < n) {19                    change[i + 1]++;20                }21            } else { // i < val22                // Good interval for k: [i + 1, i - val + n]23                if (i + 1 < n) {24                    change[i + 1]++;25                }26                if (i - val + n + 1 < n) {27                    change[i - val + n + 1]--;28                }29            }30        }31 32        int maxScore = -1;33        int bestK = 0;34        int currentScore = 0;35        for (int k = 0; k < n; k++) {36            currentScore += change[k];37            if (currentScore > maxScore) {38                maxScore = currentScore;39                bestK = k;40            }41        }42 43        return bestK;44    }45}

Complexity

Time

O(N). We make one pass through `nums` to build the `change` array (O(N)), and one pass to compute the scores and find the maximum (O(N)).

Space

O(N) to store the difference array `change`.

Trade-offs

Pros

Very efficient, with linear time complexity.
Optimal solution for the given constraints.

Cons

Requires extra space proportional to the input size.
The logic for determining the scoring intervals can be complex to derive correctly.

Solutions

Solution

1class Solution {2public3  int bestRotation(int[] nums) {4    int n = nums.length;5    int[] d = new int[n];6    for (int i = 0; i < n; ++i) {7      int l = (i + 1) % n;8      int r = (n + i + 1 - nums[i]) % n;9      ++d[l];10      --d[r];11    }12    int mx = -1;13    int s = 0;14    int ans = n;15    for (int k = 0; k < n; ++k) {16      s += d[k];17      if (s > mx) {18        mx = s;19        ans = k;20      }21    }22    return ans;23  }24}

1class Solution {2public:3  int bestRotation(vector<int> &nums) {4    int n = nums.size();5    int mx = -1, ans = n;6    vector<int> d(n);7    for (int i = 0; i < n; ++i) {8      int l = (i + 1) % n;9      int r = (n + i + 1 - nums[i]) % n;10      ++d[l];11      --d[r];12    }13    int s = 0;14    for (int k = 0; k < n; ++k) {15      s += d[k];16      if (s > mx) {17        mx = s;18        ans = k;19      }20    }21    return ans;22  }23};

1class Solution:2    def bestRotation(self, nums: List[int]) -> int: n = len(nums) mx, ans = - 1, n d = [0] * n for i, v in enumerate(nums): l, r = (i + 1) % n, (n + i + 1 - v) % n d[l] += 1 d[r] -= 1 s = 0 for k, t in enumerate(d): s += t if s > mx: mx = s ans = k return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem