2855. Minimum Right Shifts to Sort the Array

Problem Description

In this problem, we are given an array nums which contains distinct positive integers in a 0-indexed fashion, meaning the index of the array starts at 0. The goal is to determine the minimum number of right shifts needed to sort the array in ascending order. A right shift means taking an element at index i and moving it to index (i + 1) % n, where n is the length of the array. If the array can be sorted with right shifts, we return the minimum number of shifts required; otherwise, we return -1 to indicate that sorting is not possible with only right shifts.

A right shift effectively moves the last element of the array to the front while shifting all other elements to the right by one position. This operation can be repeated many times to rotate the array. However, if the array is not a rotated version of a sorted array to begin with, it cannot be sorted by just right shifting.

Intuition

To solve this problem, we're going to leverage the fact that the array contains distinct positive integers. Given that the array can only be sorted by right shifts (or rotations), the original array must be a rotation of a sorted array. If it is not, then sorting it will be impossible.

The solution starts by stepping through the array while the integers remain in ascending order. The moment this order is violated, we know we've potentially found the point of rotation. From this 'breakpoint', the next step is to check if the array continues to increase up to the first element of the array (i.e., the element before the rotation point). If the order is again violated before reaching the end of the array, it means the array is not a rotation of a sorted array, so we cannot sort it with right shifts alone, and the solution should return -1. If we successfully reach the end of the array without any order violations, it means we've confirmed that the array is a rotation of a sorted array.

Finally, to find the minimum number of right shifts, we need to return the distance from the beginning of the array to the 'breakpoint' or rotation point. However, since we're doing right shifts which effectively move the end element to the front, what we actually want is the number of elements from the rotation point to the end of the array. Therefore, we subtract the index of the rotation point from the total number of elements n to get the minimum number of right shifts required.

Solution Approach

The implementation of the solution follows a straightforward algorithm to identify if the array is a single rotation of a sorted sequence and then calculates the minimum right shifts needed to sort the array.

The complete approach is as follows:

1. Initialize two pointers, i and k.

   • i starts from 1 because we want to compare with the previous element, and it marks the index we're checking for the ascending order.
   • k is used to determine if the remaining part of the array is increasing and is smaller than nums[0]. It starts from i + 1.

2. The first while loop finds the first occurrence where nums[i-1] >= nums[i]. This is the standard pattern to identify the break in ascending order. If i reaches the end of the array n without triggering the break condition, it means the array is already sorted, and no right shifts are needed; hence, return 0.

3. The second while loop starts from the index k and checks whether every number from that index onwards is less than nums[0] and the sequence is still increasing. If k reaches n without breaking the loop, the array is one rotation away from being sorted.

4. The return value:

   • If k has not reached n, it means that there's another break in the order, hence the sequence isn't just a single rotation of a sorted array, and sorting it by rotations is impossible. In this case, return -1.
   • Otherwise, return n - i, which indicates the minimum number of right shifts required to bring nums[i] to the 0th index, effectively sorting the array.

Here is how the code encapsulates this logic:

1class Solution:
2    def minimumRightShifts(self, nums: List[int]) -> int:
3        n = len(nums)
4        i = 1
5        while i < n and nums[i - 1] < nums[i]:
6            i += 1
7        if i == n:  # The array is already sorted.
8            return 0
9        k = i + 1
10        while k < n and nums[k - 1] < nums[k] < nums[0]:
11            k += 1
12        return -1 if k < n else n - i

This solution leverages simple array traversal and comparison without any complex data structures or advanced algorithms.

• No additional space complexity is introduced since we are only using a few integer variables (i, k, n).
• The time complexity is at most O(2n) since both loops could potentially iterate over the whole array, but never more than once per element, simplifying to O(n).

One key point in understanding this algorithm is how the sorted array property is used to verify the possibility of sorting by rotations and then calculating the minimal rotation if possible.

Example Walkthrough

Let's use an example to illustrate the solution approach. Consider the following array:

1nums = [3, 4, 5, 1, 2]

Now, let's walk through the approach step by step:

1. We initialize i to 1 as we want to start comparing from the first element with the previous one (index 0). Variable k is not used until later.

2. The initial state is i = 1, and we compare nums[i - 1] and nums[i]. The pair we are comparing is therefore (3, 4) which satisfies nums[i - 1] < nums[i], so we increment i to 2.

3. Continuing the loop, i now is 2, and we compare (4, 5). This also satisfies the ascending order so i is incremented to 3.

4. At i = 3, we compare (5, 1) and find that nums[i - 1] >= nums[i], which breaks the ascending order. According to our logic, this indicates where the array was potentially rotated.

5. We set k = i + 1 which is 4 in this case and enter the second while loop to verify that the remaining part of the array is still in ascending order and each element is less than nums[0].

6. Now, k = 4 and we compare (1, 2). The condition nums[k - 1] < nums[k] < nums[0] is satisfied as (1 < 2 < 3). Since k < n, we continue and increment k to 5.

7. As k equals to n (end of array), which means the loop was never broken and confirms that the array is a rotation of a sorted array.

8. Finally, we calculate the minimum number of right shifts required to sort the array which is n - i. In this case, n is 5 and i is 3, so we need 5 - 3 = 2 right shifts.

Therefore, the array [3, 4, 5, 1, 2] requires a minimum of 2 right shifts to be sorted in ascending order.

Solution Implementation

Time and Space Complexity

Time Complexity

The given Python function involves checking each element of the array exactly once in the two while loops. The first loop continues until it encounters a non-ascending pair (nums[i - 1] >= nums[i]), and the second loop continues until it reaches an element that does not satisfy the condition (nums[k - 1] < nums[k] < nums[0]) or until it reaches the end of the array.

Both loops have a worst-case scenario where they traverse the entire list (n being the length of the list).

• The first loop runs in O(n) time in the worst case.
• The second loop also runs in O(n) time in the worst case.

As both loops run sequentially, the overall time complexity of the function is O(n) + O(n) = O(n).

Space Complexity

The function only uses a few integer variables (i, k, n) and does not allocate any additional space that grows with the size of the input. Therefore, the space complexity of the function is O(1).

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