Smallest Rotation with Highest Score

hard arrays difference-array prefix-sum

Problem

Given array nums of length n, you choose a rotation k. After rotating left by k, index i scores 1 if nums[i] <= i. Return the k that maximizes total score, choosing the smallest k on ties.

Inputnums = [2,3,1,4,0]

Output3

Rotating by 3 gives scoring at positions 0,1,2,3 — total 3.

nums

def bestRotation(nums):
    n = len(nums)
    diff = [0] * (n + 1)
    for j, v in enumerate(nums):
        lo = (j - (n - 1)) % n
        hi = (j - v) % n
        if lo <= hi:
            diff[lo] += 1
            diff[hi + 1] -= 1
        else:
            diff[lo] += 1
            diff[n] -= 1
            diff[0] += 1
            diff[hi + 1] -= 1
    best_k, best_score, cur = 0, -1, 0
    for k in range(n):
        cur += diff[k]
        if cur > best_score:
            best_score, best_k = cur, k
    return best_k

var bestRotation = function(nums) {
    const n = nums.length;
    const diff = new Array(n + 1).fill(0);
    for (let j = 0; j < n; j++) {
        const v = nums[j];
        const lo = ((j - (n - 1)) % n + n) % n;
        const hi = ((j - v) % n + n) % n;
        if (lo <= hi) { diff[lo] += 1; diff[hi + 1] -= 1; }
        else { diff[lo] += 1; diff[n] -= 1; diff[0] += 1; diff[hi + 1] -= 1; }
    }
    let bestK = 0, bestScore = -1, cur = 0;
    for (let k = 0; k < n; k++) {
        cur += diff[k];
        if (cur > bestScore) { bestScore = cur; bestK = k; }
    }
    return bestK;
};

class Solution {
    public int bestRotation(int[] nums) {
        int n = nums.length;
        int[] diff = new int[n + 1];
        for (int j = 0; j < n; j++) {
            int v = nums[j];
            int lo = ((j - (n - 1)) % n + n) % n;
            int hi = ((j - v) % n + n) % n;
            if (lo <= hi) { diff[lo]++; diff[hi + 1]--; }
            else { diff[lo]++; diff[n]--; diff[0]++; diff[hi + 1]--; }
        }
        int bestK = 0, bestScore = -1, cur = 0;
        for (int k = 0; k < n; k++) {
            cur += diff[k];
            if (cur > bestScore) { bestScore = cur; bestK = k; }
        }
        return bestK;
    }
}

class Solution {
public:
    int bestRotation(vector<int>& nums) {
        int n = nums.size();
        vector<int> diff(n + 1, 0);
        for (int j = 0; j < n; j++) {
            int v = nums[j];
            int lo = ((j - (n - 1)) % n + n) % n;
            int hi = ((j - v) % n + n) % n;
            if (lo <= hi) { diff[lo]++; diff[hi + 1]--; }
            else { diff[lo]++; diff[n]--; diff[0]++; diff[hi + 1]--; }
        }
        int bestK = 0, bestScore = -1, cur = 0;
        for (int k = 0; k < n; k++) {
            cur += diff[k];
            if (cur > bestScore) { bestScore = cur; bestK = k; }
        }
        return bestK;
    }
};

Explanation

The slow idea is to try every rotation k and count the score each time, which costs O(n²). The smart trick is to notice that each element only earns a point for a contiguous range of rotations, so we can mark those ranges cheaply with a difference array.

Think about one element v at index j. After rotating left by k, that element lands at a new position, and it scores when its value is at most its new index. Working through the math, it scores exactly for rotations k in a wrap-around window from lo = (j-(n-1)) % n to hi = (j-v) % n.

Instead of touching every k in that window, we just add +1 at the start of the range and -1 just past the end in diff. If the range wraps past the end of the array, we split it into two pieces and mark both.

After all elements are marked, we sweep a running prefix sum over diff. The value at each k is exactly the total score for that rotation. We track the highest score and, on ties, keep the smallest k by only updating on a strictly greater score.

Example: nums = [2,3,1,4,0]. Each value contributes its scoring window into diff, the prefix sum reveals rotation k = 3 hits the highest total, so the answer is 3.

Time: O(n) Space: O(n)