# Minimum Right Shifts to Sort the Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-right-shifts-to-sort-the-array)
Canonical: https://scaleengineer.com/dsa/problems/minimum-right-shifts-to-sort-the-array
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture)
---
## Problem
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.

# Approaches
## Brute Force Simulation
This approach directly simulates the process described in the problem. It repeatedly applies the right shift operation to the array and, after each shift, checks if the array has become sorted. It tries every possible number of shifts from 0 up to `n-1`.
**Time:** O(n^2) - The outer loop runs `n` times. Inside the loop, both checking if the list is sorted and performing a right shift take O(n) time, resulting in n * O(n) = O(n^2) complexity. · **Space:** O(n) - A copy of the list is created to perform the shifts, requiring space proportional to the number of elements.
**Pros:** Simple to understand and implement.; Directly models the problem statement, making the logic easy to follow.
**Cons:** Inefficient for larger arrays due to its quadratic time complexity.; Performs redundant work by repeatedly shifting and checking the entire array.
### Explanation
The brute-force algorithm iterates through all possible numbers of right shifts, from 0 to `n-1`. For each number of shifts, it applies the transformation to the array and then checks if the resulting array is sorted.

- The main loop runs `n` times, representing the number of shifts.
- In each iteration, a helper function `isSorted` checks for sorted order in O(n) time.
- If not sorted, a right shift is performed, which also takes O(n) time.

