Jobs

Interviews

Discussions

Minimum Right Shifts to Sort the Array

Easy

Asked by:

17 views

Topics:

Arrays

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.

Try coding it in LeetCode

Minimum Right Shifts to Sort the Array

Easy

Asked by:

17 views

Topics:

Arrays

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the input array, and can the array contain negative numbers or duplicates?
If the array is already sorted, should I return 0, or is there a different expected output?
If the array cannot be sorted by any number of right shifts, what should I return?
What is the maximum size of the input array?
By 'sorted,' do you mean ascending order, or is there any flexibility in the sorting criteria?

Brute Force Solution

Approach

The brute force method for sorting an array with right shifts is like trying out every possible number of shifts. We'll check if the array is sorted after each different number of shifts.

Here's how the algorithm would work step-by-step:

First, we start by shifting the array zero times and check if it's sorted.
Next, we shift the array one position to the right and check if it's sorted.
Then, we shift the array two positions to the right and check if it's sorted.
We keep repeating this process, shifting the array three times, four times, and so on, until we've shifted it as many times as there are items in the array.
Each time we shift, we carefully check if the resulting arrangement is in sorted order.
If at any point the shifted arrangement is sorted, we remember how many shifts it took.
Finally, we choose the smallest number of shifts it took to make the array sorted. If none of the shifts resulted in a sorted array, it is impossible to sort it with right shifts.

Code Implementation

def minimum_right_shifts_to_sort(numbers):
    list_length = len(numbers)

    for shift_count in range(list_length):
        # Create shifted list
        shifted_list = numbers[-shift_count:] + numbers[:-shift_count]

        # Check if the shifted list is sorted
        is_sorted = True
        for index in range(list_length - 1):
            if shifted_list[index] > shifted_list[index + 1]:
                is_sorted = False
                break

        # If sorted, return shift count
        if is_sorted:
            return shift_count

    # Return -1 if cannot be sorted
    return -1

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each possible right shift, from 0 to n-1, where n is the number of elements in the array. For each shift, it checks if the resulting array is sorted. The sorting check itself requires iterating through the array once, taking O(n) time. Since we perform this sorting check for each of the n possible shifts, the total time complexity becomes O(n * n), which simplifies to O(n²).

Space Complexity

O(1) – The brute force method described checks for sorted order after each right shift. It shifts the array in place. While checking for sorted order, the algorithm only requires a few constant space variables (e.g., loop counters, variables to check if the array is sorted). Therefore, the space used does not scale with the input size N, making the auxiliary space complexity O(1).

Optimal Solution

Approach

The goal is to find the fewest moves to put an out-of-order sequence into the correct order by shifting items from the end to the beginning. Instead of checking every possible number of moves, we look for how much of the sequence is already in order to figure out the solution faster.

Here's how the algorithm would work step-by-step:

First, check how much of the sequence is already in order from the start to the end. We're looking for the longest continuous stretch of items that are in their correct positions relative to each other.
If the whole sequence is already in order, then no moves are needed.
If there's a part that's already in order, then the number of moves needed is simply the total number of items in the sequence minus the length of that already-in-order part.
Essentially, we're figuring out how many items need to be moved from the end to the front to put the entire sequence in the correct order. That number is the answer.

Code Implementation

def min_right_shifts_to_sort(arr):
    array_length = len(arr)
    longest_increasing_suffix_length = 0

    # Find the longest sorted suffix
    for i in range(array_length - 1):
        if arr[i] > arr[i + 1]:
            
            #The array isn't sorted. Find the longest suffix
            for start_index in range(array_length - 1, -1, -1):
                is_sorted = True
                for j in range(start_index, array_length - 1):
                    if arr[j] > arr[j + 1]:
                        is_sorted = False
                        break

                if is_sorted:
                    longest_increasing_suffix_length = array_length - start_index
                    break
            break
    else:
        # Array is already sorted
        return 0

    # Calculate min shifts based on unsorted part
    minimum_shifts = array_length - longest_increasing_suffix_length
    return minimum_shifts

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n once to find the longest sorted subsequence. In each iteration, it performs a constant number of comparisons. Therefore, the time complexity is directly proportional to the input size, resulting in O(n).

Space Complexity

O(1) – The algorithm checks for the longest continuously sorted portion of the input array without creating any auxiliary data structures. It operates directly on the input and uses only a fixed number of variables for indexing and comparison. Therefore, the space required does not depend on the input size, N, and remains constant. The auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty array input	Return 0, as an empty array is considered sorted by default.
Array with only one element	Return 0, as a single-element array is already sorted.
Already sorted array	Return 0, as no shifts are required.
Array sorted in descending order	Iterate through all possible shifts and check for sorted state; if none found, return -1.
Array with all identical elements	Return 0, as identical elements are considered sorted.
Large array exceeding memory constraints	Consider an in-place approach, if possible, to avoid excessive memory usage and potential OutOfMemoryError.
Array where no number of shifts can result in a sorted array	Return -1 when the loop completes without finding a valid sorted array.
Integer overflow when calculating array indices after shifts	Use modulo operator (%) carefully to wrap around correctly and avoid exceeding the array bounds.

Null or empty array input

How to Handle:

