Smallest Rotation with Highest Score LeetCode Solution

Last updated on October 9th, 2024 at 06:25 pm

Here, We see Smallest Rotation with Highest Score LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Array, Math

Level of Question

Hard

Smallest Rotation with Highest Score LeetCode Solution

Smallest Rotation with Highest Score LeetCode Solution

Problem Statement

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.

Example 1:

Input: nums = [2,3,1,4,0]
Output: 3
Explanation: Scores for each k are listed below: 
k = 0,  nums = [2,3,1,4,0],    score 2
k = 1,  nums = [3,1,4,0,2],    score 3
k = 2,  nums = [1,4,0,2,3],    score 3
k = 3,  nums = [4,0,2,3,1],    score 4
k = 4,  nums = [0,2,3,1,4],    score 3
So we should choose k = 3, which has the highest score

Example 2:

Input: nums = [1,3,0,2,4]
Output: 0
Explanation: nums will always have 3 points no matter how it shifts.
So we will choose the smallest k, which is 0.

1. Smallest Rotation with Highest Score Leetcode Solution C++

class Solution {
public:
    int bestRotation(vector<int>& nums) {
        const int N = nums.size();
        vector<int> tmp(N+1, 0); 
        for (int i(0); i < N; ++i) {
            if (nums[i] <= i) {
                tmp[0] += 1;
                tmp[i-nums[i]+1] -= 1;
                tmp[i+1] += 1;
                tmp[N] -= 1;
            }
            else {
                tmp[i+1] += 1;
                tmp[N-nums[i]+i+1] -= 1;
            }
        }
        int maxc = INT_MIN;
        int maxK = -1;
        int cur = 0;
        for (int i(0); i < N; ++i) {
            cur += tmp[i];
            if (cur > maxc) {
                maxc = cur;
                maxK = i;
            }
        }
        return maxK;
    }
};

2. Smallest Rotation with Highest Score Leetcode Solution Java

class Solution {
    public int bestRotation(int[] nums) {
        final int size = nums.length;
        int[] rsc = new int[size];
        for(int i = 0; i < size - 1; i++) {
            int value = nums[i];
            int downPos = (i + 1 + size - value) % size;
            rsc[downPos]--;
        }
        int value = nums[size-1];
        if( value != 0 ) rsc[size - value]--;
        int bestk = 0;
        int bestscore = rsc[0];
        int score = rsc[0];
        for(int i = 1; i < nums.length; i++) {
            score += rsc[i] + 1;
            if( score > bestscore ) {
                bestk = i;
                bestscore = score;
            }
        }
        return bestk;
    }
}

3. Smallest Rotation with Highest Score Leetcode Solution JavaScript

var bestRotation = function (nums) {
    let acc = new Uint32Array(100001);
    let n = nums.length;
    acc.fill(0, 0, n + 1);
    for (let i = 0; i < n; ++i) {
        ++acc[Math.min(i + 1, Math.max(0, i - nums[i] + 1))];
    }
    let bestInd = 0;
    let bestCnt = n - acc[0];
    let currCnt = bestCnt;
    for (let i = 1; i < n; ++i) {
        currCnt -= acc[i];
        if (nums[i - 1] < n) {
            ++currCnt;
            let exp = i + n - nums[i - 1];
            if (exp < n) ++acc[exp];
        }
        if (currCnt > bestCnt) {
            bestCnt = currCnt;
            bestInd = i;
        }
    }
    return bestInd;
};

4. Smallest Rotation with Highest Score Leetcode Solution Python

class Solution(object):
    def bestRotation(self, nums):
        n = len(nums)
        change = [1] * n
        for i, num in enumerate(nums):
            change[(i - num + 1) % n] -= 1
        for i in range(1, n):
            change[i] += change[i - 1]
        return change.index(max(change))
Scroll to Top