Smallest Rotation With Highest Score, C++ Explained Solution
Upvote If Found Helpful !!!\n\n# Approach\n Describe your approach to solving the problem. \nThe problem here is quite interesting and needs some nice observati
***Upvote If Found Helpful !!!***\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe problem here is quite interesting and needs some nice observations. The brute force approach is to just perform the rotations and get the score for each rotations. However this solutions takes up quadratic time. We need to optimise ! One good observation is that numbers in array are going to be between **0** and **N-1**, where **N** is the size of the array. Now instead of rotating each element, lets focus on for which number of rotations does that element contribute to the answer. Lets say a number **nums[i] is present at index i**. Now lets look at its left and right directions. Basically after each rotation, the element moves towards left i.e from **i to i-1**. If the element **nums[i] <= i**, then it means that up till some **j < i, this element will keep on contributing until nums[i] > j**. Since the element itself are in range of size of array, therefore the left contribution for any element can be **max(0, i - nums[i])**. Now remember that we are not only interested in calculating the contribution but also the indexes where the contribution takes place. \n\nThe technique that now we are going to use is actually very basic and well known : **THE RANGE UPDATE**. In this technique, we try to keep track of contribution of each range by adding **1** at index where range starts and adding **-1** at just after the end of the range. What we do is that for left contribution, we get the indexes where the element contributes and update the range array. In similar way, we do the same thing for right contribution. The implementation goes below : \n\n# Complexity\n- Time complexity: **O(N)**\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: **O(N)**\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int bestRotation(vector<int>& nums) {\n        ios_base::sync_with_stdio(0);\n        int n = nums.size();\n        vector<int>rotations(n,0);\n        for(int i = 0; i < n; i++){\n            // We need to get what number of rotations contribute and what do not \n            if(nums[i] <= i){ // Get Left Hand Rotations\n                rotations[0]++;\n                int diff = i - nums[i] + 1;\n                if(diff < n){\n                    rotations[diff]--;\n                }\n            }\n            if(i + 1 < n){   // Get Right Hand Rotations\n                rotations[i + 1]++;\n            }\n            if(n - nums[i] + i + 1 < n){\n                rotations[n - nums[i] + i + 1]--;\n            }\n        }\n        for(int i = 1; i < n; i++){\n            rotations[i] += rotations[i-1];\n        }\n        int ans = -1, cnt = -1;\n        for(int i = 0; i < n; i++){\n            if(rotations[i] > cnt){\n                ans = i;\n                cnt = rotations[i];\n            }\n        }\n        return ans;\n    }\n};\n```
['Array', 'Math', 'Prefix Sum', 'C++']