Perfect Explaination || C++ Solution
Intuition\nThe problem involves finding the best rotation K such that after rotating the array K times, the maximum score is achieved. The score is determined b
# Intuition\nThe problem involves finding the best rotation K such that after rotating the array K times, the maximum score is achieved. The score is determined by the number of indices i where nums[i] is no greater than its index after rotation. This observation points to needing an efficient way to track the impact of each rotation on the scoring of the indices.\n\n# Approach\n1. Difference Array for Efficient Range Update:\n* We create a difference array, diff, that will allow us to efficiently manage score increments and decrements as elements move with each rotation.\n* For each element, determine the range of rotations that yield positive scores, and update the difference array accordingly.\n2. Score Calculation:\n* By iterating over the diff array, we can calculate the cumulative score for each rotation.\n* Track the maximum score and its corresponding index as we process the cumulative values.\n3. Priority Queue for Optimization:\n* To maintain the highest score efficiently as we rotate, we use a priority queue to hold potential scores and select the maximum efficiently.\n# Complexity\n- Time complexity: O(nlogn) due to the priority queue operations over n elements.\n- Space complexity: O(n) for the diff array and priority queue storage.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int bestRotation(vector<int>& nums) {\n        int n = nums.size();\n        vector<int> diff(n);\n        for(int i=0;i<n;i++){\n            diff[i] = nums[i]-i;\n        }\n        priority_queue<int> pq;\n        for(int i=0;i<n;i++){\n            if(diff[i] <= 0){\n                pq.push(diff[i]);\n            }\n        }\n        int cnt = 0;\n        int ind = 0;\n        int maxi = pq.size();\n        for(int i=0;i<n;i++){\n            diff[i] -= n;\n            pq.push(diff[i]);\n            cnt++;\n            while(!pq.empty() && pq.top() + cnt > 0){\n                pq.pop();\n            }\n            if(pq.size() > maxi){\n                maxi = pq.size();\n                ind = cnt;\n            }\n        }\n        return ind;\n    }\n};\n```
['C++']