Problem

You are given a 0-indexed array nums of length n containing distinct positive integers. Return _theminimum number of right shifts required to sort _nums and-1 if this is not possible.

A right shift is defined as shifting the element at index i to index `(i

    1. % n`, for all indices.

Examples

Example 1

1
2
3
4
5
6

Input: nums = [3,4,5,1,2]
Output: 2
Explanation: 
After the first right shift, nums = [2,3,4,5,1].
After the second right shift, nums = [1,2,3,4,5].
Now nums is sorted; therefore the answer is 2.

Example 2

1
2
3

Input: nums = [1,3,5]
Output: 0
Explanation: nums is already sorted therefore, the answer is 0.

Example 3

1
2
3

Input: nums = [2,1,4]
Output: -1
Explanation: It's impossible to sort the array using right shifts.

Constraints

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100
  • nums contains distinct integers.

Solution

Method 1 – Find Rotation Point

Intuition

If the array is sorted after some right shifts, it must be a rotated sorted array. Find the point where the order breaks. If there is more than one break, it’s impossible. Otherwise, the number of right shifts is n - break_index.

Approach

  1. Scan the array to find the index where nums[i] > nums[i+1].
  2. If there are zero breaks, array is already sorted (0 shifts).
  3. If there is one break, check if rotating at that point sorts the array.
  4. If more than one break, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int minimumRightShifts(vector<int>& nums) {
        int n = nums.size(), breaks = 0, idx = -1;
        for (int i = 0; i < n; ++i) {
            if (nums[i] > nums[(i+1)%n]) { breaks++; idx = i; }
        }
        if (breaks == 0) return 0;
        if (breaks > 1) return -1;
        return n - (idx+1);
    }
};
1
2
3
4
5
6
7
8
9

func minimumRightShifts(nums []int) int {
    n, breaks, idx := len(nums), 0, -1
    for i := 0; i < n; i++ {
        if nums[i] > nums[(i+1)%n] { breaks++; idx = i }
    }
    if breaks == 0 { return 0 }
    if breaks > 1 { return -1 }
    return n - (idx+1)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int minimumRightShifts(int[] nums) {
        int n = nums.length, breaks = 0, idx = -1;
        for (int i = 0; i < n; i++) {
            if (nums[i] > nums[(i+1)%n]) { breaks++; idx = i; }
        }
        if (breaks == 0) return 0;
        if (breaks > 1) return -1;
        return n - (idx+1);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun minimumRightShifts(nums: IntArray): Int {
        val n = nums.size
        var breaks = 0; var idx = -1
        for (i in 0 until n) {
            if (nums[i] > nums[(i+1)%n]) { breaks++; idx = i }
        }
        if (breaks == 0) return 0
        if (breaks > 1) return -1
        return n - (idx+1)
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def minimumRightShifts(self, nums: list[int]) -> int:
        n, breaks, idx = len(nums), 0, -1
        for i in range(n):
            if nums[i] > nums[(i+1)%n]:
                breaks += 1; idx = i
        if breaks == 0: return 0
        if breaks > 1: return -1
        return n - (idx+1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn minimum_right_shifts(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut breaks = 0; let mut idx = -1;
        for i in 0..n {
            if nums[i] > nums[(i+1)%n] { breaks += 1; idx = i as i32; }
        }
        if breaks == 0 { return 0; }
        if breaks > 1 { return -1; }
        n as i32 - (idx+1)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    minimumRightShifts(nums: number[]): number {
        const n = nums.length;
        let breaks = 0, idx = -1;
        for (let i = 0; i < n; i++) {
            if (nums[i] > nums[(i+1)%n]) { breaks++; idx = i; }
        }
        if (breaks === 0) return 0;
        if (breaks > 1) return -1;
        return n - (idx+1);
    }
}

Complexity

  • ⏰ Time complexity: O(n) — One pass to find break point.
  • 🧺 Space complexity: O(1) — Only a few variables.