Efficient JS solution - Line sweep O(n) (Beat 100% time)
\n\nPro tip: \u6211\u7684\u732B\u4E0D\u7231\u6211 \uD83D\uDC9C\uD83D\uDE3E\n\nFor each cycle shift from k - 1 to k, we should imagine it as a process of:\n1. Re
![image.png](https://assets.leetcode.com/users/images/551a71b1-befe-44fc-a33e-4ec2a9f2a75d_1706809245.6174912.png)\n\nPro tip: \u6211\u7684\u732B\u4E0D\u7231\u6211 \uD83D\uDC9C\uD83D\uDE3E\n\nFor each cycle shift from `k - 1` to `k`, we should imagine it as a process of:\n1. Removing `nums[k-1]` (of the original array)\n2. Decreasing every indices from `k` to the right by one\n3. Add a new element `nums[k-1]` (of the original array) with index = `n-1`.\n\nAs the indices are decreasing, there\'s gotta be an **expiration point** for each index, which is, the point where the index no longer give a score. This can either because the index `i` goes lower than `nums[i]`, or it is removed by the step 1 of the shifting process.\nAn index that is added by step 3, we will treat them as a completely new element, with a new expiration point.\nNotice that an index can no longer give a score after its expiration, this is a big hint that we can **line sweep** to progressively update the score on each cycle shift.\n\n# Complexity\n- Let `n = nums.length`.\n- Time complexity: $$O(n)$$\n- Space complexity: $$O(n)$$\n\n# Code\n```js\nlet acc = new Uint32Array(100001);\n\n/**\n * @param {number[]} nums\n * @return {number}\n */\nvar bestRotation = function (nums) {\n  let n = nums.length;\n  acc.fill(0, 0, n + 1);\n\n  for (let i = 0; i < n; ++i) {\n    ++acc[Math.min(i + 1, Math.max(0, i - nums[i] + 1))];\n  }\n\n  let bestInd = 0;\n  let bestCnt = n - acc[0];\n  let currCnt = bestCnt;\n\n  for (let i = 1; i < n; ++i) {\n    currCnt -= acc[i];\n    if (nums[i - 1] < n) {\n      ++currCnt;\n\n      let exp = i + n - nums[i - 1];\n      if (exp < n) ++acc[exp];\n    }\n\n    if (currCnt > bestCnt) {\n      bestCnt = currCnt;\n      bestInd = i;\n    }\n  }\n\n  return bestInd;\n};\n```
['Line Sweep', 'JavaScript']