Minimum Right Shifts to Sort the Array - Solution & Explanation
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 <= 1001 <= nums[i] <= 100numscontains distinct integers.
Approach Overview
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 1: Find the Minimum Shifts with Pivot Detection
One way to solve the problem is to identify the pivot point in the array where the ordering breaks. We iterate through `nums` to find the first instance where an element is greater than its successor. This breaking point indicates where the smallest element of the array needs to move in order to get the array sorted. If the entire array can be traversed without finding such a break, the array is already sorted, and zero shifts are needed.
The idea is to detect the pivot index. With the pivot identified, verify the conditions for potential shifts. If such a pivot exists, the number of shifts required is calculated as the size of the array minus the pivot index. If no valid pivot could be found to sort the array, return -1.
This solution iterates through the array to find a pivot where an element is greater than its next counterpart (with modulo for wrapping). It marks this position as a potential sorting point. If another such break is found, the function returns -1 as the array cannot be sorted via right shifts.
Complexity
Time Complexity: O(n), where n is the length of the array, as we perform a single pass through the array.
Space Complexity: O(1), since we're using only a constant amount of extra space.
Approach 2: Simulate Rotation and Check Sorted Order
A direct yet less optimal solution is to simulate the right shift and check if the array becomes sorted at any iteration. This method actively shifts every element one step and compares the array with its sorted version in every cycle. Given the distinct integers and size constraints, this approach performs feasible trials to find a minimal rotation or declare impossibility when unsatisfied.
The C solution creates functions to shift array elements and to check for sorted order. The main loop continues trying shifts until sorted form is found or all possibilities have been exhausted.
Complexity
Time Complexity: O(n^2) due to potential complete shift and check cycles.
Space Complexity: O(1) as only in-place element adjustments are employed.
Approach 3: Direct Traversal
First, we use a pointer i to traverse the array nums from left to right, finding a continuous increasing sequence until i reaches the end of the array or nums[i - 1] > nums[i]. Next, we use another pointer k to traverse the array nums from i + 1, finding a continuous increasing sequence until k reaches the end of the array or nums[k - 1] > nums[k] and nums[k] > nums[0]. If k reaches the end of the array, it means the array is already increasing, so we return n - i; otherwise, we return -1.
The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Find the Minimum Shifts with Pivot Detection | Time Complexity: O(n), where n is the length of the array, as we perform a single pass through the array. |
| Simulate Rotation and Check Sorted Order | Time Complexity: O(n^2) due to potential complete shift and check cycles. |
| Direct Traversal | — |
Detailed Complexity Analysis
| 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 |
Video Solution
🔴 2855. Minimum Right Shifts to Sort the Array II One Pass II O(n) II Biweekly Contest 113 • Aryan Mittal • 1,818 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Right Shifts to Sort the Array easy or hard?
Minimum Right Shifts to Sort the Array Python/Java solution
How to solve Minimum Right Shifts to Sort the Array in O(n)?
What is the best approach for Minimum Right Shifts to Sort the Array?
Is Minimum Right Shifts to Sort the Array asked at Google/Amazon/Meta?
What data structure is used in Minimum Right Shifts to Sort the Array?
What is the time complexity of Minimum Right Shifts to Sort the Array?
Ready to solve this problem?
Practice Minimum Right Shifts to Sort the Array with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor