798. Smallest Rotation with Highest Score

HardArrayPrefix Sum
Leetcode Link

Problem Description

The problem provides an array nums and asks to find the best rotation index k that yields the highest score after rotating the array. When an array is rotated k times, the elements are shifted in such a way that the element at index k moves to index 0, the element at index k+1 moves to index 1, and so on until the element at index 0 moves to index n-k where n is the length of the array.

The score is calculated based on the condition that each element that is less than or equal to its new index after the rotation gets one point. The goal is to determine the rotation index k that maximizes this score. If there are multiple rotation indices yielding the same maximum score, the smallest index k should be returned.

For example, take nums = [2,4,1,3,0]. When we rotate nums by k = 2, the result is [1,3,0,2,4]. In this rotated array, the elements at indices 2, 3, and 4 (which are 0, 2, and 4 respectively) are less than or equal to their indices, thereby each contributing one point to the score. Therefore, the total score is 3.

Intuition

The intuition behind the given solution is to leverage differences in the array to efficiently calculate scores for all possible rotations without performing each rotation explicitly. A key observation is that when rotating the array, certain elements will start to contribute to the score when they are moved to particular positions. Similarly, they'll stop contributing to the score when rotated past a certain point.

The solution uses a difference array d, which tracks changes in the score potential as the array is virtually rotated. The elements at d[k] represents the net change in score when rotating from k-1 to k. This allows us to compute the score for each rotation using a running total rather than recalculating the entire score each time.

For each value in the nums array, we identify the range of rotation indices for which that value will contribute to the score. This is done by using modular arithmetic to ensure indices wrap around properly:

  • l = (i + 1) % n is the first index that the number at the current index i will not contribute to the score after rotation, so we increment the score change at index l.
  • r = (n + i + 1 - v) % n is the first index where the number will start to contribute to the score, so we decrement the score change at index r.

After populating the difference array, we can iterate through it, keeping a running total (s). Whenever we get a running total that is higher than the current maximum (mx), we update the maximum and store the index k, which would be our answer.

Thus, the solution efficiently finds the best rotation that yields the highest score by intelligently tracking when each number starts and stops contributing to the score, rather than performing and checking each rotation one by one.

Learn more about Prefix Sum patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following problems can be solved with backtracking (select multiple)

Solution Approach

