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 indexk that corresponds to the highest score we can achieve if we rotatednums by it. If there are multiple answers, return the smallest such index k.

Examples

Example 1

1
2
3
4
5
6
7
8
9

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

1
2
3
4

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^5
  • 0 <= nums[i] < nums.length

Solution

Method 1 – Difference Array and Prefix Sum

Intuition

For each index, we can determine the range of rotations where it contributes a point. Using a difference array, we can efficiently accumulate the score changes for all rotations, then use prefix sum to get the score for each rotation.

Approach

  1. For each index i, calculate the range of k where nums[i] <= (i - k + n) % n.
  2. For each such range, increment the score at the start and decrement after the end in a difference array.
  3. Compute the prefix sum to get the score for each rotation.
  4. Return the smallest k with the highest score.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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

func bestRotation(nums []int) int {
    n := len(nums)
    diff := make([]int, n+1)
    for i, v := range nums {
        l := (i+1)%n
        r := (i-v+n+1)%n
        diff[l]++
        diff[r]--
        if l > r { diff[0]++ }
    }
    ans, maxs, s := 0, 0, 0
    for k := 0; k < n; k++ {
        s += diff[k]
        if s > maxs { maxs = s; ans = k }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int bestRotation(int[] nums) {
        int n = nums.length;
        int[] diff = new int[n+1];
        for (int i = 0; i < n; ++i) {
            int l = (i+1)%n, r = (i-nums[i]+n+1)%n;
            diff[l]++;
            diff[r]--;
            if (l > r) diff[0]++;
        }
        int ans = 0, maxs = 0, s = 0;
        for (int k = 0; k < n; ++k) {
            s += diff[k];
            if (s > maxs) { maxs = s; ans = k; }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun bestRotation(nums: IntArray): Int {
        val n = nums.size
        val diff = IntArray(n+1)
        for (i in 0 until n) {
            val l = (i+1)%n
            val r = (i-nums[i]+n+1)%n
            diff[l]++
            diff[r]--
            if (l > r) diff[0]++
        }
        var ans = 0; var maxs = 0; var s = 0
        for (k in 0 until n) {
            s += diff[k]
            if (s > maxs) { maxs = s; ans = k }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def bestRotation(self, nums: list[int]) -> int:
        n = len(nums)
        diff = [0]*(n+1)
        for i, v in enumerate(nums):
            l = (i+1)%n
            r = (i-v+n+1)%n
            diff[l] += 1
            diff[r] -= 1
            if l > r: diff[0] += 1
        ans = maxs = s = 0
        for k in range(n):
            s += diff[k]
            if s > maxs:
                maxs = s
                ans = k
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn best_rotation(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut diff = vec![0; n+1];
        for (i, &v) in nums.iter().enumerate() {
            let l = (i+1)%n;
            let r = (i as i32-v+n as i32+1) as usize % n;
            diff[l] += 1;
            diff[r] -= 1;
            if l > r { diff[0] += 1; }
        }
        let (mut ans, mut maxs, mut s) = (0, 0, 0);
        for k in 0..n {
            s += diff[k];
            if s > maxs { maxs = s; ans = k; }
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    bestRotation(nums: number[]): number {
        const n = nums.length;
        const diff = Array(n+1).fill(0);
        for (let i = 0; i < n; ++i) {
            const l = (i+1)%n, r = (i-nums[i]+n+1)%n;
            diff[l]++;
            diff[r]--;
            if (l > r) diff[0]++;
        }
        let ans = 0, maxs = 0, s = 0;
        for (let k = 0; k < n; ++k) {
            s += diff[k];
            if (s > maxs) { maxs = s; ans = k; }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. Each index is processed a constant number of times.
  • 🧺 Space complexity: O(n), for the difference array.