Algorithms
Easy
2855
3045
Minimum Right Shifts to Sort the Array
minimum-right-shifts-to-sort-the-array
"""
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.
"""
class Solution:
    def minimumRightShifts(self, nums: List[int]) -> int:
        
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.


Please complete the code below to solve above prblem:
```python
class Solution:
    def minimumRightShifts(self, nums: List[int]) -> int:
        
```

my_solution = Solution()

test_input = { "nums": [3,4,5,1,2] }
assert my_solution.minimumRightShifts(**test_input) == 2

test_input = { "nums": [1,3,5] }
assert my_solution.minimumRightShifts(**test_input) == 0

test_input = { "nums": [2,1,4] }
assert my_solution.minimumRightShifts(**test_input) == -1

test_input = { "nums": [31,72,79,25] }
assert my_solution.minimumRightShifts(**test_input) == 1

test_input = { "nums": [27,33,42,58,81,8,9,17] }
assert my_solution.minimumRightShifts(**test_input) == 3

test_input = { "nums": [72,13,21,35,52] }
assert my_solution.minimumRightShifts(**test_input) == 4

test_input = { "nums": [65,73,77,1] }
assert my_solution.minimumRightShifts(**test_input) == 1

test_input = { "nums": [100,8,14,68,80,84] }
assert my_solution.minimumRightShifts(**test_input) == 5

test_input = { "nums": [53,60,64,69,98,40] }
assert my_solution.minimumRightShifts(**test_input) == 1

test_input = { "nums": [21] }
assert my_solution.minimumRightShifts(**test_input) == 0

test_input = { "nums": [78,12,18,21,23,36,64,70] }
assert my_solution.minimumRightShifts(**test_input) == 7

test_input = { "nums": [25,26,53,91,92,99,10,24] }
assert my_solution.minimumRightShifts(**test_input) == 2

test_input = { "nums": [63,51,65,87,6,17,32,14,42,46] }
assert my_solution.minimumRightShifts(**test_input) == -1

test_input = { "nums": [43,46,75,76,85,96,9,19,25] }
assert my_solution.minimumRightShifts(**test_input) == 3

test_input = { "nums": [5] }
assert my_solution.minimumRightShifts(**test_input) == 0

test_input = { "nums": [35,72,76,82,96,97,24,26] }
assert my_solution.minimumRightShifts(**test_input) == 2

test_input = { "nums": [82,30,94,55,76,51,3,89,52,96] }
assert my_solution.minimumRightShifts(**test_input) == -1

test_input = { "nums": [57,59,88,97,6,27,41,46,52] }
assert my_solution.minimumRightShifts(**test_input) == 5

test_input = { "nums": [17] }
assert my_solution.minimumRightShifts(**test_input) == 0

test_input = { "nums": [62] }
assert my_solution.minimumRightShifts(**test_input) == 0

test_input = { "nums": [24,46,55,61,71,78,1,4] }
assert my_solution.minimumRightShifts(**test_input) == 2

test_input = { "nums": [83,2,21,42,73,77,80] }
assert my_solution.minimumRightShifts(**test_input) == 6

test_input = { "nums": [83,94,14,43,50,62,63] }
assert my_solution.minimumRightShifts(**test_input) == 5

test_input = { "nums": [38,46,66,77,7,15,17,35] }
assert my_solution.minimumRightShifts(**test_input) == 4

test_input = { "nums": [35,68,82,90,9,18,29,34] }
assert my_solution.minimumRightShifts(**test_input) == 4

test_input = { "nums": [71] }
assert my_solution.minimumRightShifts(**test_input) == 0

test_input = { "nums": [71,73,88,12,49,55,59,70] }
assert my_solution.minimumRightShifts(**test_input) == 5

test_input = { "nums": [54,65,75,81,24,37] }
assert my_solution.minimumRightShifts(**test_input) == 2

test_input = { "nums": [57,67,73,78,79,2,45,48,51] }
assert my_solution.minimumRightShifts(**test_input) == 4

test_input = { "nums": [36,62,65,85,95,9,21] }
assert my_solution.minimumRightShifts(**test_input) == 2

test_input = { "nums": [68,12] }
assert my_solution.minimumRightShifts(**test_input) == 1

