LeetCode 798 - Smallest Rotation with Highest Score

The problem asks us to determine the optimal rotation of an array nums so that the resulting array achieves the highest possible score, where a score is defined as the number of elements that are less than or equal to their index after rotation.

leetcodehardarrayprefix-sum

LeetCode Problem 798

Difficulty: 🔴 Hard
Topics: Array, Prefix Sum

Solution

Problem Understanding

The problem asks us to determine the optimal rotation of an array nums so that the resulting array achieves the highest possible score, where a score is defined as the number of elements that are less than or equal to their index after rotation. In other words, after rotating the array by some k, an element at position i contributes 1 point if nums[i] <= i.

The input is a zero-indexed array of integers where each element is between 0 and nums.length - 1. The output is a single integer k representing the smallest rotation index that yields the maximum score. The constraints indicate the array can be large, up to 10^5 elements, which rules out brute-force solutions that compute scores for all possible rotations individually, since that would require O(n^2) operations.

Important edge cases include arrays that are already in ascending order, arrays where all elements are the same, arrays where multiple rotations yield the same maximal score, and arrays of length 1. The problem guarantees valid input within the bounds, so we do not need to handle negative numbers or out-of-range values.

Approaches

The brute-force approach involves iterating over all possible rotations from 0 to n-1, applying the rotation, and then computing the score by checking each element against its index. This is simple to implement and guaranteed to be correct but has time complexity O(n^2) because each of the n rotations requires inspecting all n elements, which is too slow for n = 10^5.

The optimal approach uses a key observation: instead of calculating the score for each rotation individually, we can track how the score changes as we rotate. Each element nums[i] contributes a point for rotations k where (i - k + n) % n >= nums[i], which can be expressed as a range in modular arithmetic. By recording the start and end of these ranges as "score changes" in an auxiliary array and computing a prefix sum, we can determine the rotation that gives the maximal score in O(n) time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Rotate the array for all k and compute score each time
Optimal O(n) O(n) Use difference array to track score changes efficiently

Algorithm Walkthrough

  1. Initialize an array change of length n with all zeros. This array will track how the score changes as we rotate.
  2. For each index i in nums, compute the rotation index range [start, end) where the score contribution of nums[i] decreases. Specifically, if nums[i] > 0, the score decreases when rotated beyond (i - nums[i] + 1 + n) % n.
  3. Update the change array: increment change[start] and decrement change[end] to reflect the range where the element stops contributing to the score.
  4. Iterate through the change array, computing a running prefix sum to track the total score for each rotation k.
  5. Keep track of the maximum score encountered and the smallest index k that achieves it.
  6. Return the smallest k with the maximum score.

Why it works: Each element contributes to the score over a specific range of rotations. By using a difference array and prefix sums, we aggregate all individual contributions efficiently. The prefix sum guarantees we correctly compute the score for each rotation in O(n) time.

Python Solution

from typing import List

class Solution:
    def bestRotation(self, nums: List[int]) -> int:
        n = len(nums)
        change = [0] * n

        for i, num in enumerate(nums):
            start = (i - num + 1 + n) % n
            end = (i + 1) % n
            change[start] += 1
            change[end] -= 1
            if start >= end:
                change[0] += 1

        max_score = score = 0
        best_k = 0
        for k in range(n):
            score += change[k]
            if score > max_score:
                max_score = score
                best_k = k

        return best_k

Explanation: We first create a change array that tracks the effect of each number on the score as we rotate. For each number, we calculate the rotation range that decreases its score contribution. After adjusting for modular wrapping, we accumulate the total score for each rotation using a prefix sum and return the smallest rotation that gives the maximum score.

Go Solution

func bestRotation(nums []int) int {
    n := len(nums)
    change := make([]int, n)

    for i, num := range nums {
        start := (i - num + 1 + n) % n
        end := (i + 1) % n
        change[start]++
        change[end]--
        if start >= end {
            change[0]++
        }
    }

    maxScore, score, bestK := 0, 0, 0
    for k := 0; k < n; k++ {
        score += change[k]
        if score > maxScore {
            maxScore = score
            bestK = k
        }
    }

    return bestK
}

Go-specific notes: We use slices instead of arrays for dynamic allocation. Modulo operations handle wrapping correctly. No additional data structures are needed beyond the change slice.

Worked Examples

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

i nums[i] start end change update
0 2 4 1 change[4]+=1, change[1]-=1, change[0]+=1
1 3 0 2 change[0]+=1, change[2]-=1
2 1 2 3 change[2]+=1, change[3]-=1
3 4 0 4 change[0]+=1, change[4]-=1
4 0 0 0 change[0]+=1, change[0]-=1

Prefix sum produces scores for k=0..4: [2,3,3,4,3], so best_k = 3.

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

Prefix sum produces scores for k=0..4: [3,3,3,3,3], so best_k = 0.

Complexity Analysis

Measure Complexity Explanation
Time O(n) We iterate through the array once to compute changes, then once to compute prefix sums.
Space O(n) The change array requires O(n) space.

The optimal approach avoids computing the score for each rotation explicitly, resulting in a linear time algorithm suitable for large arrays.

Test Cases

# Provided examples
assert Solution().bestRotation([2,3,1,4,0]) == 3  # max score 4 at k=3
assert Solution().bestRotation([1,3,0,2,4]) == 0  # all rotations score 3, smallest k=0

# Edge cases
assert Solution().bestRotation([0]) == 0  # single element
assert Solution().bestRotation([0,0,0,0]) == 0  # all zeros, any k works
assert Solution().bestRotation([4,3,2,1,0]) == 1  # descending order
assert Solution().bestRotation([1,2,3,4,0]) == 4  # single max at end
Test Why
[2,3,1,4,0] Checks standard case with varying scores
[1,3,0,2,4] Checks multiple rotations yielding same score
[0] Single element edge case
[0,0,0,0] All elements identical edge case
[4,3,2,1,0] Descending order, rotation affects score
[1,2,3,4,0] Max at the end, affects optimal rotation

Edge Cases

  1. Single element array: An array with one element, e.g., [0]. This could trip up naive modulo calculations. Our implementation handles it because n = 1 ensures modulo arithmetic and loops work correctly.
  2. All elements the same: An array like [0,0,0,0] may have multiple rotations yielding the same maximal score. The algorithm correctly returns the smallest index because we initialize best_k to 0 and update only when a strictly higher score is found.
  3. Descending order array: An array like [4,3,2,1,0] tests whether the rotation logic properly handles negative ranges and modulo wrapping. The modular arithmetic in computing start ensures ranges wrap correctly, and prefix sum aggregation correctly identifies the optimal rotation.