This leads to a total time complexity of O(n^2). A copy of the array is used to avoid modifying the original input.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int minimumRightShifts(List<Integer> nums) {
        int n = nums.size();
        List<Integer> currentList = new ArrayList<>(nums);

        for (int shifts = 0; shifts < n; shifts++) {
            if (isSorted(currentList)) {
                return shifts;
            }
            // Perform one right shift
            int last = currentList.remove(n - 1);
            currentList.add(0, last);
        }

        return -1;
    }

    private boolean isSorted(List<Integer> arr) {
        for (int i = 0; i < arr.size() - 1; i++) {
            if (arr.get(i) > arr.get(i + 1)) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- Create a copy of the input list `nums` to avoid modifying the original.
- Loop a variable `shifts` from 0 to `n-1`, where `n` is the size of the list.
- Inside the loop, first check if the current list is sorted. A helper function `isSorted` can iterate from the first element to the second-to-last, checking if `arr[i] > arr[i+1]`.
- If the list is sorted, it means we've found the minimum number of shifts. Return the current value of `shifts`.
- If the list is not sorted, perform one right shift operation. This involves moving the last element to the front and shifting all other elements one position to the right.
- If the loop completes without the list becoming sorted, it's impossible to sort it with right shifts. Return -1.

## Sort and Compare Rotations
This method is based on the property that if an array can be sorted by right shifts, it must be a rotated version of its own sorted form. The approach is to sort the array, then determine if the original array is a specific rotation of the sorted version and calculate the required shifts.
**Time:** O(n log n) - Dominated by the sorting step. The subsequent search and verification steps take O(n) time. · **Space:** O(n) - To store the sorted copy of the list.
**Pros:** More efficient than the brute-force approach.; Logically sound, based on the definition of a rotated sorted array.
**Cons:** The sorting step makes it less efficient than a linear-time solution.; Requires extra space for the sorted copy.
### Explanation
An array that is sortable by right shifts is a *left* rotation of its sorted version. For example, `[3,4,5,1,2]` is `[1,2,3,4,5]` rotated left by 2 positions. To sort it, we need 2 *right* shifts.

The algorithm first creates a sorted version of the input array, `sortedNums`. Then, it finds the index `p` of `nums[0]` in `sortedNums`. This `p` is the potential number of left rotations. It then verifies if the entire `nums` array matches `sortedNums` rotated left by `p`. If it matches, the number of right shifts needed is `p`.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int minimumRightShifts(List<Integer> nums) {
        int n = nums.size();
        List<Integer> sortedNums = new ArrayList<>(nums);
        Collections.sort(sortedNums);

        int p = -1; // index of nums.get(0) in sortedNums
        for (int i = 0; i < n; i++) {
            if (sortedNums.get(i).equals(nums.get(0))) {
                p = i;
                break;
            }
        }

        // Check if nums is a rotation of sortedNums starting at p
        for (int i = 0; i < n; i++) {
            if (!nums.get(i).equals(sortedNums.get((i + p) % n))) {
                return -1;
            }
        }

        // If p is 0, it's already sorted, 0 shifts.
        // If p > 0, it's a left rotation by p, which needs p right shifts.
        return p;
    }
}
```
### Algorithm
- Create a sorted copy of the input list `nums`, let's call it `sortedNums`.
- Find the index `p` where the first element of the original list, `nums.get(0)`, appears in `sortedNums`.
- Verify if the original `nums` list is a left rotation of `sortedNums` by `p` positions. This is done by checking if `nums.get(i)` equals `sortedNums.get((i + p) % n)` for all `i` from 0 to `n-1`.
- If the verification fails at any point, it means `nums` is not a valid rotation, and it's impossible to sort. Return -1.
- If the verification passes, the number of right shifts needed to sort the list is equal to `p`. Return `p`.

## Single Pass by Finding the Break Point
This is the most optimal approach. It leverages the structural property of a rotated sorted array: it can have at most one 'break point' where an element is greater than its next element (considering the array wraps around). By finding this break point in a single pass, we can determine sortability and the number of shifts.
**Time:** O(n) - The list is traversed only once to find the break points. · **Space:** O(1) - Only a few variables are used to store the count and index of break points, regardless of the input size.
**Pros:** Extremely efficient with linear time complexity.; Requires constant extra space.; Solves the problem in a single pass through the data.
**Cons:** The logic, while efficient, can be slightly less intuitive to derive compared to brute force.
### Explanation
The algorithm scans the array once to find the number of indices `i` where `nums[i] > nums[i+1]`. These are called 'break points'.

1.  **Zero Break Points**: If there are no such indices, the array is already sorted. The answer is 0.
2.  **More Than One Break Point**: If there is more than one such index (e.g., `[3,1,4,2]`), the array is not a simple rotation of a sorted array and cannot be sorted by shifts. The answer is -1.
3.  **Exactly One Break Point**: If there is exactly one break point at index `p`, the array could be a valid rotation. We must perform a final 'wrap-around' check: the last element must be smaller than or equal to the first element (`nums[n-1] <= nums[0]`). If this holds, the array is sortable. The number of shifts required is the number of elements that are 'out of place', which are all the elements after the break point. The count is `n - 1 - p`.

This entire process is done in a single pass over the array.

```java
import java.util.List;

class Solution {
    public int minimumRightShifts(List<Integer> nums) {
        int n = nums.size();
        if (n <= 1) {
            return 0;
        }

        int breakPointIndex = -1;
        int breakPointCount = 0;

        for (int i = 0; i < n - 1; i++) {
            if (nums.get(i) > nums.get(i + 1)) {
                breakPointIndex = i;
                breakPointCount++;
            }
        }

        if (breakPointCount > 1) {
            // More than one dip, impossible to sort by rotation.
            return -1;
        }

        if (breakPointCount == 0) {
            // Already sorted.
            return 0;
        }

        // One break point found. Check the wrap-around condition.
        if (nums.get(n - 1) > nums.get(0)) {
            return -1;
        }

        // The number of shifts is the number of elements after the break point.
        return n - 1 - breakPointIndex;
    }
}
```
### Algorithm
- Initialize `breakPointCount = 0` and `breakPointIndex = -1`.
- Iterate through the list from `i = 0` to `n-2`. If `nums.get(i) > nums.get(i+1)`, this is a 'break point'. Increment `breakPointCount` and record the index `i` in `breakPointIndex`.
- After the loop, check `breakPointCount`:
  - If `breakPointCount == 0`, the list is already sorted. Return 0.
  - If `breakPointCount > 1`, the list is not a simple rotation of a sorted list. Return -1.
  - If `breakPointCount == 1`, the list might be a valid rotated sorted list. Perform a final 'wrap-around' check: `nums.get(n-1) > nums.get(0)`. If this is true, it's impossible to sort. Return -1.
- If all checks pass for a single break point, the number of shifts is the count of elements after the break point, which is `n - 1 - breakPointIndex`. Return this value.

# Solutions
### Java

```java
class Solution {
public
  int minimumRightShifts(List<Integer> nums) {
    int n = nums.size();
    int i = 1;
    while (i < n && nums.get(i - 1) < nums.get(i)) {
      ++i;
    }
    int k = i + 1;
    while (k < n && nums.get(k - 1) < nums.get(k) &&
           nums.get(k) < nums.get(0)) {
      ++k;
    }
    return k < n ? -1 : n - i;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumRightShifts(vector<int> &nums) {
    int n = nums.size();
    int i = 1;
    while (i < n && nums[i - 1] < nums[i]) {
      ++i;
    }
    int k = i + 1;
    while (k < n && nums[k - 1] < nums[k] && nums[k] < nums[0]) {
      ++k;
    }
    return k < n ? -1 : n - i;
  }
};

```

### Python

```python
class Solution:
    def minimumRightShifts(self, nums: List[int]) -> int: n = len(nums) i = 1 while i < n and nums[i - 1] < nums[i]: i += 1 k = i + 1 while k < n and nums[k - 1] < nums[k] < nums[0]: k += 1 return - 1 if k < n else n - i

```