LeetCode 798: Smallest Rotation with Highest Score

Problem Restatement

We are given an array nums.

A rotation by k changes the array into:

nums[k], nums[k + 1], ..., nums[n - 1], nums[0], ..., nums[k - 1]

After rotating, an element earns one point if its value is less than or equal to its new index.

We need to return the rotation index k that gives the highest score. If multiple rotations have the same highest score, return the smallest k.

Input and Output

Function shape:

class Solution:
    def bestRotation(self, nums: list[int]) -> int:
        ...

Examples

Example 1:

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

The best rotation is:

3

When k = 3, the rotated array is:

[4, 0, 2, 3, 1]

The scoring positions are:

The score is 4.

Example 2:

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

The best rotation is:

0

The original array already gives the highest score.

First Thought: Try Every Rotation

A direct solution is to simulate every possible rotation.

For each k:

1. Rotate the array.
2. Count how many positions satisfy:

rotated[i] <= i

3. Keep the rotation with the highest score.

This works, but it takes too long.

For each of n rotations, we scan n elements, so the time is:

O(n^2)

With n up to 100000, this is not acceptable.

Key Insight

Instead of computing the full score for every rotation, compute how each element affects a range of rotations.

For an element originally at index i, after rotating left by k, its new index is:

(i - k + n) % n

It earns a point when:

nums[i] <= (i - k + n) % n

Equivalently, each element has some rotations where it is good, and some rotations where it is bad.

It is easier to mark where each element loses a point.

For a value nums[i], it loses a point when its new index is:

0, 1, ..., nums[i] - 1

As k increases by one, the element moves one position left in circular order. So the bad rotations form one circular interval.

We can mark these bad intervals with a difference array.

Then a prefix sum gives the score change for every rotation.

Bad Interval

Let:

n = len(nums)
value = nums[i]

The element loses a point when its new index is less than value.

The first rotation where it becomes bad is:

start = (i - value + 1 + n) % n

The bad interval ends just after rotation:

end = (i + 1) % n

So this element is bad for rotations in the circular interval:

[start, end)

We use a difference array bad.

To add +1 bad count over a circular interval:

1. Add +1 at start.
2. Add -1 at end.
3. If the interval wraps around, also add +1 at 0.

Instead of tracking good score directly, we track how many elements are bad. The best rotation is the one with the smallest bad count.

Algorithm

1. Let n = len(nums).
2. Create a difference array diff of length n + 1.
3. For each index i:
   1. Compute start = (i - nums[i] + 1 + n) % n.
   2. Compute end = (i + 1) % n.
   3. Add one bad interval from start to end.
4. Scan rotations from 0 to n - 1 using a running bad count.
5. Choose the rotation with the smallest bad count.
6. Because we scan from left to right and update only on strictly smaller bad count, ties keep the smallest index.

Correctness

For each element nums[i], the algorithm computes exactly the rotations where that element does not score. Under rotation k, the element moves to index (i - k + n) % n. It fails exactly when this new index is less than nums[i]. These failing positions form the circular interval from (i - nums[i] + 1 + n) % n to (i + 1) % n.

The difference array adds one bad count to exactly those rotations. After all elements are processed, the prefix sum at rotation k equals the number of elements that fail to score under rotation k.

For a fixed rotation, the total score is:

n - bad_count

So maximizing the score is the same as minimizing the bad count.

The algorithm scans rotations in increasing order and records a rotation only when it finds a strictly smaller bad count. Therefore, if multiple rotations have the same best score, the first one encountered is kept, which is the smallest such k.

Thus, the algorithm returns the required rotation index.

Complexity

Implementation

class Solution:
    def bestRotation(self, nums: list[int]) -> int:
        n = len(nums)
        diff = [0] * (n + 1)

        for i, value in enumerate(nums):
            start = (i - value + 1 + n) % n
            end = (i + 1) % n

            if start < end:
                diff[start] += 1
                diff[end] -= 1
            else:
                diff[start] += 1
                diff[n] -= 1
                diff[0] += 1
                diff[end] -= 1

        best_k = 0
        best_bad = float("inf")
        current_bad = 0

        for k in range(n):
            current_bad += diff[k]

            if current_bad < best_bad:
                best_bad = current_bad
                best_k = k

        return best_k

Code Explanation

The difference array tracks how many elements are bad for each rotation:

diff = [0] * (n + 1)

For each element, compute the circular interval where it loses a point:

start = (i - value + 1 + n) % n
end = (i + 1) % n

If the interval does not wrap around, mark it normally:

diff[start] += 1
diff[end] -= 1

If it wraps, split it into two intervals:

[start, n)
[0, end)

So we mark both parts:

diff[start] += 1
diff[n] -= 1
diff[0] += 1
diff[end] -= 1

Then we scan all rotations and compute the current bad count:

current_bad += diff[k]

The best rotation is the one with the fewest bad elements:

if current_bad < best_bad:
    best_bad = current_bad
    best_k = k

Using < instead of <= preserves the smallest index in a tie.

Testing

def run_tests():
    s = Solution()

    assert s.bestRotation([2, 3, 1, 4, 0]) == 3
    assert s.bestRotation([1, 3, 0, 2, 4]) == 0

    assert s.bestRotation([0]) == 0
    assert s.bestRotation([0, 0, 0]) == 0

    assert s.bestRotation([2, 4, 1, 3, 0]) == 2

    assert s.bestRotation([1, 0, 0]) == 1

    print("all tests passed")

run_tests()

Test coverage: