A (hopefully) understandable explanation O(n)
This problem can be thought of as a transformation to a more well known problem. After we have the transformation, we can solve it effiently.\n\nDefinitions\nLe
This problem can be thought of as a transformation to a more well known problem. After we have the transformation, we can solve it effiently.\n\n**Definitions**\nLet A be the input array, and N be the number of elements in the array. Let A[i] denote the value at index i in input array A. And let K be the number of rotations.\n\n**The Transformation**\nFor every number in the  array, write the ranges which the value will yield a score of + 1.\n\n Example:\n A: [2, 3, 1, 4, 0]\n Range for 2: [1, 3] (Rotating the array for any value of 1 <= K <= 3 will give us a point for 2.\n Range for 3: [2, 3]\n Range for 1: [0, 1] and [3, 4]\n ... and so on\n \n After doing that, the value of K that gives the highest score is the value that is common to the most # of ranges. The question is how do we solve for that value? A simple approach would be to keep an array, called count, with indices from 0 to 4, and add 1 to each indice for every range that contains it. At the end the best value of k is  the indice for which count has the largest value.\n \n Example:\n count would look like this if we added + 1 for range [1, 3]: count [0, 1, 1, 1, 0]. We would continue to add for every range. So after adding range [2, 3], count would look like [0, 1,  2, 2, 0] ... and so on.\n \n But this would be O(n^2). We can improve this by making a simple adaptation. To represent some range [a, b] we can instead add +1 to only the indice a, and subtract 1 to the last b + 1 (if it exists). This would mean that we add +1 to every index >= a, and subtract -1 to every index b + 1. After doing this for every range, we can accumate from the front, we should get the same array count, as we did with out n^2 version.\n \n```\n class Solution(object):\n    def bestRotation(self, A):\n        """\n        :type A: List[int]\n        :rtype: int\n        """\n        count = [0]*len(A)\n        for i in range(len(A)):\n            if A[i] <= i:\n                mini = 0\n                maxi = i - A[i]\n                count[mini] += 1\n                if maxi + 1 < len(A): count[maxi + 1] += -1\n                if i + 1 < len(A): count[i+1] += 1\n            else:\n                if A[i] == len(A):\n                    continue #no valid range\n                mini = i + 1\n                maxi = len(A) - (A[i] - i)\n                print(mini, maxi)\n                count[mini] += 1\n                if maxi + 1 < len(A): count[maxi + 1] += -1\n        for i in range(1, len(A)):\n            count[i] += count[i-1]\n        return count.index(max(count))\n                \n                \n                    \n```\n 
[]