Watch 9 video solutions for Minimum Right Shifts to Sort the Array, a easy level problem involving Array. This walkthrough by Aryan Mittal has 1,801 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1001 <= nums[i] <= 100nums contains distinct integers.Problem Overview: You receive an integer array that may have been rotated several times. The task is to determine the minimum number of right shifts required to make the array strictly non‑decreasing. If no number of shifts produces a sorted array, return -1.
Approach 1: Simulate Rotation and Check Sorted Order (O(n²) time, O(1) space)
The straightforward method tries every possible number of right rotations. For each shift k, rotate the array (or simulate the index mapping) and verify whether the resulting order is sorted. The check itself requires a full linear scan to confirm that every adjacent pair satisfies nums[i] <= nums[i+1]. Since there are n possible rotations and each validation takes O(n), the overall complexity becomes O(n²). This approach works for small inputs and is useful for building intuition about how array rotation changes element order.
Approach 2: Find the Minimum Shifts with Pivot Detection (O(n) time, O(1) space)
A rotated sorted array has a clear structural property: exactly one position where the order breaks. Scan the array once and count how many times nums[i] > nums[i+1]. This index marks the rotation pivot. If more than one such break exists, the array cannot be transformed into a sorted array using rotations, so return -1. If no break exists, the array is already sorted and the answer is 0. Otherwise, the number of right shifts required equals n - pivot - 1, where pivot is the index where the decrease occurs. A final check ensures the last element does not violate the first element when considering the circular order. This linear scan makes the solution optimal and avoids any actual rotation.
This technique relies on understanding properties of rotated sorted arrays, a common concept in array problems and sorting validations. Many rotation-related questions use a similar pivot-detection pattern or a circular traversal strategy.
Recommended for interviews: Pivot detection is the expected solution. It demonstrates that you recognize the structure of a rotated sorted array and can solve the problem in O(n) time with constant space. The brute-force simulation is still useful during interviews to explain the baseline logic before optimizing.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulate Rotation and Check Sorted Order | O(n²) | O(1) | Useful for understanding rotation behavior or when constraints are very small |
| Pivot Detection in Rotated Array | O(n) | O(1) | Best approach for interviews and large inputs; detects the single order break |