Problem statement

https://leetcode.com/problems/smallest-rotation-with-highest-score/

Solution 1

One solution is to use SortedList: on the first moment of time we need to check how many elements there in [A[i] - i] such that they are <= 0. When we need have numbers [A[i] - i + 1] and we need to find how many of them <= 0, which is equivalent to find how many numbers from [A[i] - i] are <= -1 where we updated one element A[0] -> A[0] - n. Then we do it again and again.

Complexity

Time complexity is O(n log n), space is O(n).

Code

from sortedcontainers import SortedList

class Solution:
    def bestRotation(self, A):
        B = [a - i for i,a in enumerate(A)]
        n, ans, SList = len(A), (0, -1), SortedList(B)

        for i in range(n):
            ans = max(ans, (SortedList.bisect(SList, -i), -i))
            SList.remove(B[i])
            SList.add(B[i]-n)
            
        return -ans[1]

Solution 2

There is also O(n) smart solution, using intervals: note, that for every number A[i] there will be continuous interval of K for which it will give us a point (or continuous but with transition n-1 -> 0). So, now we have the following problem: we have several intervals and we need to find the first index with maximum number of overlappings. We can find that for i-th point interval will be [(i+1)\%n, (i-A[i])\%n], so we use trick with cumulative sums: for [a, b] we increase a-th element by 1 and decrease (b+1)-th element by one.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def bestRotation(self, A):
        n = len(A)
        good = [0]*n
        for i in range(n):
            beg, end = (i+1)%n, (i-A[i]+1)%n
            good[end] -= 1
            good[beg] += 1
        
        t = list(accumulate(good))
        return t.index(max(t))

Remark

Moreover, it is not really necessary to update beg on each iteration: it will be updated exactly $n$ times for each position, so we can start with good = [1]*n.