Minimum Right Shifts to Sort the Array — Problem & Solution
Minimum Right Shifts to Sort the Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Minimum Right Shifts to Sort the Array is an easy coding problem on arrays, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A right shift moves every element one position to the right, with the last element wrapping around to the front.
Given an array nums of distinct positive integers, return the minimum number of right shifts that sorts it in increasing order, or -1 if no number of shifts can.
Example 1
Input: nums = [3,4,5,1,2]
Output: 2
Explanation: Two right shifts give [1,2,3,4,5].
Example 2
Input: nums = [1,3,5]
Output: 0
Explanation: Already sorted.
Example 3
Input: nums = [2,1,4]
Output: -1
Constraints
1 <= nums.length <= 1001 <= nums[i] <= 100All values are distinct.
Hints for Minimum Right Shifts to Sort the Array
Hint 1
A sorted array that has been rotated has exactly one place where a value is followed by a smaller one — counting the wrap-around.
Hint 2
Zero such drops means the array is already sorted.
Hint 3
More than one means no rotation can fix it.
How to solve Minimum Right Shifts to Sort the Array
A rotation of a sorted array is characterised by having at most one "drop" in its cyclic order. The drop's position tells you exactly how far it was rotated.
Approach
- Walk
ifrom 0 ton-1, comparingnums[i]withnums[(i+1) % n]— the modulo covers the wrap. - Count the drops and remember the index of the last one.
- Zero drops means already sorted, so return 0.
- More than one drop means no rotation works, so return
-1. - Otherwise return
n - 1 - at, the number of right shifts that moves the drop to the wrap position.
Why it works
Right-shifting by k maps index i to (i + k) % n. Sorting requires the smallest element to land at index 0, which happens when the drop sits exactly at the boundary — giving k = n - 1 - at.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Skipping the wrap comparison misses the drop for arrays like
[2,3,1]. - Confusing right shifts with left shifts inverts the count.
- A single-element array has zero drops and answers 0.
Reference solution
Python
from typing import List
def minimumRightShifts(nums: List[int]) -> int:
n = len(nums)
drops = 0
at = -1
for i in range(n):
if nums[i] > nums[(i + 1) % n]:
drops += 1
at = i
if drops == 0:
return 0
if drops > 1:
return -1
return n - 1 - atJava
public static int minimumRightShifts(int[] nums) {
int n = nums.length;
int drops = 0, at = -1;
for (int i = 0; i < n; i++) {
if (nums[i] > nums[(i + 1) % n]) { drops++; at = i; }
}
if (drops == 0) return 0;
if (drops > 1) return -1;
return n - 1 - at;
}C++
int minimumRightShifts(vector<int>& nums) {
int n = (int) nums.size();
int drops = 0, at = -1;
for (int i = 0; i < n; i++) {
if (nums[i] > nums[(i + 1) % n]) { drops++; at = i; }
}
if (drops == 0) return 0;
if (drops > 1) return -1;
return n - 1 - at;
}JavaScript
var minimumRightShifts = function(nums) {
const n = nums.length;
let drops = 0, at = -1;
for (let i = 0; i < n; i++) {
if (nums[i] > nums[(i + 1) % n]) { drops++; at = i; }
}
if (drops === 0) return 0;
if (drops > 1) return -1;
return n - 1 - at;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays