algoadvance

You are given a 0-indexed array nums of length n. The array nums can be right-shifted any number of times.

A right shift operation moves the last element of nums to the front:

Return the minimum number of right shifts required to sort nums in non-decreasing order. If it is impossible to sort the array using right shifts, return -1.

Example

Input: nums = [3, 4, 5, 1, 2]
Output: 3

Input: nums = [1, 3, 5]
Output: 0

Input: nums = [2, 1, 3, 4]
Output: -1

Clarifying Questions

  1. Is the array guaranteed to have no duplicates?
    • Yes, assume all elements are distinct as the problem does not mention handling duplicates.
  2. Can the array be empty?
    • No, the array will have at least one element.
  3. Is only right shifting allowed?
    • Yes, only right shifting is allowed as per the problem statement.

Strategy

  1. Identify sorted segments:
    • The main task is to identify if the array can be made sorted by any number of right shifts.
    • For this, we need to identify a segment where the array is already in non-decreasing order, and the rest of the array can be made sorted by right shifts.
  2. Find pivot point:
    • Find the point where the order is disrupted. This point will be the pivot for the right shift.
    • If such a pivot exists, then the number of shifts needed would be the position of this pivot from the end of the array.
  3. Form a single-pass check:
    • Start from the first element, traverse the array to find the position where nums[i] > nums[i+1].
    • This position determines the point after which the right shift must start.
  4. Validation:
    • Once the potential pivot is found, verify if rotating from this point sorts the array.
  5. Edge Cases:
    • If the array is already sorted, return 0.
    • If no pivot can sort the array, return -1.

Code

def minimum_right_shifts(nums):
    n = len(nums)
    pivot = -1

    # Finding the pivot
    for i in range(n - 1):
        if nums[i] > nums[i + 1]:
            pivot = i
            break
    
    # If pivot is not found, it means array is sorted
    if pivot == -1:
        return 0

    # Check if the array can be sorted with this pivot rotation
    for i in range(pivot + 1, n - 1):
        if nums[i] > nums[i + 1]:
            return -1
    
    # To verify, we need to make sure last element is smaller than first element
    if nums[-1] > nums[0]:
        return -1

    # The minimum shifts needed is length - 1 - pivot
    return n - 1 - pivot

# Example Usage
nums = [3, 4, 5, 1, 2]
print(minimum_right_shifts(nums))  # Output: 3

nums = [1, 3, 5]
print(minimum_right_shifts(nums))  # Output: 0

nums = [2, 1, 3, 4]
print(minimum_right_shifts(nums))  # Output: -1

Time Complexity

Try our interview co-pilot at AlgoAdvance.com