2855. Minimum Right Shifts to Sort the Array - Solution

The problem

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 <= 100
1 <= nums[i] <= 100
nums contains 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.

Python

def min_right_shifts(nums):
    n = len(nums)
    pivot = -1
    
    for i in range(n):
        if nums[i] > nums[(i + 1) % n]:
            if pivot != -1:
                return -1
            pivot = i + 1
    return 0 if pivot == -1 else n - pivot

# Test Case
def test_case():
    nums = [3, 4, 5, 1, 2]
    print(min_right_shifts(nums))

test_case()

Java

public class Solution {
    public static int minRightShifts(int[] nums) {
        int n = nums.length;
        int pivot = -1;
        
        for (int i = 0; i < n; ++i) {
            if (nums[i] > nums[(i + 1) % n]) {
                if (pivot != -1) return -1;
                pivot = i + 1;
            }
        }
        return (pivot == -1) ? 0 : (n - pivot);
    }

    public static void main(String[] args) {
        int[] nums = {3, 4, 5, 1, 2};
        System.out.println(minRightShifts(nums));
    }
}

C++

#include <vector>
#include <iostream>
using namespace std;

int minRightShifts(vector<int>& nums) {
    int n = nums.size();
    int pivot = -1;
    
    for (int i = 0; i < n; ++i) {
        if (nums[i] > nums[(i + 1) % n]) {
            if (pivot != -1) return -1;
            pivot = i + 1;
        }
    }
    return (pivot == -1) ? 0 : (n - pivot);
}

int main() {
    vector<int> nums = {3, 4, 5, 1, 2};
    cout << minRightShifts(nums) << endl;
    return 0;
}

JavaScript

function minRightShifts(nums) {
    const n = nums.length;
    let pivot = -1;

    for (let i = 0; i < n; ++i) {
        if (nums[i] > nums[(i + 1) % n]) {
            if (pivot !== -1) return -1;
            pivot = i + 1;
        }
    }
    return pivot === -1 ? 0 : n - pivot;
}

console.log(minRightShifts([3, 4, 5, 1, 2]));

#include <stdio.h>

int minRightShifts(int* nums, int n) {
    int pivot = -1;
    
    for (int i = 0; i < n; ++i) {
        if (nums[i] > nums[(i + 1) % n]) {
            if (pivot != -1) return -1;
            pivot = i + 1;
        }
    }
    return (pivot == -1) ? 0 : (n - pivot);
}

int main() {
    int nums[] = {3, 4, 5, 1, 2};
    int n = sizeof(nums) / sizeof(nums[0]);
    printf("%d\n", minRightShifts(nums, n));
    return 0;
}

using System;

class Program {
    static int MinRightShifts(int[] nums) {
        int n = nums.Length;
        int pivot = -1;

        for (int i = 0; i < n; ++i) {
            if (nums[i] > nums[(i + 1) % n]) {
                if (pivot != -1) return -1;
                pivot = i + 1;
            }
        }
        return (pivot == -1) ? 0 : (n - pivot);
    }

    static void Main() {
        int[] nums = { 3, 4, 5, 1, 2 };
        Console.WriteLine(MinRightShifts(nums));
    }
}

This Python implementation loops over each index to identify the first time an element is larger than its successor, calculating whether and how the data can be shifted to achieve a sorted state.

Complexity

Time Complexity: O(n) because of a single pass through the list, examining each entry individually.
Space Complexity: O(1) as only index markers are utilized without additional structures.

Try this approach in the editor

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.

Python

def is_sorted(nums):
    return all(nums[i] <= nums[i + 1] for i in range(len(nums) - 1))

def right_shift(nums):
    nums.insert(0, nums.pop())

def min_right_shifts(nums):
    n = len(nums)
    for shifts in range(n):
        if is_sorted(nums):
            return shifts
        right_shift(nums)
    return -1

# Test Case
def test_case():
    nums = [3, 4, 5, 1, 2]
    print(min_right_shifts(nums))

test_case()

Java

import java.util.*;

public class Solution {
    private static boolean isSorted(int[] nums) {
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i - 1] > nums[i]) return false;
        }
        return true;
    }

    private static void rightShift(int[] nums) {
        int last = nums[nums.length - 1];
        System.arraycopy(nums, 0, nums, 1, nums.length - 1);
        nums[0] = last;
    }

    public static int minRightShifts(int[] nums) {
        int n = nums.length;
        for (int shifts = 0; shifts < n; ++shifts) {
            if (isSorted(nums)) return shifts;
            rightShift(nums);
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {3, 4, 5, 1, 2};
        System.out.println(minRightShifts(nums));
    }
}

C++

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool isSorted(const vector<int>& nums) {
    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i - 1] > nums[i]) return false;
    }
    return true;
}

void rightShift(vector<int>& nums) {
    int last = nums.back();
    nums.pop_back();
    nums.insert(nums.begin(), last);
}

int minRightShifts(vector<int>& nums) {
    int n = nums.size();
    for (int shifts = 0; shifts < n; ++shifts) {
        if (isSorted(nums)) return shifts;
        rightShift(nums);
    }
    return -1;
}

int main() {
    vector<int> nums = {3, 4, 5, 1, 2};
    cout << minRightShifts(nums) << endl;
    return 0;
}

JavaScript

function isSorted(nums) {
    for (let i = 1; i < nums.length; i++) {
        if (nums[i - 1] > nums[i]) return false;
    }
    return true;
}

function rightShift(nums) {
    nums.unshift(nums.pop());
}

function minRightShifts(nums) {
    const n = nums.length;
    for (let shifts = 0; shifts < n; ++shifts) {
        if (isSorted(nums)) return shifts;
        rightShift(nums);
    }
    return -1;
}

