798. Smallest Rotation with Highest Score

You 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.

• For example, if we have nums = [2,4,1,3,0], and we rotate by k = 2, it becomes [1,3,0,2,4]. This is worth 3 points because 1 > 0 [no points], 3 > 1 [no points], 0 <= 2 [one point], 2 <= 3 [one point], 4 <= 4 [one point].

Return the rotation index k that corresponds to the highest score we can achieve if we rotated nums by it. If there are multiple answers, return the smallest such index k.

• hash table solution

class Solution {
public:
    int bestRotation(vector<int>& A) {
        unordered_map<int, int> freq;
        int n = A.size(), res = 0, score = 0, ma = 0;
        for(int i = 0; i < n; i++) {
            if(A[i] > i) continue;
            freq[i-A[i]]++;
            score++;
        }
        ma = score;
        for(int i = 0, j = 1; i < n; i++, j++) {
            score -= freq[j-1];
            if(A[i] > n - 1) continue;
            freq[j+n-1-A[i]]++;
            score++;
            if(ma < score) {
                ma = score;
                res = j;
            }
        }
        
        return res;
    }
};

• heap solution

class Solution {
public:
    int bestRotation(vector<int>& A) {
        priority_queue<int, vector<int>, greater<int>> q;
        int n = A.size(), res = 0, score = 0;
        for(int i = 0; i < n; i++) {
            if(A[i] > i) continue;
            q.push(i - A[i]);
        }
        score = q.size();
        for(int i = 0, j = 1; i < n; i++, j++) {
            while(!q.empty() and q.top() < j) q.pop();
            if(A[i] > n - 1) continue;
            q.push(j + n - 1 - A[i]);
            if(score < q.size()) {
                score = q.size();
                res = j;
            }
        }
        
        return res;
    }
};