Minimum Right Shifts to Sort the Array
EasyPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize
breakPointCount = 0andbreakPointIndex = -1. - Iterate through the list from
i = 0ton-2. Ifnums.get(i) > nums.get(i+1), this is a 'break point'. IncrementbreakPointCountand record the indexiinbreakPointIndex. - 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
- 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.
Walkthrough
The algorithm scans the array once to find the number of indices i where nums[i] > nums[i+1]. These are called 'break points'.
- Zero Break Points: If there are no such indices, the array is already sorted. The answer is 0.
- 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. - 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 isn - 1 - p.
This entire process is done in a single pass over the array.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Create a copy of the input list
numsto avoid modifying the original. - Loop a variable
shiftsfrom 0 ton-1, wherenis the size of the list. - Inside the loop, first check if the current list is sorted. A helper function
isSortedcan iterate from the first element to the second-to-last, checking ifarr[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.
Walkthrough
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
ntimes, representing the number of shifts. - In each iteration, a helper function
isSortedchecks 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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Create a sorted copy of the input list
nums, let's call itsortedNums. - Find the index
pwhere the first element of the original list,nums.get(0), appears insortedNums. - Verify if the original
numslist is a left rotation ofsortedNumsbyppositions. This is done by checking ifnums.get(i)equalssortedNums.get((i + p) % n)for allifrom 0 ton-1. - If the verification fails at any point, it means
numsis 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. Returnp.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 - iVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.