console.log(minRightShifts([3, 4, 5, 1, 2]));

#include <stdio.h>
#include <stdbool.h>

bool isSorted(int* arr, int n) {
    for (int i = 1; i < n; ++i) {
        if (arr[i - 1] > arr[i]) return false;
    }
    return true;
}

void rightShift(int* arr, int n) {
    int last = arr[n - 1];
    for (int i = n - 1; i > 0; --i) {
        arr[i] = arr[i - 1];
    }
    arr[0] = last;
}

int minRightShifts(int* nums, int n) {
    for (int shifts = 0; shifts < n; ++shifts) {
        if (isSorted(nums, n)) return shifts;
        rightShift(nums, n);
    }
    return -1;
}

int main() {
    int nums[] = {3, 4, 5, 1, 2};
    int n = 5;
    printf("%d\n", minRightShifts(nums, n));
    return 0;
}

using System;
using System.Linq;

class Program {
    static bool IsSorted(int[] nums) {
        for (int i = 1; i < nums.Length; ++i) {
            if (nums[i - 1] > nums[i]) return false;
        }
        return true;
    }

    static void RightShift(int[] nums) {
        int last = nums[nums.Length - 1];
        Array.Copy(nums, 0, nums, 1, nums.Length - 1);
        nums[0] = last;
    }

    static int MinRightShifts(int[] nums) {
        int n = nums.Length;
        for (int shifts = 0; shifts < n; ++shifts) {
            if (IsSorted(nums)) return shifts;
            RightShift(nums);
        }
        return -1;
    }

    static void Main() {
        int[] nums = { 3, 4, 5, 1, 2 };
        Console.WriteLine(MinRightShifts(nums));
    }
}

This Python solution emphasizes rotation by transferring the last element forward by repositioning during each iterative attempt, and checks each rotation for the arrangement's validity compared to sorted criteria.

Complexity

Time Complexity: O(n^2) via vector operations within cyclical checks.
Space Complexity: O(1) correlating with absence of extra-primary constructions amid computations.

Try this approach in the editor

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.

TypeScript

function minimumRightShifts(nums: number[]): number {
    const n = nums.length;
    let i = 1;
    while (i < n && nums[i - 1] < nums[i]) {
        ++i;
    }
    let k = i + 1;
    while (k < n && nums[k - 1] < nums[k] && nums[k] < nums[0]) {
        ++k;
    }
    return k < n ? -1 : n - i;
}

func minimumRightShifts(nums []int) int {
	n := len(nums)
	i := 1
	for i < n && nums[i-1] < nums[i] {
		i++
	}
	k := i + 1
	for k < n && nums[k-1] < nums[k] && nums[k] < nums[0] {
		k++
	}
	if k < n {
		return -1
	}
	return n - i
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Find the Minimum Shifts with Pivot Detection	Time Complexity: O(n) because of a single pass through the list, examining each entry individually. Space Complexity: O(1) as only index markers are utilized without additional structures.
Simulate Rotation and Check Sorted Order	Time Complexity: O(n^2) via vector operations within cyclical checks. Space Complexity: O(1) correlating with absence of extra-primary constructions amid computations.
Direct Traversal	–

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

Frequently asked questions

Is Minimum Right Shifts to Sort the Array easy or hard?

The problem is categorized as Easy because it relies on recognizing the property of rotated sorted arrays. Once you detect the single pivot where ordering breaks, computing the number of right shifts becomes straightforward with a simple formula.

Minimum Right Shifts to Sort the Array Python/Java solution

Most implementations follow the same O(n) pivot detection logic. Iterate through the array, track the index where nums[i] > nums[i+1], and compute the required shifts from that pivot. This approach works consistently across Python, Java, C++, JavaScript, and other languages.

How to solve Minimum Right Shifts to Sort the Array in O(n)?

Iterate through the array and count the number of indices where nums[i] > nums[i+1]. If more than one such index appears, the array cannot become sorted using rotations. If exactly one break exists at index i, the minimum right shifts required is n - i - 1. If no break exists, the array is already sorted.

What is the best approach for Minimum Right Shifts to Sort the Array?

The optimal approach uses pivot detection. Scan the array once and count positions where nums[i] > nums[i+1]. A valid rotated sorted array has at most one such break. If one break exists, the required right shifts equal n - pivot - 1. This runs in O(n) time and O(1) space.

Is Minimum Right Shifts to Sort the Array asked at Google/Amazon/Meta?

Rotation and pivot detection problems frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, interviewers often test the same concept using rotated sorted arrays and order validation techniques.

What data structure is used in Minimum Right Shifts to Sort the Array?

The problem mainly uses a basic array traversal. No additional data structures are required. The key idea is detecting the pivot point in a rotated sorted array using a simple linear scan.

What is the time complexity of Minimum Right Shifts to Sort the Array?

The optimal solution runs in O(n) time because the array is scanned once to detect the pivot where the sorted order breaks. Space complexity is O(1) since no additional data structures are required. A brute-force rotation simulation approach takes O(n²) time.

Minimum Right Shifts to Sort the Array solution and explanation

The problem

Approach overview

Approach 1: Find the Minimum Shifts with Pivot Detection

Approach 2: Simulate Rotation and Check Sorted Order

Approach 3: Direct Traversal

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Minimum Right Shifts to Sort the Array solution and explanation

The problem

Approach overview

Approach 1: Find the Minimum Shifts with Pivot Detection

Approach 2: Simulate Rotation and Check Sorted Order

Approach 3: Direct Traversal

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems