Skip to content

2855. Minimum Right Shifts to Sort the Array 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  int minimumRightShifts(vector<int>& nums) {
    int count = 0;
    int pivot = -1;

    for (int i = 0; i + 1 < nums.size(); i++)
      if (nums[i] > nums[i + 1]) {
        ++count;
        pivot = i;
      }

    if (count == 0)
      return 0;
    if (count > 1 || nums.back() > nums.front())
      return -1;
    return nums.size() - 1 - pivot;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public int minimumRightShifts(List<Integer> nums) {
    int pivot = -1;
    int count = 0;

    for (int i = 0; i + 1 < nums.size(); i++)
      if (nums.get(i) > nums.get(i + 1)) {
        ++count;
        pivot = i;
      }

    if (count == 0)
      return 0;
    if (count > 1 || nums.get(nums.size() - 1) > nums.get(0))
      return -1;
    return nums.size() - 1 - pivot;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def minimumRightShifts(self, nums: list[int]) -> int:
    count = 0

    for i, (a, b) in enumerate(itertools.pairwise(nums)):
      if a > b:
        count += 1
        pivot = i

    if count == 0:
      return 0
    if count > 1 or nums[-1] > nums[0]:
      return -1
    return len(nums) - pivot - 1