algoadvance

Leetcode 2855. Minimum Right Shifts to Sort the Array

Problem Statement

You are given an array nums of n unique integers. You can perform the following operation on the array any number of times:

• Rotate the array to the right by one position.

Return the minimum number of right shifts needed to sort the array in non-decreasing order. If it’s not possible to sort the array using the above operation, return -1.

Clarifying Questions

1. Q: Will the array always have unique integers? A: Yes, the problem states that the integers in the array are unique.

2. Q: What is the definition of a right shift? A: A right shift means taking the last element of the array and moving it to the first position (like rotating the array).

3. Q: Should the array be sorted in strictly increasing order? A: No, it should be sorted in non-decreasing order which allows for repeated elements. However, since the array has unique integers, strictly increasing order is implicated.

4. Q: Can we assume that the input array will be valid with length n ≥ 0? A: Yes, valid array lengths ranging from 0 to n.

Strategy

To determine the minimum number of right shifts to sort the array, or whether it’s impossible, follow these steps:

1. Identify the pivot: An array can be sorted by right shifts if there’s exactly one place (pivot) where the array transitions from the largest element to the smallest. For instance, in [4, 5, 1, 2, 3], the pivot is at 2, where 5 is followed by 1.

2. Validation: After identifying the pivot index, determine if the array rotated to start from the pivot would be sorted in non-decreasing order.

3. Count shifts: The necessary shifts to rotate the array starting from the pivot to the end of the array is equal to the length of the array minus the pivot index.

4. Edge Cases: Consider cases where the array is already sorted or cases where no such pivot exists, meaning it is impossible to sort with rotations.

Code

public class Solution {
    public int minimumRightShifts(int[] nums) {
        int n = nums.length;

        // Check if the array is already sorted
        boolean isSorted = true;
        for (int i = 1; i < n; i++) {
            if (nums[i] < nums[i - 1]) {
                isSorted = false;
                break;
            }
        }
        if (isSorted) return 0;

        // Identify pivot
        int pivot = -1;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                if (pivot != -1) {
                    return -1; // More than one pivot means it's unsortable by rotations
                }
                pivot = i;
            }
        }

        // No pivot found means array is strictly increasing or completely unsortable
        if (pivot == -1) return -1;

        // Validate if the array can be sorted by rotating from the found pivot
        for (int i = pivot + 1; i < n - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                return -1;
            }
        }
        if (nums[n - 1] > nums[0]) {
            return -1;
        }

        // Return the number of right shifts needed
        return n - 1 - pivot;
    }
}

Time Complexity

• Time Complexity: O(n), where n is the number of elements in the array. We traverse the array a few times to both identify potential pivot points and validate the sorted order.
• Space Complexity: O(1), as no extra space proportional to the input size is used.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?