2855. Minimum Right Shifts to Sort the Array

Problem Statement

You are given a 0-indexed array nums of length n containing distinct positive integers. Return the minimum 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.

Example 1:

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:

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

Example 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.

Intuition

Approach 1: Brute

Approach 2: Optimal
Scan and maintain the count, and hence compare the first and last

Links

https://leetcode.com/problems/minimum-right-shifts-to-sort-the-array/description/

Video Links

Approach 1:

Brute

C++

class Solution {
public:
    bool check_sorted(vector<int>& nums){
        for(int i=1; i<nums.size(); i++){
            if(nums[i-1] > nums[i] )
                return false;
        }
        return true;
    }

    int minimumRightShifts(vector<int>& nums) {
        int k=0;
        for(int i=0; i<nums.size(); i++){
            if(check_sorted(nums))
                return k;

            else{
                int temp = nums.back();
                for(int j=nums.size()-2; j>=0; j--){
                    nums[j+1] = nums[j];
                }
                nums[0] = temp;
            } 
            k++;
        }

        return -1;
    }
};

Approach 2:

Optimal

C++

class Solution {
public:
    int minimumRightShifts(vector<int>& nums) {
        int index = nums.size();
        int count=0;
        for(int i=nums.size()-1; i>=1; i--){
            if(nums[i-1] > nums[i]){
                index = i;
                count++;
            }
        }
        if(nums[0] < nums[nums.size()-1])
            count++;

        if(count>1)
            return -1;

        return nums.size() - index;
    }
};

Approach 3:

C++

Approach 4:

C++