# Smallest Rotation with Highest Score
**Difficulty:** HARD
[External](https://leetcode.com/problems/smallest-rotation-with-highest-score)
Canonical: https://scaleengineer.com/dsa/problems/smallest-rotation-with-highest-score
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
---
## Problem
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`

# Approaches
## Brute Force Simulation
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.
**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).
**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.
### Explanation
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.

```java
class Solution {
    public int bestRotation(int[] nums) {
        int n = nums.length;
        int maxScore = -1;
        int bestK = 0;

        for (int k = 0; k < n; k++) {
            int currentScore = 0;
            for (int i = 0; i < n; i++) {
                // The original index of the element at new index i is (i + k) % n
                int originalIndex = (i + k) % n;
                if (nums[originalIndex] <= i) {
                    currentScore++;
                }
            }
            if (currentScore > maxScore) {
                maxScore = currentScore;
                bestK = k;
            }
        }
        return bestK;
    }
}
```
### Algorithm
1. Initialize `maxScore` to -1 and `bestK` to 0.
2. Iterate through each possible rotation index `k` from `0` to `N-1`, where `N` is the length of the array.
3. For each `k`, initialize a `currentScore` to 0.
4. Iterate through each index `i` from `0` to `N-1` of the (conceptually) rotated array.
5. The element at index `i` in the array rotated by `k` is `nums[(i + k) % N]`.
6. Check if this element's value is less than or equal to its new index: `nums[(i + k) % N] <= i`.
7. If the condition is true, increment `currentScore`.
8. After iterating through all `i`'s, compare `currentScore` with `maxScore`.
9. If `currentScore > maxScore`, update `maxScore = currentScore` and `bestK = k`.
10. After the outer loop finishes, `bestK` will hold the smallest rotation index with the highest score. Return `bestK`.

## Difference Array / Sweep Line
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.
**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`.
**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.
### Explanation
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.

```java
class Solution {
    public int bestRotation(int[] nums) {
        int n = nums.length;
        int[] change = new int[n];

        for (int i = 0; i < n; i++) {
            int val = nums[i];
            // For each element nums[i], find the intervals of k where it scores.
            // A point is scored if val <= new_index, where new_index = (i - k + n) % n.
            if (i >= val) {
                // Good intervals for k: [0, i - val] and [i + 1, n - 1]
                // Interval [0, i - val]
                change[0]++;
                if (i - val + 1 < n) {
                    change[i - val + 1]--;
                }
                // Interval [i + 1, n - 1]
                if (i + 1 < n) {
                    change[i + 1]++;
                }
            } else { // i < val
                // Good interval for k: [i + 1, i - val + n]
                if (i + 1 < n) {
                    change[i + 1]++;
                }
                if (i - val + n + 1 < n) {
                    change[i - val + n + 1]--;
                }
            }
        }

        int maxScore = -1;
        int bestK = 0;
        int currentScore = 0;
        for (int k = 0; k < n; k++) {
            currentScore += change[k];
            if (currentScore > maxScore) {
                maxScore = currentScore;
                bestK = k;
            }
        }

        return bestK;
    }
}
```
### Algorithm
1. Let `N` be the length of `nums`. Create a difference array `change` of size `N`, initialized to zeros.
2. Iterate through each element `nums[i]` from `i = 0` to `N-1`. Let `val = nums[i]`.
3. 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`.
4. 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]++`.
5. 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]--`.
6. 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`.
7. Iterate `k` from `0` to `N-1`. Update `currentScore += change[k]`. If `currentScore > maxScore`, update `maxScore = currentScore` and `bestK = k`.
8. Return `bestK`.

# Solutions
### Java

```java
class Solution {
public
  int bestRotation(int[] nums) {
    int n = nums.length;
    int[] d = new int[n];
    for (int i = 0; i < n; ++i) {
      int l = (i + 1) % n;
      int r = (n + i + 1 - nums[i]) % n;
      ++d[l];
      --d[r];
    }
    int mx = -1;
    int s = 0;
    int ans = n;
    for (int k = 0; k < n; ++k) {
      s += d[k];
      if (s > mx) {
        mx = s;
        ans = k;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int bestRotation(vector<int> &nums) {
    int n = nums.size();
    int mx = -1, ans = n;
    vector<int> d(n);
    for (int i = 0; i < n; ++i) {
      int l = (i + 1) % n;
      int r = (n + i + 1 - nums[i]) % n;
      ++d[l];
      --d[r];
    }
    int s = 0;
    for (int k = 0; k < n; ++k) {
      s += d[k];
      if (s > mx) {
        mx = s;
        ans = k;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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

```