798. Smallest Rotation with Highest Score
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 indexi
will not contribute to the score after rotation, so we increment the score change at indexl
.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 indexr
.
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.
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:
-
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), andans
holds the rotation index that yields the maximum score (initialized ton
to ensure we return the smallest index in case of a tie). We also initialize a difference arrayd
of sizen
, with all elements set to 0. -
Populate the difference array: Going through each element in
nums
with their indexi
and valuev
, we calculate two valuesl
andr
using modular arithmetic to wrap around the array.l = (i + 1) % n
: This value represents the rotation index right after the elementv
at indexi
would stop contributing a point. Therefore, we increment the score change at this index withd[l] += 1
.r = (n + i + 1 - v) % n
: This value represents the rotation index when the elementv
starts contributing a point. We then decrement the score change at this index withd[r] -= 1
.
-
Find the best rotation: To find the rotation yielding the highest score, we track a running total
s
. We iterate through the difference arrayd
, addingd[k]
tos
for each indexk
. Whenever the running total exceeds the current maximum scoremx
, we updatemx
with this new score and setans
to the current indexk
. This process takes advantage of the fact thatd[k]
represents the net change in score when "rotating" fromk-1
tok
, allowing us to efficiently calculate the score for each potential rotation. -
Return the optimal rotation index: After iterating through the entire difference array and updating
mx
andans
accordingly, we finally returnans
. This index corresponds to the smallest rotation indexk
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through a small example to illustrate the solution approach using the array nums = [2, 3, 1, 4, 0]
.
-
Initialize variables: The length of the array
n
is 5. We initializemx
as -1,ans
as 5, and a difference arrayd
of size 5 with all elements as 0. -
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
andr = (5 + 0 + 1 - 2) % 5 = 4
. Sod[1]
gets incremented by 1 andd[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 atr
since it wraps around to the same position.
- For
-
Find the best rotation: We now have the difference array
d = [1, 0, 0, 1, -1]
after processing all elements. Starting with a scores = 0
, we iterate throughd
and track the running total.- At
k = 0
, the scores
becomess + d[0] = 0 + 1 = 1
. Sinces
is greater thanmx
(-1), we updatemx = 1
andans = 0
. - At
k = 1
, the score does not change (s + d[1] = 1
), and sincemx
is not exceeded, we do not updatemx
orans
. - At
k = 2
, again, the score does not change (s + d[2] = 1
). - At
k = 3
, the score increases tos + d[3] = 1 + 1 = 2
. We updatemx = 2
, andans = 3
. - Finally, at
k = 4
, the score decreases tos + d[4] = 2 - 1 = 1
. Sincemx
is not exceeded, we do not update it.
- At
-
Return the optimal rotation index: After processing the difference array, we find that the maximum score is
mx = 2
achieved atans = 3
. Therefore, we returnans = 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
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
.
-
The loop to calculate the difference array: This loop runs for
n
iterations, wheren
is the length of the arraynums
. 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. -
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 thenums
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.
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
Recommended Readings
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 Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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 Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.