Smallest Rotation with Highest Score - Practice Coding Problems

Smallest Rotation with Highest Score - Problem

You are given an array nums. You can rotate it by a non-negative integer k so that the array becomes [nums[k], nums[k + 1], ... nums[nums.length - 1], nums[0], nums[1], ..., nums[k-1]].

Afterward, any entries that are less than or equal to their index are worth one point.

For example, if we have nums = [2,4,1,3,0], and we rotate by k = 2, it becomes [1,3,0,2,4]. This is worth 3 points because:

1 > 0 [no points]
3 > 1 [no points]
0 ≤ 2 [one point]
2 ≤ 3 [one point]
4 ≤ 4 [one point]

Return the rotation index k that corresponds to the highest score we can achieve if we rotated nums by it. If there are multiple answers, return the smallest such index k.

Input & Output

Example 1 — Basic Rotation

$ Input: nums = [2,4,1,3,0]

› Output: 3

💡 Note: Rotating by k=3 gives [3,0,2,4,1]. Score: 3>0 (no), 0≤1 (yes), 2≤2 (yes), 4>3 (no), 1≤4 (yes) = 3 points. This is optimal.

Example 2 — Multiple Optimal Solutions

$ Input: nums = [1,3,0,2,4]

› Output: 0

💡 Note: No rotation needed. Score: 1>0 (no), 3>1 (no), 0≤2 (yes), 2≤3 (yes), 4≤4 (yes) = 3 points. This equals other rotations but k=0 is smallest.

Example 3 — Edge Case Small Array

$ Input: nums = [1,1]

› Output: 1

💡 Note: k=0: [1,1] scores 1 point (1≤1). k=1: [1,1] scores 1 point (1≤1). Both equal, return k=1 since it's the only other option.

Constraints

1 ≤ nums.length ≤ 10⁵
0 ≤ nums[i] < nums.length

Visualization

Tap to expand

Understanding the Visualization

Input

Array [2,4,1,3,0] - find best rotation k

Process

Try rotations and count nums[i] ≤ i conditions

Output

Return k=3 with maximum score

Key Takeaway

🎯 Key Insight: Track score changes as rotation increases instead of recalculating from scratch

Asked in

G Google 15 f Facebook 8

The key insight is to avoid recalculating scores for each rotation by tracking when elements contribute points. The difference array approach efficiently computes all rotation scores in O(n) time by marking score changes. Best approach uses difference array: Time O(n), Space O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized with Difference Array	O(n)	O(n)	Use difference array to track score changes as we increment rotation k
Brute Force - Try All Rotations	O(n²)	O(1)	Try every possible rotation k and calculate the score for each

Optimized with Difference Array — Algorithm Steps

For each element, find the range of k values where it contributes a point
Use difference array to mark score changes at specific k values
Iterate through k values and track cumulative score changes
Return k with maximum score

Visualization

Tap to expand

Step-by-Step Walkthrough

Analyze Contributions

For each element, find k ranges where it scores

Difference Array

Mark start/end of contribution ranges

Prefix Sum

Calculate all scores in one pass

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int n) {
    if (n == 0) return 0;
    
    // Difference array to track score changes
    int* diff = (int*)calloc(n, sizeof(int));
    
    for (int i = 0; i < n; i++) {
        // Find the range of k where this element contributes a point
        int left = (i - nums[i] + 1 + n) % n;
        int right = i;
        
        if (left <= right) {
            diff[left]++;
            if (right + 1 < n) {
                diff[right + 1]--;
            }
        } else {
            diff[0]++;
            if (right + 1 < n) {
                diff[right + 1]--;
            }
            diff[left]++;
        }
    }
    
    // Calculate scores using prefix sum
    int maxScore = 0;
    int currentScore = 0;
    int bestK = 0;
    
    for (int k = 0; k < n; k++) {
        currentScore += diff[k];
        if (currentScore > maxScore) {
            maxScore = currentScore;
            bestK = k;
        }
    }
    
    free(diff);
    return bestK;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[10000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to analyze each element's contribution ranges, then one pass to compute all scores

✓ Linear Growth

Space Complexity

O(n)

Difference array of size n to track score changes at each rotation

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized with Difference Array — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler