798: Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n\nn = len(nums)\nchange = [1] * n\n\n\nHere, we find the length n of the 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n```\nn = len(nums)\nchange = [1] * n\n```\n\nHere, we find the length n of the nums array.\nWe initialize a change list of the same length filled with ones. This list represents the difference in scores for each rotation k.\n\n```\nfor i, num in enumerate(nums):\n    change[(i - num + 1) % n] -= 1\n```\n\nWe iterate over each number num at index i in nums.\nIf a number num at index i is rotated to the first position (index 0), it would need i + 1 rotations. Hence, to represent the change in score when num is moved to index 0, we access change at position (i - num + 1) % n and decrement it by 1.\n\n```\nfor i in range(1, n):\n    change[i] += change[i - 1]\n```\n\nHere, we are using the prefix sum technique to accumulate the score changes for each rotation. So, the change list now represents the total score for each rotation k.\n\n```\nreturn change.index(max(change))\n```\n\nFinally, we return the index k (rotation) that gives the maximum score.\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution:\n  def bestRotation(self, nums: List[int]) -> int:\n\n    n = len(nums)\n    change = [1] * n\n    \n    for i, num in enumerate(nums):\n        change[(i - num + 1) % n] -= 1\n        \n    for i in range(1, n):\n        change[i] += change[i - 1]\n        \n    return change.index(max(change))\n\n```
['Array', 'Prefix Sum', 'Python', 'Python3']