test_input = { "nums": [34,9,86,20,67,94,65,82,40,79] }
assert my_solution.minimumRightShifts(**test_input) == -1

test_input = { "nums": [92,84,37,19,16,85,20,79,25,89] }
assert my_solution.minimumRightShifts(**test_input) == -1

test_input = { "nums": [3,16,38,44,67,79,84] }
assert my_solution.minimumRightShifts(**test_input) == 0

test_input = { "nums": [14,24,58,69,71,94,13] }
assert my_solution.minimumRightShifts(**test_input) == 1

test_input = { "nums": [100,18] }
assert my_solution.minimumRightShifts(**test_input) == 1

test_input = { "nums": [13] }
assert my_solution.minimumRightShifts(**test_input) == 0

test_input = { "nums": [94,30,53,56,67,72,82] }
assert my_solution.minimumRightShifts(**test_input) == 6

test_input = { "nums": [92,14,65,80,85] }
assert my_solution.minimumRightShifts(**test_input) == 4

test_input = { "nums": [43,53,81,87,93,19,31,39] }
assert my_solution.minimumRightShifts(**test_input) == 3

test_input = { "nums": [80,38] }
assert my_solution.minimumRightShifts(**test_input) == 1

test_input = { "nums": [52,72,78,83,85,99,20] }
assert my_solution.minimumRightShifts(**test_input) == 1

test_input = { "nums": [3,6,89] }
assert my_solution.minimumRightShifts(**test_input) == 0

test_input = { "nums": [3] }
assert my_solution.minimumRightShifts(**test_input) == 0

test_input = { "nums": [55,56,63,91,3,46] }
assert my_solution.minimumRightShifts(**test_input) == 2

test_input = { "nums": [58,10,31,37,41] }
assert my_solution.minimumRightShifts(**test_input) == 4

test_input = { "nums": [17,33,53,58,78] }
assert my_solution.minimumRightShifts(**test_input) == 0

test_input = { "nums": [82,44] }
assert my_solution.minimumRightShifts(**test_input) == 1

test_input = { "nums": [89,96,35,48,57,71] }
assert my_solution.minimumRightShifts(**test_input) == 4

test_input = { "nums": [43,69,4,29,37] }
assert my_solution.minimumRightShifts(**test_input) == 3

test_input = { "nums": [65,88] }
assert my_solution.minimumRightShifts(**test_input) == 0

test_input = { "nums": [42,44,59,76,86] }
assert my_solution.minimumRightShifts(**test_input) == 0

test_input = { "nums": [29,56,78,96,1,10,27] }
assert my_solution.minimumRightShifts(**test_input) == 3

test_input = { "nums": [48,100] }
assert my_solution.minimumRightShifts(**test_input) == 0

test_input = { "nums": [4,33,17,3,8,91,28,13,72,42] }
assert my_solution.minimumRightShifts(**test_input) == -1

test_input = { "nums": [5,35,53,56] }
assert my_solution.minimumRightShifts(**test_input) == 0

test_input = { "nums": [65,67,70,27,41,50,52,57,60] }
assert my_solution.minimumRightShifts(**test_input) == 6

test_input = { "nums": [94,32,45,62] }
assert my_solution.minimumRightShifts(**test_input) == 3

test_input = { "nums": [23,25,34,47,61,65,6,21] }
assert my_solution.minimumRightShifts(**test_input) == 2

test_input = { "nums": [99,11,12,21,22,55,62,83] }
assert my_solution.minimumRightShifts(**test_input) == 7

test_input = { "nums": [92,13,33,58,61,85] }
assert my_solution.minimumRightShifts(**test_input) == 5

test_input = { "nums": [46] }
assert my_solution.minimumRightShifts(**test_input) == 0

test_input = { "nums": [12,27,30,36] }
assert my_solution.minimumRightShifts(**test_input) == 0

test_input = { "nums": [33,44,57,16,22,26,30] }
assert my_solution.minimumRightShifts(**test_input) == 4

test_input = { "nums": [67,24] }
assert my_solution.minimumRightShifts(**test_input) == 1

test_input = { "nums": [12,44,83,87] }
assert my_solution.minimumRightShifts(**test_input) == 0

