We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Right Shifts to Sort the Array

Difficulty: Easy

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

Key Insights

  • The array can only be sorted by right shifts if there is at most one point where the order breaks (i.e., where a larger number is followed by a smaller number).
  • If the array is already sorted, the number of shifts required is zero.
  • If there are multiple breaks in the order, it is impossible to sort the array using right shifts.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To determine the minimum number of right shifts needed to sort the array, we can follow these steps:

  1. Traverse the array to identify the number of "break points" where the current element is greater than the next element.
  2. If there are more than one break points, return -1 as it's impossible to sort the array with right shifts.
  3. If there are no break points, the array is already sorted, so return 0.
  4. If there is exactly one break point, calculate the number of right shifts required to sort the array. This can be determined by the index of the break point.

Code Solutions

def min_right_shifts(nums):
    n = len(nums)
    break_points = 0
    break_index = -1

    for i in range(n):
        if nums[i] > nums[(i + 1) % n]:
            break_points += 1
            break_index = i

    if break_points > 1:
        return -1
    elif break_points == 0:
        return 0
    else:
        return n - (break_index + 1)

# Example usage
print(min_right_shifts([3, 4, 5, 1, 2]))  # Output: 2
← Back to All Questions