README_EN.md

comments	true
difficulty	Medium
edit_url	https://github.com/doocs/leetcode/edit/main/solution/3900-3999/3942.Minimum%20Operations%20to%20Sort%20a%20Permutation/README_EN.md
rating	1854
source	Weekly Contest 503 Q3

3942. Minimum Operations to Sort a Permutation

中文文档

Description

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.

 

Example 1:

Input: nums = [0,2,1]

Output: 2

Explanation:

• Rotate Left by one: [2, 1, 0]
• Reverse the array: [0, 1, 2]

The array becomes sorted in 2 operations, which is minimal

Example 2:

Input: nums = [1,0,2]

Output: 2

Explanation:

• Reverse the array: [2, 0, 1]
• Rotate Left by one: [0, 1, 2]

The array becomes sorted in 2 operations, which is minimal.

Example 3:

Input: nums = [2,0,1,3]

Output: -1

Explanation:

It is impossible to reach [2, 0, 1, 3]. Thus, the answer is -1.

 

Constraints:

• 1 <= n == nums.length <= 105
• 0 <= nums[i] <= n - 1
• nums is a permutation of integers from 0 to n - 1.

Solutions

Solution 1: Case Analysis

We first find the position of 0 in the array, denoted as $\textit{zero}$.

Next, we check whether the sequence is increasing when traversing right from 0, and whether it is increasing when traversing left from 0.

If it is increasing to the right from 0, we can sort the array in either of the following two ways:

• Rotate directly: left-rotate the array by $\textit{zero}$ positions.
• Reverse, rotate, then reverse back: reverse the array, left-rotate it by $n - \textit{zero}$ positions, then reverse it again.

If it is increasing to the left from 0, we can sort the array in either of the following two ways:

• Rotate, then reverse: left-rotate the array by $\textit{zero} + 1$ positions to move 0 to the end, then reverse the array.
• Reverse, then rotate: reverse the array, then left-rotate it by $n - \textit{zero} - 1$ positions to move 0 to the beginning.

We compute the number of operations for all four methods above and return the minimum. If sorting is impossible, return -1.

The time complexity is $O(n)$, where $n$ is the length of $\textit{nums}$. The space complexity is $O(1)$.

Python3

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        n = len(nums)

        zero = nums.index(0)

        def check(step: int) -> bool:
            for i in range(1, n):
                prev = (zero + (i - 1) * step) % n
                curr = (zero + i * step) % n

                if nums[prev] > nums[curr]:
                    return False

            return True

        ans = inf

        if check(1):
            ans = min(ans, zero)
            ans = min(ans, n - zero + 2)

        if check(-1):
            ans = min(ans, zero + 2)
            ans = min(ans, n - zero)

        return -1 if ans == inf else ans

Java

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

        int zero = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                zero = i;
                break;
            }
        }

        int finalZero = zero;

        IntPredicate check = step -> {
            for (int i = 1; i < n; i++) {
                int prev = (finalZero + (i - 1) * step + n) % n;
                int curr = (finalZero + i * step + n) % n;

                if (nums[prev] > nums[curr]) {
                    return false;
                }
            }

            return true;
        };

        int ans = Integer.MAX_VALUE;

        if (check.test(1)) {
            ans = Math.min(ans, zero);
            ans = Math.min(ans, n - zero + 2);
        }

        if (check.test(-1)) {
            ans = Math.min(ans, zero + 2);
            ans = Math.min(ans, n - zero);
        }

        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

C++

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int n = nums.size();

        int zero = ranges::find(nums, 0) - nums.begin();

        auto check = [&](int step) -> bool {
            for (int i = 1; i < n; i++) {
                int prev = (zero + (i - 1) * step + n) % n;
                int curr = (zero + i * step + n) % n;

                if (nums[prev] > nums[curr]) {
                    return false;
                }
            }
            return true;
        };

        int ans = INT_MAX;

        if (check(1)) {
            ans = min(ans, zero);
            ans = min(ans, n - zero + 2);
        }

        if (check(-1)) {
            ans = min(ans, zero + 2);
            ans = min(ans, n - zero);
        }

        return ans == INT_MAX ? -1 : ans;
    }
};

Go

func minOperations(nums []int) int {
	n := len(nums)

	zero := 0
	for i, x := range nums {
		if x == 0 {
			zero = i
			break
		}
	}

	check := func(step int) bool {
		for i := 1; i < n; i++ {
			prev := (zero + (i-1)*step + n) % n
			curr := (zero + i*step + n) % n

			if nums[prev] > nums[curr] {
				return false
			}
		}

		return true
	}

	ans := math.MaxInt

	if check(1) {
		ans = min(ans, zero)
		ans = min(ans, n-zero+2)
	}

	if check(-1) {
		ans = min(ans, zero+2)
		ans = min(ans, n-zero)
	}

	if ans == math.MaxInt {
		return -1
	}

	return ans
}

TypeScript

function minOperations(nums: number[]): number {
    const n = nums.length;

    const zero = nums.indexOf(0);

    const check = (step: number): boolean => {
        for (let i = 1; i < n; i++) {
            const prev = (zero + (i - 1) * step + n) % n;
            const curr = (zero + i * step + n) % n;

            if (nums[prev] > nums[curr]) {
                return false;
            }
        }

        return true;
    };

    let ans = Number.MAX_SAFE_INTEGER;

    if (check(1)) {
        ans = Math.min(ans, zero);
        ans = Math.min(ans, n - zero + 2);
    }

    if (check(-1)) {
        ans = Math.min(ans, zero + 2);
        ans = Math.min(ans, n - zero);
    }

    return ans === Number.MAX_SAFE_INTEGER ? -1 : ans;
}