Minimum Right Shifts to Sort the Array

EASY

Description

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

Checkout 3 different approaches to solve Minimum Right Shifts to Sort the Array. Click on different approaches to view the approach and algorithm in detail.

Single Pass by Finding the Break Point

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.

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 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 Analysis

Time Complexity: O(n) - The list is traversed only once to find the break points.Space Complexity: O(1) - Only a few variables are used to store the count and index of break points, regardless of the input size.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Minimum Right Shifts to Sort the Array. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Minimum Right Shifts to Sort the Array

Data Structures:

Array

Companies:

Accenture |