Two Python3 O(n) time and space AC solutions with picture explanation
I firstly maintain a counter to solve it and got TLE (I modified it into an AC one now and it\'s at the end of the post) , then I came up with the following sol
I firstly maintain a counter to solve it and got TLE (I modified it into an AC one now and it\'s at the end of the post) , then I came up with the following solution after the contest...\n\nLet `N=len(A)`, for each `i in range(N)` and `A[i]` we can know a range `[x, y]` so that from the `x-th` rotate to the `y-th` rotate it contributes to a point. \n\nThen we use two arrays `left` and `right`,  `left[i]` means `[i, N-1]th` rotations get the point,  `right[i]` means `[0, i]th` rotations get the point.\n\nSo there are 3 kinds of ranges:\n\n1. `[0, i]`, just update `right[i]+=1`\n2. `[i, N-1]`, just update `left[i]+=1`\n3. `[i, j]`, this is equal to `[0, i-1]` and `[j+1, N-1]` lose point, so update  `right[i-1]-=1` and `left[j+1]-=1`\n\nThen for `A[i]` and `i` there are `>`, `=`, `<` three situations. Just analyze them and update according to rules above.\n\nIn the following picture, valid rotation ranges are colored with black or red, and then update the ranges to the `left` and `right` array.\n\nNext, combine the `left` and `right` array to get the points.\n\nFor `i in [1 to N-1]`, `left[i]+=left[i-1]`\nFor `i in [N-2 to 0]`, `right[i]+=right[i+1]`\n\nThen `total[i]=left[i]+right[i]` is the point for `i-th` rotation.\n\nTime complexity analysis:\nFor each `i in [0, N]`, we just update `left` and `right`, both cost `O(1)`, so the loop cost `O(N)`.\nCalculating `total` also cost `O(N)`\nSo time complexity is `O(N)`\n\nSpace complexity analysis:\n`left` and `right` both `O(N)`\nSo space complexity is  `O(N)`\n\n\n\n![image](https://s3-lc-upload.s3.amazonaws.com/users/luckypants/image_1520745726.png)\n\n\n```\nclass Solution:\n    def bestRotation(self, A):\n        """\n        :type A: List[int]\n        :rtype: int\n        """\n        N = len(A)\n\n        left = [0]*N\n        right = [0]*N\n        \n        for i in range(N):\n            if A[i]>i:\n                right[i] += -1\n                if i+N-A[i]+1<N:\n                    left[i+N-A[i]+1] += -1\n            elif A[i]==i:\n                right[0] += 1\n                if i+1<N:\n                    left[i+1] += 1\n            else:\n                right[i-A[i]] += 1\n                if i+1<N:\n                    left[i+1] += 1\n            # print(left, right)\n        \n        for i in range(1, N):\n            left[i] += left[i-1]\n            right[N-1-i] += right[N-i]\n        \n        total = [left[i]+right[i] for i in range(N)]\n        \n        ret = -1\n        ma = -sys.maxsize\n        \n        # print(total)\n        for i in range(N):\n            if total[i]>ma:\n                ret = i\n                ma = total[i]\n\t\t\t\t\t\t\t\t\n        return ret\n```\n\t\t\t\t\nMy TLE Solution, it use a dictionary to maintain count of each `A[i]-i` value:\n\n```\nclass Solution:\n    def bestRotation(self, A):\n        """\n        :type A: List[int]\n        :rtype: int\n        """\n        N = len(A)\n        \n        arr = [A[i]-i for i in range(N)]\n        \n        counter = collections.Counter(arr)\n        max_points = 0\n        for k in counter:\n            if k<=0:\n                max_points += counter[k]\n        ret = 0\n        for i in range(1, N):\n            v = arr[i-1]+(i-1)\n            new_counter = collections.Counter()\n            for k in counter:\n                new_counter[k+1] = counter[k]\n            new_counter[v+1] -= 1\n            new_counter[v-(N-1)] += 1\n            counter = new_counter\n            points = 0\n            for k in counter:\n                if k<=0:\n                    points += counter[k]\n            if points>max_points:\n                ret = i\n                max_points = points\n        \n        return ret\n```\n\nIt use too much time to calculate `new_counter`, but in fact we can update the `threshold` instead of update the counter. Each time all other number is updated with `n+=1`, the rotated position is updated with `n-=(N-1)`, so if we make numbers not at rotated position unmoved, **relatively** just update rotated position with `n-=N` and update the threshold with `thres-=1`(Which is `1-i` in the following code). \n\nBoth time complexity and space complexity are also `O(N)`\n\nHere is the updated AC solution:\n\n```\nclass Solution:\n    def bestRotation(self, A):\n        """\n        :type A: List[int]\n        :rtype: int\n        """\n        N = len(A)\n        \n        arr = [A[i]-i for i in range(N)]\n        \n        counter = collections.Counter(arr)\n        max_points = 0\n        for k in counter:\n            if k<=0:\n                max_points += counter[k]\n        \n        ret = 0\n        \n        points = max_points\n\n        for i in range(1, N):\n            v = arr[i-1]\n                \n            counter[v] -= 1\n            \n            if v>1-i:\n                points += 1\n            counter[v-N] += 1\n            \n            points -= counter[1-i]\n            \n            if points>max_points:\n                ret = i\n                max_points = points\n        \n        return ret
[]