LeetCode : Smallest Rotation with Highest Score – Stokastik

LeetCode : Smallest Rotation with Highest Score – Stokastik

As we can see that, we can easily come up with a $O(N^2)$ solution. Rotate the array each time and compute the score. There are N possible rotations for an array of size N, and for each rotated position, computing the score for the array takes O(N) time complexity. Since the approach is very easy, we will not code this approach but will explore whether we can do better than $O(N^2)$.

What if we can find out the minimum and the maximum values of rotation, for which each element of the array will contribute towards a positive score ? For example, given the array

[2, 3, 1, 4, 0],

the minimum and maximum values for each position are as follows :

1st position (element = 2) : min rotation = 1 and max rotation = 3

Because if rotated 1 time, 2 will land up at index 4 and if rotated 3 times, 2 will land up at index 2. If rotated more than 3 or less than 1 time, then 2 will land up at an index 'm' for which m < 2.

[3, 1, 4, 0, 2] -> [1, 4, 0, 2, 3] -> [4, 0, 2, 3, 1]

Similarly, 2nd position (element = 3) : min rotation = 2 and max rotation = 3

Because if rotated 2 times, 3 will land up at index 4 and if rotated 3 times, 3 will land up at index 3. If rotated more than 3 or less than 2 times, then 3 will land up at an index 'm' for which m < 3.

[1, 4, 0, 2, 3] -> [4, 0, 2, 3, 1]

and so on.

Note that for the 3rd position (element = 1), it is already at a 'good' position (2 >= 1). It has two possible pairs of min and max rotation (0, 1) and (3, 4), because with 0 and 1 rotation it will land up at index 2 and 1 respectively, where both 2 >= 1 and 1 >= 1 satisfies. But for rotation 2, 1 will land up at index 0, where 0 < 1. If rotated 3 times or 4 times 1 will land up at indexes 4 and 3 respectively, where 4 >= 1 and 3 >= 1.

Thus for positions where the element is already contributing towards a positive score, such as 1 in the above case, there would be two disjoint pairs of min and max rotations possible.

The maximum possible number of min-max pairs would be 2N, e.g. [0,1,2,3,4]

If the element is 0, then it can be rotated any number of times and will contribute wherever it lands. Thus min rotation = 0 and max rotation = 4.

2 : [1, 3],

3 : [2, 3]

1 : [0, 1], [3, 4]

4 : [4, 4]

0 : [0, 4]

Then in order to find the rotation for which the score is maximum, we need to find the value of rotation for which the maximum number of elements contribute towards a score of 1.

In the above example, if k = 3 rotations, then the elements 2, 3, 1 and 0 contributes, from the above calculations. For k = 3, 4 does not contribute since it only contributes for a rotation of 4. Similarly for k = 1, [2, 1, 0] contributes, for k = 2, [2, 3, 0] contributes and k = 0, [1, 0] contributes. Thus we see that for k = 3, there are maximum contributions, i.e 4 elements.

How can we code this, so that the time complexity does not come out to be $O(N^2)$ ?

If we compute the min and max rotations for each element first and then for each rotation, compute the number of elements that contributes towards that rotation, it will be $O(N^2)$, since we need to look up each min-max rotation pair and then decide whether the element contributes or not and there are 2N possible min-max pairs.

We will use the fact that the min-max pairs are a range of indices. For example, if we have an array M of size N, with all elements set to 0 initially. Then whenever we encounter a min-max pair [a, b], we will increment the sub-array M[a : b] by 1. This signifies that, for all rotations between the values 'a' to 'b' (inclusive), we have found one more element.

Using the Numpy library of python, updating a range of contiguous array indices would take O(1) time, since they are contiguous in memory.

Read full article from LeetCode : Smallest Rotation with Highest Score – Stokastik