Return 0, as an empty array is considered sorted by default.

Array with only one element

How to Handle:

Return 0, as a single-element array is already sorted.

Already sorted array

How to Handle:

Return 0, as no shifts are required.

Array sorted in descending order

How to Handle:

Iterate through all possible shifts and check for sorted state; if none found, return -1.

Array with all identical elements

How to Handle:

Return 0, as identical elements are considered sorted.

Large array exceeding memory constraints

How to Handle:

Consider an in-place approach, if possible, to avoid excessive memory usage and potential OutOfMemoryError.

Array where no number of shifts can result in a sorted array

How to Handle:

Return -1 when the loop completes without finding a valid sorted array.

Integer overflow when calculating array indices after shifts

How to Handle:

Use modulo operator (%) carefully to wrap around correctly and avoid exceeding the array bounds.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the input array, and can the array contain negative numbers or duplicates?
If the array is already sorted, should I return 0, or is there a different expected output?
If the array cannot be sorted by any number of right shifts, what should I return?
What is the maximum size of the input array?
By 'sorted,' do you mean ascending order, or is there any flexibility in the sorting criteria?

Brute Force Solution

Approach

The brute force method for sorting an array with right shifts is like trying out every possible number of shifts. We'll check if the array is sorted after each different number of shifts.

Here's how the algorithm would work step-by-step:

First, we start by shifting the array zero times and check if it's sorted.
Next, we shift the array one position to the right and check if it's sorted.
Then, we shift the array two positions to the right and check if it's sorted.
We keep repeating this process, shifting the array three times, four times, and so on, until we've shifted it as many times as there are items in the array.
Each time we shift, we carefully check if the resulting arrangement is in sorted order.
If at any point the shifted arrangement is sorted, we remember how many shifts it took.
Finally, we choose the smallest number of shifts it took to make the array sorted. If none of the shifts resulted in a sorted array, it is impossible to sort it with right shifts.

Code Implementation

def minimum_right_shifts_to_sort(numbers):
    list_length = len(numbers)

    for shift_count in range(list_length):
        # Create shifted list
        shifted_list = numbers[-shift_count:] + numbers[:-shift_count]

        # Check if the shifted list is sorted
        is_sorted = True
        for index in range(list_length - 1):
            if shifted_list[index] > shifted_list[index + 1]:
                is_sorted = False
                break

        # If sorted, return shift count
        if is_sorted:
            return shift_count

    # Return -1 if cannot be sorted
    return -1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, check how much of the sequence is already in order from the start to the end. We're looking for the longest continuous stretch of items that are in their correct positions relative to each other.
If the whole sequence is already in order, then no moves are needed.
If there's a part that's already in order, then the number of moves needed is simply the total number of items in the sequence minus the length of that already-in-order part.
Essentially, we're figuring out how many items need to be moved from the end to the front to put the entire sequence in the correct order. That number is the answer.

Code Implementation

def min_right_shifts_to_sort(arr):
    array_length = len(arr)
    longest_increasing_suffix_length = 0

    # Find the longest sorted suffix
    for i in range(array_length - 1):
        if arr[i] > arr[i + 1]:
            
            #The array isn't sorted. Find the longest suffix
            for start_index in range(array_length - 1, -1, -1):
                is_sorted = True
                for j in range(start_index, array_length - 1):
                    if arr[j] > arr[j + 1]:
                        is_sorted = False
                        break

                if is_sorted:
                    longest_increasing_suffix_length = array_length - start_index
                    break
            break
    else:
        # Array is already sorted
        return 0

    # Calculate min shifts based on unsorted part
    minimum_shifts = array_length - longest_increasing_suffix_length
    return minimum_shifts

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty array input	Return 0, as an empty array is considered sorted by default.
Array with only one element	Return 0, as a single-element array is already sorted.
Already sorted array	Return 0, as no shifts are required.
Array sorted in descending order	Iterate through all possible shifts and check for sorted state; if none found, return -1.
Array with all identical elements	Return 0, as identical elements are considered sorted.
Large array exceeding memory constraints	Consider an in-place approach, if possible, to avoid excessive memory usage and potential OutOfMemoryError.
Array where no number of shifts can result in a sorted array	Return -1 when the loop completes without finding a valid sorted array.
Integer overflow when calculating array indices after shifts	Use modulo operator (%) carefully to wrap around correctly and avoid exceeding the array bounds.

Null or empty array input

How to Handle:

Return 0, as an empty array is considered sorted by default.

Array with only one element

How to Handle:

Return 0, as a single-element array is already sorted.

Already sorted array

How to Handle:

Return 0, as no shifts are required.

Array sorted in descending order

How to Handle:

Iterate through all possible shifts and check for sorted state; if none found, return -1.

Array with all identical elements

How to Handle:

Return 0, as identical elements are considered sorted.

Large array exceeding memory constraints

How to Handle:

Consider an in-place approach, if possible, to avoid excessive memory usage and potential OutOfMemoryError.

Array where no number of shifts can result in a sorted array

How to Handle:

Return -1 when the loop completes without finding a valid sorted array.

Integer overflow when calculating array indices after shifts

How to Handle:

Use modulo operator (%) carefully to wrap around correctly and avoid exceeding the array bounds.