3942. Minimum Operations to Sort a Permutation

1. Description

The array nums contains each integer from 0 through n - 1 exactly once, where n is its length.
In each operation, either reverse nums completely or shift it left by one position, moving its first element to the end. Each reversal or single-position shift counts as one operation.
Return the fewest operations needed to arrange nums in increasing order, or -1 if these operations cannot sort it.

2. Example

Example 1

Input: nums = [0,2,1]
Output: 2
Explanation: A left shift produces [2,1,0], and reversing it produces [0,1,2]. Two operations are necessary and sufficient.

Example 2

Input: nums = [1,0,2]
Output: 2
Explanation: Reversing produces [2,0,1], then a left shift produces [0,1,2]. The minimum is two operations.

Example 3

Input: nums = [2,0,1,3]
Output: -1
Explanation: No combination of full reversals and left shifts can transform this permutation into [0,1,2,3].

3. Constraints

• 1 <= n == nums.length <= 10$^5$
• 0 <= nums[i] <= n - 1
• nums contains every integer from 0 through n - 1 exactly once.

4. Solutions

Case Analysis

n = nums.size()
Time complexity: O(n)
Space complexity: 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
28
29
30

class Solution {
public:
    int minOperations(const vector<int> &nums) {
        const int n = nums.size();
        if (n == 1) {
            return 0;
        }

        int increase_count = nums.back() < nums.front();
        int zero_index = 0;

        for (int i = 1; i < n; ++i) {
            increase_count += nums[i - 1] < nums[i];

            if (nums[i] == 0) {
                zero_index = i;
            }
        }

        if (increase_count == n - 1) {
            return min(zero_index, n - zero_index + 2);
        }

        if (increase_count == 1) {
            return min(n - zero_index, zero_index + 2);
        }

        return -1;
    }
};