The solution provided uses a smart approach with help of a difference array to track the change in score with each possible rotation. Here's a breakdown of the implementation:

  1. Initialize variables: We start by initializing a few variables. n stores the length of the array, mx is used to keep track of the maximum score encountered so far (initialized to -1 since the score can't be negative), and ans holds the rotation index that yields the maximum score (initialized to n to ensure we return the smallest index in case of a tie). We also initialize a difference array d of size n, with all elements set to 0.

  2. Populate the difference array: Going through each element in nums with their index i and value v, we calculate two values l and r using modular arithmetic to wrap around the array.

    • l = (i + 1) % n: This value represents the rotation index right after the element v at index i would stop contributing a point. Therefore, we increment the score change at this index with d[l] += 1.
    • r = (n + i + 1 - v) % n: This value represents the rotation index when the element v starts contributing a point. We then decrement the score change at this index with d[r] -= 1.

  3. Find the best rotation: To find the rotation yielding the highest score, we track a running total s. We iterate through the difference array d, adding d[k] to s for each index k. Whenever the running total exceeds the current maximum score mx, we update mx with this new score and set ans to the current index k. This process takes advantage of the fact that d[k] represents the net change in score when "rotating" from k-1 to k, allowing us to efficiently calculate the score for each potential rotation.

  4. Return the optimal rotation index: After iterating through the entire difference array and updating mx and ans accordingly, we finally return ans. This index corresponds to the smallest rotation index k that achieves the maximum score.

This algorithm leverages the properties of difference arrays to calculate the cumulative effect of each rotation on the score without exhaustive computation, resulting in an efficient solution. The use of modular arithmetic ensures that index values are correctly wrapped around the boundaries of the array, which is necessary for the rotations.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Example Walkthrough

Let's go through a small example to illustrate the solution approach using the array nums = [2, 3, 1, 4, 0].

  1. Initialize variables: The length of the array n is 5. We initialize mx as -1, ans as 5, and a difference array d of size 5 with all elements as 0.

  2. Populate the difference array: We process each element to determine when it starts and stops contributing to the score.

    • For nums[0] = 2, l = (0 + 1) % 5 = 1 and r = (5 + 0 + 1 - 2) % 5 = 4. So d[1] gets incremented by 1 and d[4] gets decremented by 1.
    • Repeat the process for all other elements in nums:
      • nums[1] = 3: l = 2, r = 0 (since after 3 rotations, index 1 will be at position 3) => d[2]++, d[0]--
      • nums[2] = 1: l = 3, r = 2 => d[3]++, d[2]--
      • nums[3] = 4: l = 4, r = 1 => d[4]++, d[1]--
      • nums[4] = 0: l = 0, r = 4 => d[0]++, no change at r since it wraps around to the same position.

  3. Find the best rotation: We now have the difference array d = [1, 0, 0, 1, -1] after processing all elements. Starting with a score s = 0, we iterate through d and track the running total.

    • At k = 0, the score s becomes s + d[0] = 0 + 1 = 1. Since s is greater than mx (-1), we update mx = 1 and ans = 0.
    • At k = 1, the score does not change (s + d[1] = 1), and since mx is not exceeded, we do not update mx or ans.
    • At k = 2, again, the score does not change (s + d[2] = 1).
    • At k = 3, the score increases to s + d[3] = 1 + 1 = 2. We update mx = 2, and ans = 3.
    • Finally, at k = 4, the score decreases to s + d[4] = 2 - 1 = 1. Since mx is not exceeded, we do not update it.

  4. Return the optimal rotation index: After processing the difference array, we find that the maximum score is mx = 2 achieved at ans = 3. Therefore, we return ans = 3 as the optimal rotation index for the maximum score.

Using this example, we've shown how the difference array helps avoid calculating each possible rotation's score from scratch, instead using differences to achieve an efficient computation of the best rotation index.

Solution Implementation

1class Solution:
2    def bestRotation(self, nums: List[int]) -> int:
3        n = len(nums)
4        max_score, best_k = -1, 0  # Initialize max_score and best_k to hold the highest score and best k value
5        delta = [0] * n  # Create a delta array to keep track of score changes
6      
7        # Walk through each number in the array to calculate score changes
8        for index, value in enumerate(nums):
9            left = (index + 1) % n
10            right = (n + index + 1 - value) % n
11
12            # Increment score for this position and decrement at the position where it starts losing scores
13            delta[left] += 1
14            delta[right] -= 1
15            if left > right:  # If the range wraps around, we increment the first element too
16                delta[0] += 1
17      
18        score = 0  # Keep track of the aggregate score so far
19        # Iterate through delta array to find the k with the maximum score
20        for k, change in enumerate(delta):
21            score += change  # Update the score by the current change
22            # If the current score is greater than max_score, update it and record the current k
23            if score > max_score:
24                max_score = score
25                best_k = k
26      
27        return best_k  # Return the k index that gives the maximum score
28
1class Solution {
2    public int bestRotation(int[] nums) {
3        int n = nums.length; // Get the length of the array 'nums'
4        int[] delta = new int[n]; // Initialize an array to track the change in scores for each rotation 'k'
5      
6        for (int i = 0; i < n; ++i) {
7            // Calculate the lower bound (inclusive) of the range for which the number nums[i] gains a score if 'k' is the rotation.
8            int lower = (i + 1) % n; 
9            // Calculate the upper bound (exclusive) of the range for which the number nums[i] gains a score if 'k' is the rotation.
10            int upper = (n + i + 1 - nums[i]) % n;
11            // Increment the score change at the lower bound
12            ++delta[lower];
13            // Decrement the score change at the upper bound as it is exclusive
14            --delta[upper]; 
15          
16            // If after rotating, the number wraps around the array, decrease score change at index 0
17            if (lower > upper) {
18                ++delta[0];
19            }
20        }
21      
22        int maxScore = -1; // Initialize maxScore to track the maximum score
23        int score = 0; // Score for the current rotation 'k'
24        int bestRotationIndex = 0; // Initialize bestRotationIndex to track the best rotation which gives maxScore
25      
26        for (int k = 0; k < n; ++k) {
27            // Accumulate score changes for rotation 'k'
28            score += delta[k];
29            // If the current rotation score is greater than maxScore, update maxScore and bestRotationIndex
30            if (score > maxScore) {
31                maxScore = score;
32                bestRotationIndex = k;
33            }
34        }
35      
36        // Return the index 'k' corresponding to the best rotation of the array that maximizes the score
37        return bestRotationIndex;
38    }
39}
40
1class Solution {
2public:
3    int bestRotation(vector<int>& nums) {
4        int n = nums.size();         // Store the size of the input vector nums
5        int maxScore = -1;           // Initialize the variable to keep track of the maximum score
6        int bestK = n;               // Initialize the variable to store the best rotation index k
7        vector<int> diffs(n);        // Initialize a difference array to track score changes
8      
9        for (int i = 0; i < n; ++i) {
10            int left = (i + 1) % n;                         // Calculate the left index for score increment
11            int right = (n + i + 1 - nums[i]) % n;          // Calculate the right index for score decrement
12          
13            diffs[left]++;                                  // Increment score at position 'left'
14            diffs[right]--;                                 // Decrement score at position 'right'
15            if (left > right) {                             // If the range wraps around the array
16                diffs[0]++;                                 // Increment score at the beginning of the array
17            }
18        }
19      
20        int score = 0;              // Initialize the score variable for the accumulative score sum
21        for (int k = 0; k < n; ++k) {
22            score += diffs[k];       // Update the score by adding the current difference
23          
24            if (score > maxScore) {  // Update maxScore and bestK if a higher score is found
25                maxScore = score;
26                bestK = k;
27            }
28        }
29      
30        // Return the best rotation index 'k' with the highest score
31        return bestK;
32    }
33};
34
1// Global function that returns the best rotation for the maximum score
2function bestRotation(nums: number[]): number {
3    const n: number = nums.length; // Store the length of the input array nums
4    let maxScore: number = -1;     // Initialize the variable for tracking the maximum score
5    let bestK: number = n;         // Initialize the variable to store the best rotation index k
6    let diffs: number[] = new Array(n).fill(0); // Initialize a difference array with zeros to track score changes
7
8    for (let i = 0; i < n; ++i) {
9        let left: number = (i + 1) % n;              // Calculate the left index for score increment
10        let right: number = (n + i + 1 - nums[i]) % n; // Calculate the right index for score decrement
11      
12        diffs[left]++;   // Increment score at position 'left'
13        diffs[right]--;  // Decrement score at position 'right'
14        if (left > right) {  // If the range wraps around the array
15            diffs[0]++;  // Increment score at the beginning of the array
16        }
17    }
18
19    let score: number = 0; // Initialize the score variable for the accumulative score sum
20    for (let k = 0; k < n; ++k) {
21        score += diffs[k];  // Update the score by adding the difference at index k
22      
23        if (score > maxScore) {  // If a higher score is found, update maxScore and bestK
24            maxScore = score;
25            bestK = k;
26        }
27    }
28
29    // Return the best rotation index 'k' with the highest score
30    return bestK;
31}
32
33// The function can then be used as follows:
34// let nums = [some array of numbers];
35// let result = bestRotation(nums);
36
Not Sure What to Study? Take the 2-min Quiz：

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Time and Space Complexity

The given Python code implements a function to determine the best rotation for an array such that the number of elements nums[i] that are not greater than their index i is maximized when the array nums is rotated.

Time Complexity:

The time complexity of the function is O(n), where n is the length of the array nums.

  1. The loop to calculate the difference array: This loop runs for n iterations, where n is the length of the array nums. Inside the loop, we calculate the changes for each rotation using modulo operations and update the difference array (d). Each update is a constant time operation. Therefore, this step takes O(n) time.

  2. The loop to find the best rotation: This loop also runs for n iterations. It iterates over the difference array, cumulatively adding the differences (s += t) to find the score for each rotation, and keeps track of the maximum score and the corresponding index (rotation). Since each iteration of the loop does a constant amount of work, this step is also O(n).

Thus, the overall time complexity of the function is O(n).

Space Complexity:

The space complexity of the function is O(n).

  • We maintain a difference array (d) of the same length as the nums array, which takes O(n) space.
  • Aside from the difference array, only a constant amount of extra space is used for variables to keep track of the maximum score, current score, and the best rotation.

Therefore, the total space used by the function is determined by the size of the difference array, which is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How does merge sort divide the problem into subproblems?

Recommended Readings

Prefix Sum

Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