Teaching Kids Programming – Minimum Right Shifts to Sort the Array

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a 0-indexed array nums of length n containing distinct positive integers. Return the minimum number of right shifts required to sort nums and -1 if this is not possible.

A right shift is defined as shifting the element at index i to index (i + 1) % n, for all indices.

Example 1:
Input: nums = [3,4,5,1,2]
Output: 2
Explanation:
After the first right shift, nums = [2,3,4,5,1].
After the second right shift, nums = [1,2,3,4,5].
Now nums is sorted; therefore the answer is 2.

Example 2:
Input: nums = [1,3,5]
Output: 0
Explanation: nums is already sorted therefore, the answer is 0.

Example 3:
Input: nums = [2,1,4]
Output: -1
Explanation: It’s impossible to sort the array using right shifts.

Constraints:
1 <= nums.length <= 100
1 <= nums[i] <= 100
nums contains distinct integers.

How to Check if a List/Array is Sorted?

We can sort the array and compare the input, however, this is O(NLogN).

1
2
3

def is_sorted(arr):
    sa = list(sorted(arr))
    return arr == sa

def is_sorted(arr):
    sa = list(sorted(arr))
    return arr == sa

Another better algorithm is to check every consecutive elements in the array to see if they are assending.

1
2
3
4

def is_sorted(arr):
    if any(arr[v] < arr[v - 1] for v in range(1, len(arr))):
        return False
    return True

def is_sorted(arr):
    if any(arr[v] < arr[v - 1] for v in range(1, len(arr))):
        return False
    return True

Here is the version that uses the all keyword instead:

1
2

def is_sorted(arr):
    return all(arr[v] >= arr[v - 1] for v in range(1, len(arr)))

def is_sorted(arr):
    return all(arr[v] >= arr[v - 1] for v in range(1, len(arr)))

Algorithms to Find the Minimum Right Shifts to Sort the Array

We can convert the array to double-ended queue aka deque, and then simulate the process, up to N times, to see if any rotation/shift gives a sorted list. However, this may not be optimial depending as the time complexity is O(N^2). Assuming we use double-ended queue to implement the shift which is O(1) constant time.

1
2
3
4
5
6
7
8
9

class Solution:    
    def minimumRightShifts(self, nums: List[int]) -> int:
        q = deque(nums)
        n = len(nums)
        i = 0
        while (not is_sorted(list(q))) and i < n:
            i += 1
            q.appendleft(q.pop())
        return i if i < n else -1

class Solution:    
    def minimumRightShifts(self, nums: List[int]) -> int:
        q = deque(nums)
        n = len(nums)
        i = 0
        while (not is_sorted(list(q))) and i < n:
            i += 1
            q.appendleft(q.pop())
        return i if i < n else -1

We can find the index of the minimum number, and then move the numbers from it to the end, then check if the array is sorted. This is going to take O(N) time. When the array is sorted, we should return 0, as no shifts is needed.

1
2
3
4
5
6
7
8
9

class Solution:    
    def minimumRightShifts(self, nums: List[int]) -> int:
        n = len(nums)
        a = min(nums)
        i = nums.index(a)
        new_arr = nums[i:] + nums[:i]
        if not is_sorted(new_array):
            return -1 
        return (n - i) % n

class Solution:    
    def minimumRightShifts(self, nums: List[int]) -> int:
        n = len(nums)
        a = min(nums)
        i = nums.index(a)
        new_arr = nums[i:] + nums[:i]
        if not is_sorted(new_array):
            return -1 
        return (n - i) % n

–EOF (The Ultimate Computing & Technology Blog) —