test_input = { "nums": [19,52,3,8,12] }
assert my_solution.minimumRightShifts(**test_input) == 3

test_input = { "nums": [82,86,88,6,35,47,52,58,62] }
assert my_solution.minimumRightShifts(**test_input) == 6

test_input = { "nums": [48] }
assert my_solution.minimumRightShifts(**test_input) == 0

test_input = { "nums": [60,11] }
assert my_solution.minimumRightShifts(**test_input) == 1

test_input = { "nums": [69,60] }
assert my_solution.minimumRightShifts(**test_input) == 1

test_input = { "nums": [22,28,36,16,82,77,41,85,44,97] }
assert my_solution.minimumRightShifts(**test_input) == -1

test_input = { "nums": [63,94,2,14] }
assert my_solution.minimumRightShifts(**test_input) == 2

test_input = { "nums": [41,45,74,84,90,93,100,18,31] }
assert my_solution.minimumRightShifts(**test_input) == 2

test_input = { "nums": [21,38,57,64,12] }
assert my_solution.minimumRightShifts(**test_input) == 1

test_input = { "nums": [99,2,9,17,33,58,59,72] }
assert my_solution.minimumRightShifts(**test_input) == 7

test_input = { "nums": [36,89,90,98,11,14,23] }
assert my_solution.minimumRightShifts(**test_input) == 3

test_input = { "nums": [84,90,5,57,78] }
assert my_solution.minimumRightShifts(**test_input) == 3

test_input = { "nums": [48,73,76,30] }
assert my_solution.minimumRightShifts(**test_input) == 1

test_input = { "nums": [74] }
assert my_solution.minimumRightShifts(**test_input) == 0

test_input = { "nums": [21,84,35,65,12,74,30,95,46,23] }
assert my_solution.minimumRightShifts(**test_input) == -1

test_input = { "nums": [64,76,46,53,54] }
assert my_solution.minimumRightShifts(**test_input) == 3

test_input = { "nums": [77,84,89,47,52,74] }
assert my_solution.minimumRightShifts(**test_input) == 3

test_input = { "nums": [12,29,31,52,88,89,10] }
assert my_solution.minimumRightShifts(**test_input) == 1

test_input = { "nums": [20,25,28,41,57,89] }
assert my_solution.minimumRightShifts(**test_input) == 0

test_input = { "nums": [1,28,51,59] }
assert my_solution.minimumRightShifts(**test_input) == 0

test_input = { "nums": [59,76,2,26,49,78,36,70,64,24] }
assert my_solution.minimumRightShifts(**test_input) == -1

test_input = { "nums": [35,43,49,63,21] }
assert my_solution.minimumRightShifts(**test_input) == 1

test_input = { "nums": [1,35,38,47,54,56,58,74] }
assert my_solution.minimumRightShifts(**test_input) == 0

test_input = { "nums": [49,94,97] }
assert my_solution.minimumRightShifts(**test_input) == 0

test_input = { "nums": [32,30] }
assert my_solution.minimumRightShifts(**test_input) == 1

test_input = { "nums": [37,36] }
assert my_solution.minimumRightShifts(**test_input) == 1

test_input = { "nums": [31,41,65,14] }
assert my_solution.minimumRightShifts(**test_input) == 1

test_input = { "nums": [45,57,73,77,17,30,42,43] }
assert my_solution.minimumRightShifts(**test_input) == 4

test_input = { "nums": [17,65,11] }
assert my_solution.minimumRightShifts(**test_input) == 1

test_input = { "nums": [32,84,93,31,61,78,15,52,100,65] }
assert my_solution.minimumRightShifts(**test_input) == -1

test_input = { "nums": [61,72,90,3,8,17,23,55] }
assert my_solution.minimumRightShifts(**test_input) == 5

test_input = { "nums": [19,30,44,95,13] }
assert my_solution.minimumRightShifts(**test_input) == 1

test_input = { "nums": [42,46,66,71,87,3,4,5,14] }
assert my_solution.minimumRightShifts(**test_input) == 4

test_input = { "nums": [13,57,7] }
assert my_solution.minimumRightShifts(**test_input) == 1