Skip to content

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

Thinking

The allowed operations are combinations of rotate and reverse, not arbitrary permutations. If the array can be sorted, the cyclic order starting at \(0\) must be increasing in one direction or the other.

Locate \(0\) at \(\textit{zero}\) and test step \(+1\) and step \(-1\). For each valid direction the rotate count and the “reverse–rotate–reverse” count follow from \(\textit{zero}\) and \(n\); take the minimum, or report impossible if neither direction is sorted.

The check is \(O(n)\) and never simulates the operations step by step.

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)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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;
}

Comments