LC-0798 Hard LeetCode

798. Smallest Rotation with Highest Score

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 52% Topics: Array, Prefix Sum

Reading material

Arrays & Hashing 12 min Prefix Sums & Difference Arrays 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

class Solution(object):
    def bestRotation(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        N = len(A)
        change = [1] * N
        for i in xrange(N):
            change[(i-A[i]+1)%N] -= 1
        for i in xrange(1, N):
            change[i] += change[i-1]
        return change.index(max(change))

Solution from kamyu104/LeetCode-Solutions · MIT