algoadvance

Leetcode 2855. Minimum Right Shifts to Sort the Array

Problem Statement

You are given a 0-indexed array nums of length n. The array might be rotated to the right by any number of positions. The task is to find the minimum number of right shifts required to sort the array. A right shift consists of removing the last element of the array and adding it to the beginning.

If the array cannot be sorted using any number of right shifts, return -1.

Example

Input: nums = [3, 4, 5, 1, 2]
Output: 3
Explanation: After shifting right three times, nums becomes [1, 2, 3, 4, 5].

Clarifying Questions

  1. Can the array contain duplicate elements?
    • Yes. The problem does not specify that all elements are unique.
  2. What are the constraints on the length of the array n?
    • Constraints are typically provided in the problem statement, but we can assume typical LeetCode constraints (e.g., up to 10^4 elements).
  3. What is the range of element values in nums?
    • The elements in the array can be any integer values.

Strategy

  1. Identify Rotation Points:
    • Identify if there is exactly one point in the array after which the array is sorted in increasing order, and the first part up to this point is also sorted. This point gives us the required number of shifts.
  2. Check for Sorted Subarray Sequences:
    • Iterate through the array to find where the sorted sequence breaks from the end. Use this breaking point to calculate the number of shifts.
  3. Validation:
    • After determining the potential number of shifts, validate by performing the right shifts and checking if the resultant array is sorted.

Code Implementation

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minimumRightShifts(vector<int>& nums) {
        int n = nums.size();
        
        // Check if the array is already sorted.
        if (is_sorted(nums.begin(), nums.end())) return 0;

        // Identify the point of rotation.
        for (int i = 0; i < n; ++i) {
            vector<int> shifted = nums;
            // Perform the right shift operation.
            rotate(shifted.rbegin(), shifted.rbegin() + i, shifted.rend());
            
            // Check if the resultant array is sorted.
            if (is_sorted(shifted.begin(), shifted.end())) {
                return i;
            }
        }
        
        // If no valid right shift rotation sorts the array, return -1.
        return -1;
    }
};

int main() {
    Solution sol;
    vector<int> nums = {3, 4, 5, 1, 2};
    
    int result = sol.minimumRightShifts(nums);
    // Expected output: 3
    return 0;
}

Time Complexity

Given the rotate and is_sorted operations, and iterating for potentially all n indices:

Conclusion

The solution involves checking each possible right shift to determine if it results in a sorted array. It ensures an optimal and simple approach to identifying the necessary rotations.

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