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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Right Shifts to Sort the Array

Number: 3045

Difficulty: Easy

Paid? No

Companies: Amazon, Accenture

Problem Description

Given an array of distinct positive integers, determine the minimum number of right shifts required to sort the array in ascending order. A right shift means that every element moves one position to the right and the last element moves to the front. If it is impossible to sort the array using right shifts, return -1.

Key Insights

  • A sorted array that is rotated will have at most one "drop" (an index i where nums[i] > nums[i+1]).
  • If the array is already sorted (no drops), no shifts are required.
  • If there is one drop, the number of shifts needed is n - (drop index + 1), provided that the last element is less than or equal to the first element.
  • If there is more than one drop, the array cannot be sorted by cyclic right shifts, hence return -1.

Space and Time Complexity

Time Complexity: O(n) because we scan the array once.
Space Complexity: O(1) as only a few variables are used.

Solution

The solution involves scanning the array once to identify if it can be treated as a rotated version of a sorted array. Count the number of drops (where an element is greater than its next neighbor).

  • If no drops are found, the array is already sorted and zero shifts are needed.
  • If exactly one drop is found, then calculate the number of shifts as (n - drop_index - 1). However, a final check is necessary: ensure that the last element is not greater than the first element; otherwise, a valid sorted rotation is not possible.
  • If more than one drop is identified, then sorting by right shifts is impossible, so return -1.

The algorithm relies on simple linear traversal and arithmetic operations, making it both time and space efficient.

Code Solutions

def minimum_right_shifts(nums):
    # Get the length of the array
    n = len(nums)
    # Count the number of drops where the sequence descends
    drop_count = 0
    drop_index = -1
    for i in range(n - 1):
        # Check if the current element is greater than the next one
        if nums[i] > nums[i + 1]:
            drop_count += 1
            drop_index = i
    # If no drop is found, the array is already sorted
    if drop_count == 0:
        return 0
    # More than one drop means the array is not a rotated sorted array
    if drop_count > 1:
        return -1
    # Single drop found; check if the last element is less than or equal to the first element
    if nums[-1] > nums[0]:
        return -1
    # The number of shifts required equals n - (drop_index + 1)
    return n - (drop_index + 1)

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