Problem statement

You are given an array nums of length n. Rotating it by k (0 <= k < n) moves the first k elements to the back, giving [nums[k], nums[k + 1], …, nums[n - 1], nums[0], …, nums[k - 1]].

After the rotation, every element that is less than or equal to its new index scores one point.

Return the rotation k with the highest score. If several rotations tie, return the smallest such k.

Example 1

Input: nums = [2,3,1,4,0]
Output: 3
Explanation: Scores for k = 0..4 are 2, 3, 3, 4, 3. Rotating by 3 gives [4,0,2,3,1]: 0 <= 1, 2 <= 2, 3 <= 3 and 1 <= 4 score.

Example 2

Input: nums = [1,3,0,2,4]
Output: 0
Explanation: Every rotation scores 3, so the smallest k wins.

Example 3

Input: nums = [0]
Output: 0

Constraints

• 1 <= nums.length <= 10^5
• 0 <= nums[i] < nums.length

Hints for Smallest Rotation with Highest Score

1. Hint 1

   Trying every rotation and recounting costs O(n^2). Instead, ask for each element: for which rotations k does it score?

2. Hint 2

   Element nums[i] lands at index (i - k) mod n. It scores when that index is at least nums[i] — this happens for one contiguous (cyclic) range of k, and it fails on the complementary range.

3. Hint 3

   The failing range is k in [(i - nums[i] + 1) mod n, i] (cyclically). Mark every element's failing range in a difference array, take prefix sums, and pick the k with the fewest failures.

How to solve Smallest Rotation with Highest Score

Instead of scoring each rotation, compute for each element the rotations where it loses its point. Each such set is one cyclic interval of k, so a difference array over k adds them all up in O(n); the best rotation is the one with the fewest losses.

Approach

1. Create change of length n, all zero.
2. For each i with nums[i] > 0, the element loses its point exactly for k from lo = (i - nums[i] + 1) mod n up to i (wrapping around). Do change[lo] -= 1 and change[(i + 1) mod n] += 1; if the interval wraps (lo > i), also do change[0] -= 1.
3. Sweep k = 0 .. n - 1, keeping the prefix sum cur of change — it equals the score of rotation k minus n.
4. Return the first k where cur is largest.

Why it works

After rotating by k, element i sits at index j = (i - k) mod n and scores iff j >= nums[i]. As k runs over 0..n-1, j takes every value exactly once; the failing values j < nums[i] correspond to k = i - j for j = 0 .. nums[i] - 1, i.e. k from i - nums[i] + 1 to i modulo n — one cyclic block of length nums[i]. A difference array adds -1 over each block (split in two when it wraps), so the prefix sum at k is minus the number of elements failing at k, which differs from the score by the constant n. A strict comparison while scanning keeps the smallest best k.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• Use a non-negative modulo: in C-family languages (i - nums[i] + 1) % n can be negative.
• An element with nums[i] = 0 scores at every rotation and has no failing range — skip it, or the formula lo = i + 1 would be mistaken for a wrapping interval.
• Ties go to the smallest k: update the best only on a strictly larger score.

Reference solution

Python

from typing import List

def bestRotation(nums: List[int]) -> int:
    n = len(nums)
    change = [0] * n
    for i, x in enumerate(nums):
        if x == 0:
            continue  # always scores
        lo, hi = (i - x + 1) % n, (i + 1) % n
        change[lo] -= 1
        change[hi] += 1
        if lo > i:
            change[0] -= 1
    best, best_k, cur = -n - 1, 0, 0
    for k in range(n):
        cur += change[k]
        if cur > best:
            best, best_k = cur, k
    return best_k

Java

public static int bestRotation(int[] nums) {
    int n = nums.length;
    int[] change = new int[n];
    for (int i = 0; i < n; i++) {
        if (nums[i] == 0) continue; // always scores
        int lo = ((i - nums[i] + 1) % n + n) % n, hi = (i + 1) % n;
        change[lo]--;
        change[hi]++;
        if (lo > i) change[0]--;
    }
    int best = -n - 1, bestK = 0, cur = 0;
    for (int k = 0; k < n; k++) {
        cur += change[k];
        if (cur > best) { best = cur; bestK = k; }
    }
    return bestK;
}

C++

int bestRotation(vector<int>& nums) {
    int n = nums.size();
    vector<int> change(n, 0);
    for (int i = 0; i < n; i++) {
        if (nums[i] == 0) continue; // always scores
        int lo = ((i - nums[i] + 1) % n + n) % n, hi = (i + 1) % n;
        change[lo]--;
        change[hi]++;
        if (lo > i) change[0]--;
    }
    int best = -n - 1, bestK = 0, cur = 0;
    for (int k = 0; k < n; k++) {
        cur += change[k];
        if (cur > best) { best = cur; bestK = k; }
    }
    return bestK;
}

JavaScript

var bestRotation = function(nums) {
    var n = nums.length;
    var change = new Array(n);
    for (var t = 0; t < n; t++) change[t] = 0;
    for (var i = 0; i < n; i++) {
        if (nums[i] === 0) continue; // always scores
        var lo = ((i - nums[i] + 1) % n + n) % n, hi = (i + 1) % n;
        change[lo]--;
        change[hi]++;
        if (lo > i) change[0]--;
    }
    var best = -n - 1, bestK = 0, cur = 0;
    for (var k = 0; k < n; k++) {
        cur += change[k];
        if (cur > best) { best = cur; bestK = k; }
    }
    return bestK;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Sum of Imbalance Numbers of All Subarrays Hard