Problem Description

Given an array A of length N, you can rotate it any number of times (from 0 up to N-1). After each rotation by K (where 0 ≤ K < N), the score is defined as the number of indices i where A[i] is less than or equal to its new index after rotation.

Formally, after rotating A by K, the element A[i] moves to index (i-K+N)%N. The score is the count of positions i where A[i] <= (i-K+N)%N.

Your task: Find the rotation K (0 ≤ K < N) that yields the highest score. If multiple K achieve the highest score, return the smallest such K.

• Each rotation is circular (elements wrap around).
• There is guaranteed to be one valid solution.
• Do not reuse elements; every array element is considered exactly once per rotation.

Thought Process

At first glance, it seems we could simulate every possible rotation, count the score for each, and return the best. However, this brute-force approach would require O(N^2) time, which is inefficient for large arrays.

To optimize, we need to find a way to compute the score for all K efficiently. Notice that for each element, there are certain rotations where it will "contribute" to the score, and others where it won't. If we can efficiently track when each element starts and stops contributing as we increment K, we can compute all scores in O(N) time.

This leads to the idea of using a "difference array" or "interval sweep" method: for each element, mark the range of rotations where it fails to contribute, and tally up all contributions as we sweep through K.

Solution Approach

• Step 1: Understand Contribution Ranges
  For each A[i], determine for which rotations K it will not contribute to the score. For a rotation K, A[i] moves to index (i-K+N)%N. It contributes if A[i] <= (i-K+N)%N.
• Step 2: Compute "Bad" Intervals
  For each A[i], solve for K where A[i] > (i-K+N)%N. This gives a contiguous interval of K values for which A[i] does not contribute. We can mark the start and end of this interval in a difference array.
• Step 3: Use a Difference Array
  Initialize a difference array change of size N. For each "bad" interval, decrement at the start and increment at the end (modulo N). After all intervals are marked, perform a prefix sum to get the score for each rotation.
• Step 4: Find the Best Rotation
  The rotation with the highest score is the one with the most contributions (i.e., the smallest number of "bad" intervals overlapping it). Return the smallest such K in case of ties.

This approach reduces the time complexity to O(N).

Example Walkthrough

Let's take A = [2, 3, 1, 4, 0] (N = 5).

1. For each element, calculate the range of K where it does not contribute:
   • i = 0, A[0] = 2: It fails to contribute when its new index (0-K+5)%5 < 2, i.e., when K = 4 or K = 0, 1 (modulo 5). Mark these intervals in the difference array.
   • Repeat for other elements.
2. After marking all "bad" intervals, perform a prefix sum sweep over the difference array to compute the score for each rotation K.
3. Find the rotation K with the maximum score. In this case, K = 3 yields the highest score.

This method efficiently finds the answer without simulating every rotation.

Time and Space Complexity

• Brute-force Approach:
  For each of N rotations, we scan the array to count scores, leading to O(N^2) time and O(N) space.
• Optimized Approach:
  We process each element once and use a difference array and prefix sum, both O(N) operations. The overall time complexity is O(N), and space complexity is also O(N) for the difference array.

Summary

By recognizing that each element's contribution changes over a contiguous interval of rotations, we can use a difference array to efficiently tally the scores for all possible rotations. This transforms a potentially slow brute-force solution into a fast, elegant O(N) algorithm, making use of clever interval marking and prefix sums.

Code Implementation

class Solution:
    def bestRotation(self, A):
        N = len(A)
        change = [0] * (N + 1)
        for i, a in enumerate(A):
            # Start of bad interval
            low = (i - a + 1 + N) % N
            # End of bad interval
            high = (i + 1) % N
            change[low] -= 1
            change[high] += 1
            if low > high:
                change[0] -= 1
        score = 0
        max_score = -N
        best_k = 0
        for k in range(N):
            score += change[k]
            if score > max_score:
                max_score = score
                best_k = k
        return best_k
      

class Solution {
public:
    int bestRotation(vector<int>& A) {
        int N = A.size();
        vector<int> change(N + 1, 0);
        for (int i = 0; i < N; ++i) {
            int low = (i - A[i] + 1 + N) % N;
            int high = (i + 1) % N;
            change[low] -= 1;
            change[high] += 1;
            if (low > high) {
                change[0] -= 1;
            }
        }
        int score = 0, max_score = -N, best_k = 0;
        for (int k = 0; k < N; ++k) {
            score += change[k];
            if (score > max_score) {
                max_score = score;
                best_k = k;
            }
        }
        return best_k;
    }
};
      

class Solution {
    public int bestRotation(int[] A) {
        int N = A.length;
        int[] change = new int[N + 1];
        for (int i = 0; i < N; ++i) {
            int low = (i - A[i] + 1 + N) % N;
            int high = (i + 1) % N;
            change[low] -= 1;
            change[high] += 1;
            if (low > high) {
                change[0] -= 1;
            }
        }
        int score = 0, maxScore = -N, bestK = 0;
        for (int k = 0; k < N; ++k) {
            score += change[k];
            if (score > maxScore) {
                maxScore = score;
                bestK = k;
            }
        }
        return bestK;
    }
}
      

var bestRotation = function(A) {
    const N = A.length;
    const change = new Array(N + 1).fill(0);
    for (let i = 0; i < N; ++i) {
        let low = (i - A[i] + 1 + N) % N;
        let high = (i + 1) % N;
        change[low] -= 1;
        change[high] += 1;
        if (low > high) {
            change[0] -= 1;
        }
    }
    let score = 0, maxScore = -N, bestK = 0;
    for (let k = 0; k < N; ++k) {
        score += change[k];
        if (score > maxScore) {
            maxScore = score;
            bestK = k;
        }
    }
    return bestK;
};