798. Smallest Rotation with Highest Score LeetCode Solution

In this guide, you will get 798. Smallest Rotation with Highest Score LeetCode Solution with the best time and space complexity. The solution to Smallest Rotation with Highest Score problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Smallest Rotation with Highest Score solution in C++
  4. Smallest Rotation with Highest Score solution in Java
  5. Smallest Rotation with Highest Score solution in Python
  6. Additional Resources
798. Smallest Rotation with Highest Score LeetCode Solution image

Problem Statement of 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.

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.

See also  1235. Maximum Profit in Job Scheduling LeetCode Solution

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.

Constraints:

1 <= nums.length <= 105
0 <= nums[i] < nums.length

Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(1)

798. Smallest Rotation with Highest Score LeetCode Solution in C++

class Solution {
 public:
  int bestRotation(vector<int>& nums) {
    const int n = nums.size();
    // rotate[i] := the number of points lost after rotating left i times
    vector<int> rotate(n);

    // Rotating i - nums[i] times makes nums[i] == its new index.
    // So, rotating i - nums[i] + 1 times will "start" to make nums[i] > its
    // index, which is the starting index to lose point.
    for (int i = 0; i < n; ++i)
      --rotate[(i - nums[i] + 1 + n) % n];

    // Each time of the rotation, make index 0 to index n - 1 to get 1 point.
    for (int i = 1; i < n; ++i)
      rotate[i] += rotate[i - 1] + 1;

    return distance(rotate.begin(), ranges::max_element(rotate));
  }
};
/* code provided by PROGIEZ */

798. Smallest Rotation with Highest Score LeetCode Solution in Java

class Solution {
  public int bestRotation(int[] nums) {
    final int n = nums.length;
    // rotate[i] := the number of points lost after rotating left i times
    int[] rotate = new int[n];

    // Rotating i - nums[i] times makes nums[i] == its new index.
    // So, rotating i - nums[i] + 1 times will "start" to make nums[i] > its
    // index, which is the starting index to lose point.
    for (int i = 0; i < n; ++i)
      --rotate[(i - nums[i] + 1 + n) % n];

    // Each time of the rotation, make index 0 to index n - 1 to get 1 point.
    for (int i = 1; i < n; ++i)
      rotate[i] += rotate[i - 1] + 1;

    int mx = Integer.MIN_VnumsLUE;
    int maxIndex = 0;

    for (int i = 0; i < n; ++i)
      if (rotate[i] > mx) {
        mx = rotate[i];
        maxIndex = i;
      }

    return maxIndex;
  }
}
// code provided by PROGIEZ

798. Smallest Rotation with Highest Score LeetCode Solution in Python

N/A
# code by PROGIEZ

Additional Resources

See also  748. Shortest Completing Word LeetCode Solution

Happy Coding! Keep following PROGIEZ for more updates and solutions.