798. Smallest Rotation with Highest Score

LeetCode ↗

Problem Editor Pattern Idea Example Code Complex Pitfalls

Problem Description

You have an array nums that can be rotated by a non-negative integer k. When you rotate by k, the array transforms from its original form to [nums[k], nums[k + 1], ... nums[nums.length - 1], nums[0], nums[1], ..., nums[k-1]]. In other words, you take the first k elements and move them to the end of the array.

After rotation, you calculate a score based on how many elements satisfy a specific condition: an element at index i earns one point if its value is less than or equal to i.

For example, given nums = [2,4,1,3,0]:

If you rotate by k = 2, the array becomes [1,3,0,2,4]
Now checking each position:
- Index 0: value 1 > 0 → no point
- Index 1: value 3 > 1 → no point
- Index 2: value 0 ≤ 2 → one point
- Index 3: value 2 ≤ 3 → one point
- Index 4: value 4 ≤ 4 → one point
Total score = 3 points

Your task is to find the rotation value k that produces the maximum possible score. If multiple values of k give the same maximum score, return the smallest k.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Prefix Sum?

This problem maps to Prefix Sum through a short path in the full flowchart.

A circular difference array marks the rotation interval in which each element scores so a single sweep finds the best k.

Open in Flowchart

Intuition

The key insight is to think about when each element contributes a point across different rotations, rather than calculating the entire score for each possible rotation.

For an element nums[i] with value v, we need to determine: for which rotation values k will this element contribute a point? After rotation by k, the element originally at index i moves to position (i - k + n) % n. For this element to score a point, we need v ≤ (i - k + n) % n.

Instead of checking all rotations directly (which would be O(n²)), we can be smarter. For each element, we can calculate the range of k values where it contributes a point. When an element starts contributing and when it stops contributing forms an interval.

The critical observation is that for each element at original position i with value v:

It starts contributing a point when rotated to a position where its new index is at least v
The element begins contributing at rotation k = (i + 1) % n
It stops contributing when the new position becomes less than v, which happens at k = (n + i + 1 - v) % n

By using a difference array technique, we can efficiently track how the score changes as we increase k. We mark the start of each contribution interval with +1 and the end with -1. Then, by scanning through all possible k values and maintaining a running sum, we can find the maximum score and the smallest k that achieves it.

This transforms the problem from calculating full scores for each rotation to simply tracking score changes, reducing complexity from O(n²) to O(n).

Pattern Learn more about Prefix Sum patterns.

New to patterns?Most interview problems reduce to a handful of patterns. This video covers the main eight.

Solution Approach

The solution uses a difference array to efficiently track score changes across all possible rotations. The snippets below use short names; in the full solution, d is diff, l and r are left and right, s is current_score, mx is max_score, and ans is best_rotation.

Step 1: Initialize the difference array

d = [0] * n

This array tracks the change in score when moving from rotation k-1 to rotation k.

Step 2: Calculate contribution intervals for each element For each element at index i with value v:

l, r = (i + 1) % n, (n + i + 1 - v) % n
d[l] += 1
d[r] -= 1

l = (i + 1) % n: The rotation where element nums[i] starts contributing a point
r = (n + i + 1 - v) % n: The rotation where element nums[i] stops contributing
We increment d[l] to mark the start of contribution
We decrement d[r] to mark the end of contribution

Step 3: Find the rotation with maximum score

s = 0
mx, ans = -1, n
for k, t in enumerate(d):
    s += t
    if s > mx:
        mx = s
        ans = k

We iterate through all possible rotations k from 0 to n-1:

s += t: Accumulate the score change to get the actual score at rotation k
Track the maximum score mx and its corresponding rotation ans
Since we iterate from small to large k, we automatically get the smallest k when there are ties

Time Complexity: O(n) - We iterate through the array twice (once to build the difference array, once to find the maximum)

Space Complexity: O(n) - For the difference array

The elegance of this approach lies in converting a seemingly O(n²) problem (checking n rotations with n elements each) into an O(n) solution by focusing on when each element's contribution changes rather than recalculating everything from scratch.

Example Walkthrough

Let's walk through the solution with nums = [1, 0, 3, 2].

Step 1: Initialize difference array

d = [0, 0, 0, 0]

Step 2: Process each element to find contribution intervals

For element at index 0, value 1:

Start contributing: l = (0 + 1) % 4 = 1
Stop contributing: r = (4 + 0 + 1 - 1) % 4 = 0
Update: d[1] += 1, d[0] -= 1
Result: d = [-1, 1, 0, 0]

