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.

Python Solution

1from typing import List
2
3class Solution:
4
5    def minimum_right_shifts(self, nums: List[int]) -> int:
6        # Determine the length of the input list `nums`
7        length = len(nums)
8      
9        # Initialize the index `i` to start checking the ascending order from the beginning of the list
10        i = 1
11      
12        # Find the first breaking point where ascending order is violated
13        while i < length and nums[i - 1] < nums[i]:
14            i += 1
15      
16        # If there was no breaking point, the list is already in ascending order
17        if i == length:
18            return 0
19      
20        # Initialize `k` for the second part of the task to identify if the right-shift requirement is met.
21        k = i + 1
22      
23        # Check if the rest of the list after the breaking point is in ascending order and 
24        # that it is less than the first element (to ensure a proper shifting sequence)
25        while k < length and nums[k - 1] < nums[k] < nums[0]:
26            k += 1
27      
28        # If `k` did not reach end of the list, it means the right-shift to fix is impossible
29        return -1 if k < length else length - i  # Return the number of shifts or -1 if not possible
30
31# Example of creating an instance of the solution and using the method
32solution_instance = Solution()
33print(solution_instance.minimum_right_shifts([3, 4, 5, 1, 2]))  # Example output: 3 because it takes three right shifts for the list to become sorted
34

Java Solution

1class Solution {
2    public int minimumRightShifts(List<Integer> nums) {
3        // Get the size of the list
4        int listSize = nums.size();
5      
6        // Initialize an index to track how many elements are
7        // in non-decreasing order starting from the beginning of the list
8        int nonDecreasingIndex = 1;
9      
10        // Iterate through the list until elements are no longer in
11        // non-decreasing order, starting from the second element
12        while (nonDecreasingIndex < listSize && nums.get(nonDecreasingIndex - 1) < nums.get(nonDecreasingIndex)) {
13            ++nonDecreasingIndex;
14        }
15      
16        // Once the non-decreasing sequence is broken, start another
17        // index to track the rest of the list if the elements are in non-decreasing order
18        // and also less than the first element of the list (to ensure proper rotation)
19        int checkIndex = nonDecreasingIndex + 1;
20        while (checkIndex < listSize && nums.get(checkIndex - 1) < nums.get(checkIndex) && nums.get(checkIndex) < nums.get(0)) {
21            ++checkIndex;
22        }
23      
24        // If the checkIndex hasn't reached the end of the list, it means that the list can't be
25        // sorted by right rotations alone, so we return -1
26        // Otherwise, return the number of right shifts required, which is the size of the list minus
27        // the index of the initial non-decreasing sequence
28        return checkIndex < listSize ? -1 : listSize - nonDecreasingIndex;
29    }
30}
31

C++ Solution

1class Solution {
2public:
3    int minimumRightShifts(vector<int>& nums) {
4        // Get the size of the vector nums.
5        int numsSize = nums.size();
6
7        // Initialize an index to keep track of the sequence.
8        int index = 1;
9
10        // Loop through the vector to find when the ascending sequence breaks.
11        while (index < numsSize && nums[index - 1] < nums[index]) {
12            ++index;
13        }
14
15        // If the entire vector is in ascending order, no right shift is needed.
16        if (index == numsSize) {
17            return 0;
18        }
19
20        // Initialize an index for the second part of the sequence.
21        int secondIndex = index + 1;
22
23        // Loop through the second part to validate ascending order 
24        // till an element is less than the first element of the vector.
25        while (secondIndex < numsSize && 
26               nums[secondIndex - 1] < nums[secondIndex] && 
27               nums[secondIndex] < nums[0]) {
28            ++secondIndex;
29        }
30
31        // If secondIndex did not reach the end, sequence is not strictly ascending,
32        // return -1 indicating it's impossible to achieve the condition.
33        if (secondIndex < numsSize) {
34            return -1;
35        }
36
37        // Return the number of right shifts needed which is the length of the vector
38        // minus the length of the initial ascending sequence.
39        return numsSize - index;
40    }
41};
42

Typescript Solution

1/**
2 * Computes the minimum number of right shifts required to sort the array in non-decreasing order.
3 * If it's impossible to sort the array with only right shifts, the function returns -1.
4 * @param {number[]} nums - The input array of numbers.
5 * @return {number} The minimum number of shifts required, or -1 if impossible.
6 */
7function minimumRightShifts(nums: number[]): number {
8    // Get the length of the array.
9    const length = nums.length;
10  
11    // Initialize the first index to 1.
12    let currentIndex = 1;
13  
14    // Find the first element that is smaller than its previous element (breaks the increasing order).
15    while (currentIndex < length && nums[currentIndex - 1] < nums[currentIndex]) {
16        currentIndex++;
17    }
18  
19    // If we have reached the end of the array, no right shifts are needed.
20    if (currentIndex === length) {
21        return 0;
22    }
23  
24    // Define a variable to start checking for the correct position of first element after shifting.
25    let indexToCheck = currentIndex;
26  
27    // Check that the remaining elements are still in increasing order and smaller than the first element.
28    while (indexToCheck < length && nums[indexToCheck - 1] < nums[indexToCheck] && nums[indexToCheck] < nums[0]) {
29        indexToCheck++;
30    }
31  
32    // If indexToCheck has not reached the end, sorting is impossible.
33    return indexToCheck < length ? -1 : length - currentIndex;
34}
35

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


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