# LeetCode 798: Smallest Rotation with Highest Score

## Problem Restatement

We are given an array `nums`.

A rotation by `k` changes the array into:

```python
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

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | Smallest rotation index `k` with the highest score |
| Rotation range | `0 <= k < len(nums)` |
| Point rule | A value earns one point if `value <= new_index` |
| Tie rule | Return the smallest valid `k` |

Function shape:

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

## Examples

Example 1:

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

The best rotation is:

```python
3
```

When `k = 3`, the rotated array is:

```python
[4, 0, 2, 3, 1]
```

The scoring positions are:

| Index | Value | Point? |
|---:|---:|---|
| `0` | `4` | No |
| `1` | `0` | Yes |
| `2` | `2` | Yes |
| `3` | `3` | Yes |
| `4` | `1` | Yes |

The score is `4`.

Example 2:

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

The best rotation is:

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

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

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

```python
(i - k + n) % n
```

It earns a point when:

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

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

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

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

The bad interval ends just after rotation:

```python
end = (i + 1) % n
```

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

```text
[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:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each element contributes one interval, then we scan once |
| Space | `O(n)` | The difference array stores rotation changes |

## Implementation

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

```python
diff = [0] * (n + 1)
```

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

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

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

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

If it wraps, split it into two intervals:

```python
[start, n)
[0, end)
```

So we mark both parts:

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

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

```python
current_bad += diff[k]
```

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

```python
if current_bad < best_bad:
    best_bad = current_bad
    best_k = k
```

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

## Testing

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

| Test | Why |
|---|---|
| `[2, 3, 1, 4, 0]` | Standard example |
| `[1, 3, 0, 2, 4]` | Best rotation is zero |
| Single element | Smallest input |
| All zeroes | Every rotation scores fully, smallest `k` wins |
| Wrapped interval case | Checks circular difference handling |
| Tie-like small case | Checks smallest index rule |