Minimum Right Shifts to Sort the Array

Easy
566.

Minimum Right Shifts to Sort the Array

Minimum Right Shifts to Sort the Array is an easy coding problem on arrays, asked in Amazon and Adobe interviews.

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 <= 100
  • 1 <= nums[i] <= 100
  • All values are distinct.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumRightShifts = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 100
  • 1 <= nums[i] <= 100
  • All values are distinct.

Hints for Minimum Right Shifts to Sort the Array

  1. 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.

  2. Hint 2

    Zero such drops means the array is already sorted.

  3. 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

  1. Walk i from 0 to n-1, comparing nums[i] with nums[(i+1) % n] — the modulo covers the wrap.
  2. Count the drops and remember the index of the last one.
  3. Zero drops means already sorted, so return 0.
  4. More than one drop means no rotation works, so return -1.
  5. 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 - at

Java

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