# 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
### Video Links
### Approach 1:
```
Brute
```
{% code title="C++" lineNumbers="true" %}
```cpp
class Solution {
public:
bool check_sorted(vector& nums){
for(int i=1; i nums[i] )
return false;
}
return true;
}
int minimumRightShifts(vector& nums) {
int k=0;
for(int i=0; i=0; j--){
nums[j+1] = nums[j];
}
nums[0] = temp;
}
k++;
}
return -1;
}
};
```
{% endcode %}
### Approach 2:
```
Optimal
```
{% code title="C++" lineNumbers="true" %}
```cpp
class Solution {
public:
int minimumRightShifts(vector& 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;
}
};
```
{% endcode %}
### Approach 3:
```
```
{% code title="C++" lineNumbers="true" %}
```cpp
```
{% endcode %}
### Approach 4:
```
```
{% code title="C++" lineNumbers="true" %}
```cpp
```
{% endcode %}
### Similar Problems