Simple O(n) C++ solution with detailed description
Problem description\nYou are given an array nums. You can rotate it by a non-negative integer k so that the array becomes [nums[k], nums[k + 1], ... nums[nums.l
# Problem description\nYou are given an array `nums`. You can rotate it by a non-negative integer `k` so that the array becomes `[nums[k], nums[k + 1], ... nums[nums.length - 1], nums[0], nums[1], ..., nums[k-1]]`. Afterward, any entries that are less than or equal to their index are worth one point.\n\n# Solution\nFor simplification let\'s denote the input array as `A`, its elements as `A[i]` and its length as `n`.\n\nThe first working solution is to check all possible array rotations and find one which produces the maximum score. But it\'s `O(n\xB2)` and thus it\'s not our way.\n\nHow can we solve the task faster? What if we know how many points we get and how many points we lose when we rotate the array by `k`? Then we can iterate over the all possible values of `k` and find that one which produces the maximum score. It will be $$O(n)$$ if we can calculate the score change for any `k` for just $$O(1)$$. Is it possible? Yes.\n\nSo, let\'s analyze the array first. We know from the description that for any arbitraty `i`, if `A[i] <= i` that number is already worth a point, otherwise it is not. In case if it\'s not, what can we do? We can rotate the array so this element takes some other place `j` such that `A[i] <= j`. And which place could it be? Since when we rotate the array we effectively shift it left (i.e. we are decreasing the indices of the existing elements), it\'s obvious that we need to shift this element out, so then it will be shifted in on the right side and takes the last place in the array with the highest possible index. And to do so, we need to rotate the array by `i + 1`. \n\nGood, but what if we continue to rotate the array more? At some new `j > i + 1` we lose this element again as its index will continue do decrease. But where does this happen? Let\'s calculate `d` as `d = A[i] - i`. Since in our case `A[i] > i`, `d` will be greater than zero and it will specify how far we need to move the current element to the right so it will worth a point. But we can\'t move it to the right, we can move it to the left only! Not an issue.\n\nIf we rotate the array by `n`, obvisouly nothing happens. Each number ends up at its original place. But if we rotate it by `n - 1` we effectively shift it right by one number. So, to shift it right by `d` numbers, we need to rotate it by `n - d`. And we remember that `i + d` is the last position for our element when it is worth a point. Thus it will lose the point if we rotate the array by one more, or `n - d + 1`.\n\nNow we have enough information about `A[i]`: we know that it will get us a point if we rotate the array by `i + 1` and it will lose its point if we rotate the array by `n - d + 1`. All we have to do now is to repeat this alrorithm for all other array elements.\n\nSo, let\'s create another array `rots` where `rots[k]` will denote how many points we gain (or lose) if we rotate the array from `k - 1` to `k`. Now we can write the following code for our case:\n```\n    ++rots[i + 1];\n    --rots[n - d + 1];\n```\nOK, so far so good. But what if our `A[i]` originally is worth a point? If we start shifting it left, it will lose its point at some place. And that happens when we rotate the array by `1 - d`. To understand it let\'s imagine that we have a number `3` at index `4`. It\'s worth a point there. Now we rotate the array by `1`. The same number `3` is now at index `3` and it\'s still OK. Now we rotate the array by `2` and it moves to the index `2` where it is not worth a point anymore! And `d = 3 - 4 = -1; 1 - d = 1 - (-1) = 2`.\n\nBut if we continue rotating the array, at some point the current number will be moved to the array\'s end and there it will worth a point again. You already know that it happens at `i + 1`.\n\nSo we can write the following code for this case:\n```\n    --rots[1 - d];\n    ++rots[i + 1];\n```\n\nAs you see, we have `++rots[i + 1]` in both cases, so we can move it out of the condition. Thus the final code will look like:\n```\n    ++rots[i + 1];\n    int d = nums[i] - i;\n    if (d > 0)\n        --rots[n - d + 1];\n    else\n        --rots[1 - d];\n```\nOne more note - we are completely not interested in rotating the array by `0`, so we don\'t need the `rots[0]` element. Thus we can subtract `1` from the index and get the following code:\n```\n    ++rots[i];\n    int d = nums[i] - i;\n    if (d > 0)\n        --rots[n - d];\n    else\n        --rots[-d];\n```\nWait a minute - do we really have `++rots[i]` for each possible `i`? Obviously it\'s redundant, we can skip it here and then add `1` later to remove two excessive array element accesses (one read and one write).\n\nAnd now we are almost there. What is left to do is to go through the `rots` array and calculate which score we get if we rotate the array by `k` by summing its elements: `rots[0] + 1` contains score change if we rotate the array by `1`, `rots[0] + rots[1] + 2` contains score change for rotating by `2`, `rots[0] + rots[1] + rots[2] + 3` contains for `3`, etc. Also we can find the maximum possible score in this loop.\n\nPlease note that we don\'t need to calculate the original array score at all since it\'s not relevant - the maximum score change is enough.\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nclass Solution {\npublic:\n    int bestRotation(vector<int>& nums) {\n        int sz = (int)nums.size();\n        std::vector<int> rots (sz);\n        for (int i = 0; i < sz; ++i)\n        {\n            int d = nums[i] - i;\n            if (d > 0)\n                --rots[sz - d];\n            else\n                --rots[-d];\n        }\n\n        int m = 0, s = 0, k = 0;\n        for (int i = 0; i < (int)rots.size(); ++i)\n        {\n            s += rots[i] + 1;\n            if (s > m)\n            {\n                m = s;\n                k = i + 1;\n            }\n        }\n\n        return k;\n    }\n};\n```
['C++']