We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Smallest Rotation with Highest Score

Number: 814

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an array of integers, you are allowed to rotate the array by a non‐negative integer k. After rotating, each index i that has a value less than or equal to i earns one point. The goal is to find the rotation index k that maximizes the total score. If multiple rotations result in the same highest score, return the smallest k.

Key Insights

  • Rotating the array shifts the positions of each element; therefore, whether an element contributes to the score depends on its new index.
  • Instead of re‐computing the score from scratch for each possible rotation (which would be too slow), use a difference array (or prefix sum technique) to track how the score changes with rotation.
  • For each element, determine an interval of rotations where it stops contributing (or starts contributing) and update a difference array accordingly.
  • Finally, iterate over all rotations by accumulating the differences to obtain the score change relative to the initial configuration, and pick the rotation with the highest score.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the array, since we process each element once and then perform a single pass over the difference array. Space Complexity: O(n), for storing the difference array.

Solution

We solve the problem by first computing the initial score when k = 0 (i.e. no rotation). Next, rather than simulating every rotation, we precompute how each element’s contribution changes as k increases using a difference array.

For each index i with value nums[i]:

  1. The element is initially at index i. After a rotation of k positions (yielding a new index of (i - k + n) mod n), this element contributes a point if new_index >= nums[i].
  2. Determine the interval of rotations k for which the element stops contributing. This interval can be found by solving: (i - k + n) mod n >= nums[i].
  3. Use modular arithmetic to calculate the starting and ending points of the interval where the contribution changes. Update the difference array so that when we compute the prefix sum over all k, we obtain the score for each rotation.

Once the difference array is built, iterate over k = 0 to n-1, keeping track of the maximum score seen and the corresponding smallest k.

This trick avoids recomputing the score from scratch for each rotation and provides an O(n) time solution.

Code Solutions

# Python solution for Smallest Rotation with Highest Score
def bestRotation(nums):
    n = len(nums)
    diff = [0] * (n + 1)
    # Process each element to determine how its contribution to the score changes with rotations.
    for i, num in enumerate(nums):
        # Calculate the start index where this element stops contributing a point.
        low = (i - num + 1 + n) % n
        # Calculate the end index (one past the last rotation where it does contribute)
        high = (i + 1) % n
        diff[low] += 1
        diff[high] -= 1
        # If the interval wraps around, adjust the difference array accordingly.
        if low > high:
            diff[0] += 1

    best_k = 0
    current_score = 0
    max_score = -1
    # Evaluate the score for each rotation using prefix sum.
    for k in range(n):
        current_score += diff[k]
        if current_score > max_score:
            max_score = current_score
            best_k = k
    return best_k

# Example usage:
nums = [2,3,1,4,0]
print(bestRotation(nums))  # Expected output: 3
← Back to All Questions