Problem Description

You have an array nums of length n containing distinct positive integers (indexed from 0). Your task is to determine the minimum number of right shifts needed to sort the array in ascending order. If it's impossible to sort the array using only right shifts, return -1.

A right shift operation moves every element one position to the right in a circular manner. Specifically, the element at index i moves to index (i + 1) % n. This means the last element wraps around to become the first element.

For example, if nums = [3, 4, 5, 1, 2]:

• After 1 right shift: [2, 3, 4, 5, 1]
• After 2 right shifts: [1, 2, 3, 4, 5] (sorted)

The solution works by finding the rotation point in the array. It first traverses from the beginning to find where the sorted sequence breaks (where nums[i-1] > nums[i]). Then it checks if the remaining elements form a valid continuation that could wrap around to the beginning. If the array can be sorted through rotation, the answer is n - i where i is the position where the first sorted sequence ends. Otherwise, it returns -1.

The key insight is that for an array to be sortable through right shifts, it must consist of at most two sorted segments where the second segment (if it exists) contains values smaller than the first element of the first segment.

Intuition

Think about what happens when we perform right shifts on an array. Each right shift moves all elements one position to the right circularly. If we keep doing this, we're essentially rotating the array. The key observation is that if an array can be sorted through right shifts, it must already be "almost sorted" in a specific way.

Consider a sorted array that has been rotated some number of times. What does it look like? It would have two parts: a sorted sequence from some point to the end, followed by another sorted sequence from the beginning that continues where the first one left off. For example, [3, 4, 5, 1, 2] is essentially [1, 2, 3, 4, 5] rotated left by 2 positions (or right by 3 positions).

This means the original array must have at most one "break point" where the ascending order is violated. If we find this break point, we can determine:

1. Whether the array can be sorted at all (by checking if everything after the break point is sorted and fits before the beginning)
2. How many right shifts are needed (which would be n - position_of_break)

The algorithm naturally follows: we scan for where the first sorted sequence ends (where nums[i-1] > nums[i]). Then we verify that everything after this point forms a valid sorted sequence that could wrap around to the front. The condition nums[k] < nums[0] ensures that elements in the second part are smaller than the first element, maintaining the sorted order when rotated.

If we traverse the entire array without finding a break, the array is already sorted (return 0). If we find exactly one valid break point, we can calculate the shifts needed. If the second part doesn't maintain the required properties, sorting is impossible (return -1).

Solution Approach

The implementation uses a two-pointer traversal approach to identify and validate the rotation point in the array.

Step 1: Find the first break point

We initialize a pointer i = 1 and traverse the array from left to right, checking if each element is greater than the previous one (nums[i - 1] < nums[i]). We continue until we either:

• Reach the end of the array (meaning it's already sorted)
• Find a position where nums[i - 1] >= nums[i] (the break point)

This gives us the end position of the first sorted segment.

Step 2: Validate the second segment

Starting from k = i + 1, we traverse the remaining array to ensure:

• The elements continue to be in ascending order (nums[k - 1] < nums[k])
• Each element is less than the first element of the array (nums[k] < nums[0])

The second condition is crucial because when we perform right shifts, these elements will eventually wrap around to the beginning and must be smaller than nums[0] to maintain sorted order.

Step 3: Determine the result

After the second traversal:

• If k < n (didn't reach the end), it means either the second segment isn't sorted or contains elements that are too large to wrap around properly. Return -1.
• If k == n (reached the end successfully), the array can be sorted with n - i right shifts.

The special case where i == n (no break point found) means the array is already sorted, and n - i = 0 right shifts are needed, which is correct.

Time Complexity: O(n) - we traverse the array at most twice
Space Complexity: O(1) - only using a few variables for indices

Example Walkthrough

Let's walk through the solution with nums = [3, 4, 5, 1, 2]:

Step 1: Find the first break point

• Start with i = 1
• Check nums[0] < nums[1]: 3 < 4 ✓, increment i = 2
• Check nums[1] < nums[2]: 4 < 5 ✓, increment i = 3
• Check nums[2] < nums[3]: 5 < 1 ✗, found break point!
• First sorted segment ends at position i = 3

Step 2: Validate the second segment

• Start with k = i + 1 = 4
• Check nums[3] < nums[4]: 1 < 2 ✓ (sorted)
• Check nums[4] < nums[0]: 2 < 3 ✓ (can wrap around)
• Increment k = 5
• Since k == n, we've successfully validated the entire second segment

Step 3: Calculate result

• Array can be sorted with n - i = 5 - 3 = 2 right shifts

Verification:

• Original: [3, 4, 5, 1, 2]
• After 1 right shift: [2, 3, 4, 5, 1]
• After 2 right shifts: [1, 2, 3, 4, 5] ✓ Sorted!

Now let's see an impossible case with nums = [3, 1, 4, 2]:

Step 1: Find the first break point

• Start with i = 1
• Check nums[0] < nums[1]: 3 < 1 ✗, found break point at i = 1

Step 2: Validate the second segment

• Start with k = i + 1 = 2
• Check nums[1] < nums[2]: 1 < 4 ✓ (sorted)
• Check nums[2] < nums[0]: 4 < 3 ✗ (too large to wrap around!)
• Since the condition fails, return -1

The array cannot be sorted through right shifts because 4 is larger than 3, so when rotated, it would break the sorted order.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm uses two while loops that traverse the array sequentially:

• The first while loop starts from index 1 and continues while the array is in ascending order, incrementing i until it finds a position where nums[i-1] >= nums[i] or reaches the end. This loop runs at most n-1 iterations.
• The second while loop starts from index i+1 and continues while the elements are in ascending order and less than nums[0], incrementing k. This loop also runs at most n-i-1 iterations.

Since each element is visited at most once across both loops, and the loops run sequentially (not nested), the total number of operations is linear with respect to the array size. Therefore, the time complexity is O(n).

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space:

• Variables n, i, and k are integer variables that store indices or the array length.
• No additional data structures (arrays, lists, or other collections) are created.
• The space usage does not depend on the input size.

Therefore, the space complexity is O(1), which represents constant space usage.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Missing Edge Case: Already Sorted Array

The current implementation has a subtle bug when the array is already sorted. When break_point reaches n (no break found), the code sets current_position = n + 1, which causes the while loop condition current_position < n to be false immediately. This makes the function return n - n = 0, which is correct by coincidence, but the logic is flawed.

Problem Example:

nums = [1, 2, 3, 4, 5]  # Already sorted
# break_point becomes 5
# current_position starts at 6
# while loop doesn't execute
# Returns 5 - 5 = 0 (correct, but logic is wrong)

2. Incorrect Validation of Wraparound Condition

The condition nums[current_position] < nums[0] in the second while loop is too restrictive. It should check against the last element of the first segment (nums[break_point - 1]) to ensure proper continuation after rotation.

Problem Example:

nums = [4, 5, 1, 2, 3]
# First segment: [4, 5], Second segment: [1, 2, 3]
# The code checks if 3 < 4, which is true
# But we also need to ensure 3 < 5 for proper sorting after rotation

3. Off-by-One Error in Boundary Check

When break_point equals n, accessing nums[break_point] in the subsequent code would cause an index out of bounds error if not handled properly.

Corrected Solution

class Solution:
    def minimumRightShifts(self, nums: List[int]) -> int:
        n = len(nums)
      
        # Find the rotation point (where ascending order first breaks)
        rotation_point = 1
        while rotation_point < n and nums[rotation_point - 1] < nums[rotation_point]:
            rotation_point += 1
      
        # If no break point found, array is already sorted
        if rotation_point == n:
            return 0
      
        # Validate the second segment
        # 1. Must be sorted in ascending order
        # 2. Last element must be less than first element for valid rotation
        current = rotation_point
        while current < n:
            # Check ascending order within second segment
            if current > rotation_point and nums[current - 1] >= nums[current]:
                return -1
            # Check wraparound condition
            if nums[current] >= nums[0]:
                return -1
            current += 1
      
        # Additional check: last element of array must be less than first element
        # of the first sorted segment to ensure continuity after rotation
        if nums[n - 1] >= nums[0]:
            return -1
          
        return n - rotation_point

Key Improvements:

1. Explicitly handles the already-sorted case early
2. Separates the validation logic for clarity
3. Properly validates both ascending order within the second segment and the wraparound condition
4. Adds defensive checks to prevent index errors