For element at index 1, value 0:

Start contributing: l = (1 + 1) % 4 = 2
Stop contributing: r = (4 + 1 + 1 - 0) % 4 = 2
Update: d[2] += 1, d[2] -= 1
Result: d = [-1, 1, 0, 0] (no net change at index 2)

For element at index 2, value 3:

Start contributing: l = (2 + 1) % 4 = 3
Stop contributing: r = (4 + 2 + 1 - 3) % 4 = 0
Update: d[3] += 1, d[0] -= 1
Result: d = [-2, 1, 0, 1]

For element at index 3, value 2:

Start contributing: l = (3 + 1) % 4 = 0
Stop contributing: r = (4 + 3 + 1 - 2) % 4 = 2
Update: d[0] += 1, d[2] -= 1
Result: d = [-1, 1, -1, 1]

Step 3: Find maximum score by scanning difference array

Starting with s = 0, mx = -1, ans = 4:

k=0: s = 0 + (-1) = -1. Since -1 ≤ -1, no update
k=1: s = -1 + 1 = 0. Since 0 > -1, update mx = 0, ans = 1
k=2: s = 0 + (-1) = -1. Since -1 ≤ 0, no update
k=3: s = -1 + 1 = 0. Since 0 ≤ 0, no update

Result: The highest running sum is 0, first reached at k = 1, so the function returns 1.

Why the running sums are not the actual scores: An interval [left, right) that wraps around the end of the array (where right <= left) is marked only with +1 at left and -1 at right. The prefix sum then misses the part of the interval that lies in [0, right), which lowers every rotation's sum by exactly 1 for that element. Elements 0 and 2 have wrapping intervals, and element 1 (value 0, which scores at every rotation) has left == right, so its marks cancel. Each of these three elements lowers every running sum by the same constant 1, so the running sum at each k equals the actual score minus 3. A constant shift does not change which k has the largest value, so the answer is still correct.

Verification against actual scores:

k=0: [1, 0, 3, 2] → indices 1 and 3 score → 2 points (running sum -1, plus 3)
k=1: [0, 3, 2, 1] → indices 0, 2, 3 score → 3 points (running sum 0, plus 3)
k=2: [3, 2, 1, 0] → indices 2 and 3 score → 2 points (running sum -1, plus 3)
k=3: [2, 1, 0, 3] → indices 1, 2, 3 score → 3 points (running sum 0, plus 3)

The maximum score is 3, reached first at k = 1, which matches the returned answer.

Solution Implementation

1class Solution:
2    def bestRotation(self, nums: List[int]) -> int:
3        """
4        Find the rotation index K that maximizes the score.
5        Score is calculated as the count of elements where nums[i] <= i after rotation.
6      
7        Args:
8            nums: List of integers to rotate
9          
10        Returns:
11            The rotation index K that gives the maximum score
12        """
13        n = len(nums)
14      
15        # Initialize variables to track the best rotation
16        max_score = -1
17        best_rotation = n
18      
19        # Use difference array to efficiently track score changes
20        # diff[k] represents the change in score when rotating by k positions
21        diff = [0] * n
22      
23        # For each element, calculate the range of rotations where it contributes to the score
24        for index, value in enumerate(nums):
25            # Calculate the rotation range where nums[index] contributes 1 point
26            # After k rotations, element at index i moves to position (i - k + n) % n
27            # We need: value <= (index - k + n) % n, which means k is in range [left, right)
28          
29            # Start of valid rotation range (inclusive)
30            left = (index + 1) % n
31          
32            # End of valid rotation range (exclusive)
33            # Derived from: value <= (index - k + n) % n
34            right = (n + index + 1 - value) % n
35          
36            # Mark the range in the difference array
37            diff[left] += 1
38            diff[right] -= 1
39      
40        # Use prefix sum to calculate actual scores for each rotation
41        current_score = 0
42        for rotation_k, delta in enumerate(diff):
43            current_score += delta
44          
45            # Update the best rotation if current score is better
46            if current_score > max_score:
47                max_score = current_score
48                best_rotation = rotation_k
49      
50        return best_rotation
51

