Scale Engineer

Minimum Right Shifts to Sort the Array

Easy
#2552Time: 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.1 company
Data structures
Array
Companies
Accenture

Prompt

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.

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 = 0 and breakPointIndex = -1.
  • Iterate through the list from i = 0 to n-2. If nums.get(i) > nums.get(i+1), this is a 'break point'. Increment breakPointCount and record the index i in breakPointIndex.
  • 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 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'.

  1. Zero Break Points: If there are no such indices, the array is already sorted. The answer is 0.
  2. 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.
  3. 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 is n - 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.

Solutions

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;  }}

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

← Previous

Previous problem

Next →

Next problem