Minimum Right Shifts to Sort the Array

Difficulty: Easy | Acceptance: 57.40% | Paid: No Topics: Array

You are given a 0-indexed array nums of distinct integers. A right shift moves the last element of the array to the first position and shifts all other elements to the right. Return the minimum number of right shifts required to make nums sorted in strictly increasing order. If it is impossible to sort the array by right shifts, return -1.

• Examples
• Constraints
• Brute Force Simulation
• Find Minimum Element Index

Examples

Input: nums = [3,4,5,1,2]
Output: 2
Explanation: 
1st shift: nums = [2,3,4,5,1]
2nd shift: nums = [1,2,3,4,5]

Input: nums = [1,2,3]
Output: 0
Explanation: The array is already sorted.

Input: nums = [2,1,4]
Output: -1
Explanation: No matter how many shifts we do, the array cannot be sorted.

Constraints

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

Brute Force Simulation

Intuition Since the array length is small (up to 100), we can simulate the right shift operation for every possible number of shifts from 0 to n-1. For each shifted configuration, we check if the array is sorted.

Steps

• Iterate k from 0 to n-1, representing the number of right shifts.
• For each k, check if the array is sorted in strictly increasing order starting from index k and wrapping around to the beginning.
• If a sorted configuration is found, return the number of shifts required to align the start of the sorted sequence to index 0. This is (n - k) % n.
• If no configuration is sorted after checking all k, return -1.

from typing import List

class Solution:
    def minimumRightShifts(self, nums: List[int]) -> int:
        n = len(nums)
        for k in range(n):
            is_sorted = True
            for i in range(n - 1):
                curr = nums[(k + i) % n]
                nxt = nums[(k + i + 1) % n]
                if curr > nxt:
                    is_sorted = False
                    break
            if is_sorted:
                return (n - k) % n
        return -1

Complexity

• Time: O(n²) - We iterate through n shifts and check n elements for each.
• Space: O(1) - We only use a few variables for iteration.
• Notes: Simple to implement but inefficient for very large arrays (though constraints are small here).

Find Minimum Element Index

Intuition In a sorted array of distinct integers, the minimum element is at the beginning. If the array is a rotation of a sorted array, the minimum element marks the start of the sorted sequence. We can find the index of the minimum element and verify if the array is sorted starting from that index.

Steps

• Find the index min_idx of the smallest element in the array.
• Iterate through the array starting from min_idx and check if the sequence is strictly increasing, wrapping around to the beginning.
• If the sequence is sorted, the number of right shifts needed is (n - min_idx) % n (moving the tail to the front).
• If the sequence is not sorted, return -1.

from typing import List

class Solution:
    def minimumRightShifts(self, nums: List[int]) -> int:
        n = len(nums)
        min_idx = 0
        for i in range(n):
            if nums[i] < nums[min_idx]:
                min_idx = i
        
        for i in range(n - 1):
            curr = nums[(min_idx + i) % n]
            nxt = nums[(min_idx + i + 1) % n]
            if curr > nxt:
                return -1
        
        return (n - min_idx) % n

Complexity

• Time: O(n) - We pass through the array twice (once to find min, once to verify order).
• Space: O(1) - Constant extra space used.
• Notes: This is the optimal approach for this problem.