1class Solution {
2    public int bestRotation(int[] nums) {
3        int n = nums.length;
4      
5        // Difference array to track score changes at each rotation
6        int[] scoreDelta = new int[n];
7      
8        // For each element, calculate the range of rotations where it contributes a point
9        for (int i = 0; i < n; ++i) {
10            // Left boundary: rotation where element starts contributing to score
11            // This happens when the element moves to index 0 (rotation = i + 1)
12            int leftBoundary = (i + 1) % n;
13          
14            // Right boundary: rotation where element stops contributing to score
15            // Element contributes when: newIndex >= value
16            // newIndex = (i - k + n) % n, so we need (i - k + n) % n >= nums[i]
17            // This gives us k <= i + 1 - nums[i] (mod n)
18            int rightBoundary = (n + i + 1 - nums[i]) % n;
19          
20            // Mark the range [leftBoundary, rightBoundary) using difference array
21            scoreDelta[leftBoundary]++;
22            scoreDelta[rightBoundary]--;
23        }
24      
25        // Find the rotation with maximum score using prefix sum
26        int maxScore = -1;
27        int currentScore = 0;
28        int bestRotation = n;  // Initialize with n (will be overwritten)
29      
30        for (int rotation = 0; rotation < n; ++rotation) {
31            // Update current score by applying the delta
32            currentScore += scoreDelta[rotation];
33          
34            // Track the rotation with the highest score
35            // In case of tie, we keep the smallest rotation index
36            if (currentScore > maxScore) {
37                maxScore = currentScore;
38                bestRotation = rotation;
39            }
40        }
41      
42        return bestRotation;
43    }
44}
45

1class Solution {
2public:
3    int bestRotation(vector<int>& nums) {
4        int n = nums.size();
5      
6        // Initialize variables to track the maximum score and best rotation
7        int maxScore = -1;
8        int bestK = n;
9      
10        // Difference array to track score changes at each rotation k
11        vector<int> scoreDelta(n);
12      
13        // For each element, calculate the range of k values where it contributes to the score
14        for (int i = 0; i < n; ++i) {
15            // Calculate the left boundary: rotation where nums[i] starts contributing
16            // When k = i+1, element at index i moves to position n-1
17            int leftBoundary = (i + 1) % n;
18          
19            // Calculate the right boundary: last rotation where nums[i] still contributes
20            // Element contributes when new_index >= nums[i]
21            // new_index = (i - k + n) % n >= nums[i]
22            // Solving for k: k <= (i + 1 - nums[i] + n) % n
23            int rightBoundary = (n + i + 1 - nums[i]) % n;
24          
25            // Mark the range [leftBoundary, rightBoundary) using difference array
26            ++scoreDelta[leftBoundary];
27            --scoreDelta[rightBoundary];
28        }
29      
30        // Calculate cumulative scores and find the rotation with maximum score
31        int currentScore = 0;
32        for (int k = 0; k < n; ++k) {
33            currentScore += scoreDelta[k];
34          
35            // Update best rotation if current score is higher
36            if (currentScore > maxScore) {
37                maxScore = currentScore;
38                bestK = k;
39            }
40        }
41      
42        return bestK;
43    }
44};
45

1function bestRotation(nums: number[]): number {
2    const n = nums.length;
3  
4    // Initialize variables to track the maximum score and best rotation
5    let maxScore = -1;
6    let bestK = n;
7  
8    // Difference array to track score changes at each rotation k
9    const scoreDelta: number[] = new Array(n).fill(0);
10  
11    // For each element, calculate the range of k values where it contributes to the score
12    for (let i = 0; i < n; i++) {
13        // Calculate the left boundary: rotation where nums[i] starts contributing
14        // When k = i+1, element at index i moves to position n-1
15        const leftBoundary = (i + 1) % n;
16      
17        // Calculate the right boundary: last rotation where nums[i] still contributes
18        // Element contributes when new_index >= nums[i]
19        // new_index = (i - k + n) % n >= nums[i]
20        // Solving for k: k <= (i + 1 - nums[i] + n) % n
21        const rightBoundary = (n + i + 1 - nums[i]) % n;
22      
23        // Mark the range [leftBoundary, rightBoundary) using difference array
24        scoreDelta[leftBoundary]++;
25        scoreDelta[rightBoundary]--;
26    }
27  
28    // Calculate cumulative scores and find the rotation with maximum score
29    let currentScore = 0;
30    for (let k = 0; k < n; k++) {
31        currentScore += scoreDelta[k];
32      
33        // Update best rotation if current score is higher
34        if (currentScore > maxScore) {
35            maxScore = currentScore;
36            bestK = k;
37        }
38    }
39  
40    return bestK;
41}
42

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of two main parts:

First loop iterates through all elements in nums to calculate difference array values - O(n) operations
Second loop iterates through the difference array diff to find the maximum prefix sum - O(n) operations

Each operation inside both loops (including modulo calculations and array updates) takes O(1) time. Therefore, the overall time complexity is O(n) + O(n) = O(n).

