Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

798. Smallest Rotation with Highest Score

Time: $O(n)$

Space: $O(1)$

			


class Solution {
 public:
  int bestRotation(vector<int>& A) {
    const int n = A.size();
    // rotate[i] := how many points losing after rotating left i times
    vector<int> rotate(n);

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

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

    return distance(begin(rotate), max_element(begin(rotate), end(rotate)));
  }
};




			


class Solution {
  public int bestRotation(int[] A) {
    final int n = A.length;
    // rotate[i] := how many points losing after rotating left i times
    int[] rotate = new int[n];

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

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

    int max = Integer.MIN_VALUE;
    int maxIndex = 0;

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

    return maxIndex;
  }
}