[Python3] Explanation - Runtime And Space Analysis - O(n) Time/Space
Explanation\nWe use two hashtables rotation_to_valids and rotation_to_invalids to keep track of the number of elements which become valid or invalid after a giv
**Explanation**\nWe use two hashtables `rotation_to_valids` and `rotation_to_invalids` to keep track of the number of elements which become valid or invalid after a given number of rotations as the index. Since the result of each rotation after `len(A) - 1` rotations repeats (`len(A)` rotations lead to the unmodified input list again), we just need to cover the first `len(A) - 1` rotations.\n\nIn the first step, we examine every element in the input list (`i` is the current position of the element). If the element is already on a valid position, the counter for valid elements after `0` rotations (`rotation_to_valids[0]`) is increased by one. It will become invalid if it reaches the position left from its value which requires `i - A[i] + 1` shifts to the left (rotations), therefore `rotation_to_invalids[ i - A[i] + 1 ] += 1`. However, it will become valid again if it reaches the last position since every element in the input list is smaller or equal to the last index. In order to reach the last position, `i + 1` rotations are required, therefore `rotation_to_valids[ i + 1 ] += 1`.\nIf the element is not on a valid position which means that `A[i] > i`, it will stay invalid until `i + 1` rotations have been made, therefore `rotation_to_valids[ i + 1 ] += 1`. It will become invalid again, if `i + 1 + len(A) - A[i]` rotations have been made (`i + 1` rotations so the element will be on the last position, plus `len(A) - A[i]` rotations until its on the position left from its value).\nBoth hashtables are of size `len(A) + 1` because some elements will become valid/invalid the second time after performing at maximum `len(A)` rotations. They will not be examined later but considering them now in terms of the hashtables will make the code more compact.\n\nIn the last step, we execute all `len(A) - 1` rotations and add the number of elements which have become valid and subtract the ones which have become invalid to the number of valid elements before the rotation has been executed. The first rotation sequence which will lead to the highest number of valid elements (score) will be stored and returned.\n_____________________________________\n**Time Complexity**\n`O(n)` for looping through the number of elements twice.\n_____________________________________\n**Space Complexity**\n`O(n)` for storing the number of valid and invalid elements after `0 <= i < n` rotations.\n_____________________________________\n**Python Implementation**\n```\nclass Solution:\n    def bestRotation(self, A: List[int]) -> int:\n        rotation_to_valids = [0]*(len(A) + 1)\n        rotation_to_invalids = [0]*len(rotation_to_valids)\n        valids = 0\n        max_valids = 0\n        \n        for i in range(len(A)):\n            if A[i] <= i:\n                rotation_to_valids[0] += 1\n                rotation_to_invalids[i - A[i] + 1] += 1\n            else:\n                rotation_to_invalids[i + 1 + len(A) - A[i]] += 1\n\n            rotation_to_valids[i + 1] += 1  \n\n        for i in range(len(A)):\n            valids += rotation_to_valids[i] - rotation_to_invalids[i]\n             \n            if max_valids < valids:\n                max_valids = valids\n                ret = i\n            \n        return ret   \n```
[]