Space Complexity: O(n)

The algorithm uses additional space for:

Difference array diff of size n - O(n) space
A few scalar variables (max_score, best_rotation, current_score, left, right) - O(1) space

The total auxiliary space used is O(n) + O(1) = O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Splitting a Wrapping Range Into Two Ranges by Hand

The Problem: When right <= left, the range of good rotations wraps around: it is [left, n) together with [0, right). It is tempting to treat this as a bug and add special handling. The extra marking is not needed for correctness, because the missing [0, right) part only lowers every running sum by the same constant 1, and a constant shift does not change which k has the maximum.

Equivalent Implementation (extra work, same answer):

if left <= right:
    diff[left] += 1
    diff[right] -= 1
else:
    # Wrapping range: [left, n) plus [0, right)
    diff[left] += 1
    diff[0] += 1
    diff[right] -= 1

This version makes the running sums equal the true scores, which helps when the score itself is needed, but it returns the same k.

Solution Used:

# Mark only the start and end; wrapping ranges shift all sums by a constant
diff[left] += 1
diff[right] -= 1

The real requirement that follows from this is in Pitfall 4: since the running sums can be shifted down, they are relative values and can be zero or negative.

Pitfall 2: Off-by-One Error in Range Calculation

The Problem: The formula for calculating the right boundary (n + i + 1 - v) % n is derived from the inequality v <= (i - k + n) % n. A common mistake is forgetting the +1 or using incorrect boundary logic.

Incorrect Implementation:

# Wrong: Missing the +1
right = (n + i - v) % n  # Ends the range one rotation too early

# Or wrong: Using inclusive end instead of exclusive
right = (n + i - v) % n
diff[right + 1] -= 1  # This could cause index out of bounds

Correct Solution:

# Correct: The range is [left, right) where right is exclusive
left = (i + 1) % n
right = (n + i + 1 - v) % n  # Note the +1 here
diff[left] += 1
diff[right] -= 1  # Mark the end of the range (exclusive)

Pitfall 3: Forgetting to Handle the Case When `v > n`

The Problem: The problem guarantees 0 <= nums[i] < n, so the solution does not need this check. In a variant where values can exceed the largest index (v > n - 1), such an element can never score at any rotation. For v = n the formula gives right == left and the marks cancel, but for v > n it marks a range of rotations that does not exist, so the element must be skipped.

Incorrect Implementation:

# Wrong only if values larger than n can appear
for i, v in enumerate(nums):
    left = (i + 1) % n
    right = (n + i + 1 - v) % n  # Could give unexpected results if v > n
    diff[left] += 1
    diff[right] -= 1

Correct Solution:

for i, v in enumerate(nums):
    # Skip elements that can never contribute
    if v >= n:
        continue
  
    left = (i + 1) % n
    right = (n + i + 1 - v) % n
    diff[left] += 1
    diff[right] -= 1

Pitfall 4: Initializing Best Score Incorrectly

The Problem: The running sums are shifted down by a constant (see Pitfall 1), so they can be zero or negative even when the real scores are positive. Starting with max_score = 0 and best_rotation = 0 then skips a rotation whose running sum is 0 and returns the wrong index. For nums = [2, 5, 3, 4, 5, 2], the running sums are [-2, -1, 0, 0, 0, 0] (the real scores are [1, 2, 3, 3, 3, 3]), so this version never updates and returns 0 instead of 2.

Incorrect Implementation:

max_score = 0  # Wrong: running sums can be 0 or negative
best_rotation = 0

for k, delta in enumerate(diff):
    current_score += delta
    if current_score > max_score:  # This might never trigger
        max_score = current_score
        best_rotation = k

Correct Solution:

max_score = -1  # Start with -1 to ensure first valid score is captured
best_rotation = n  # Or 0, but should be set on first iteration

for k, delta in enumerate(diff):
    current_score += delta
    if current_score > max_score:
        max_score = current_score
        best_rotation = k

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which of these pictures shows the visit order of a depth-first search?

I don't know

798. Smallest Rotation with Highest Score

Problem Description

How We Pick the Algorithm

Why Prefix Sum?

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Common Pitfalls

Pitfall 1: Splitting a Wrapping Range Into Two Ranges by Hand

Pitfall 2: Off-by-One Error in Range Calculation

Pitfall 3: Forgetting to Handle the Case When v > n

Pitfall 4: Initializing Best Score Incorrectly

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Recommended Readings

Pitfall 3: Forgetting to Handle the Case When `v > n`