October 22Medium

Minimum operations to sort a permutation

Array

Problem

You are given an integer array nums of length n, where nums is a permutation of the integers from 0 to n - 1.

You may perform only the following operations: - Reverse the entire array. - Rotate Left by One: Move the first element to the end of the array, and rest elements to left by one position.

Return an integer denoting the minimum number of operations required to sort the array in increasing order. If it is not possible to sort the array using only the given operations, return -1.

Solution

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        normal = 0 if nums[0] <= nums[-1] else None
        reverse = 0 if nums[0] >= nums[-1] else None
        for i in range(1, len(nums)):
            if nums[i] < nums[i-1]:
                if normal is None:
                    normal = i
                else:
                    normal = False
            elif nums[i] > nums[i-1]:
                if reverse is None:
                    reverse = i
                else:
                    reverse = False

        if normal is False and reverse is False:
            return -1
        if normal is not False:
            return min(normal, 2 + len(nums) - normal)
        return 1+min(reverse, len(nums) - reverse)