Problem

You are given a 0-indexed permutation of n integers nums.

A permutation is called semi-ordered if the first number equals 1 and the last number equals n. You can perform the below operation as many times as you want until you make nums a semi-ordered permutation:

  • Pick two adjacent elements in nums, then swap them.

Return the minimum number of operations to makenums asemi-ordered permutation.

A permutation is a sequence of integers from 1 to n of length n containing each number exactly once.

Examples

Example 1

1
2
3
4
5
6

Input: nums = [2,1,4,3]
Output: 2
Explanation: We can make the permutation semi-ordered using these sequence of operations: 
1 - swap i = 0 and j = 1. The permutation becomes [1,2,4,3].
2 - swap i = 2 and j = 3. The permutation becomes [1,2,3,4].
It can be proved that there is no sequence of less than two operations that make nums a semi-ordered permutation.

Example 2

1
2
3
4
5
6
7

Input: nums = [2,4,1,3]
Output: 3
Explanation: We can make the permutation semi-ordered using these sequence of operations:
1 - swap i = 1 and j = 2. The permutation becomes [2,1,4,3].
2 - swap i = 0 and j = 1. The permutation becomes [1,2,4,3].
3 - swap i = 2 and j = 3. The permutation becomes [1,2,3,4].
It can be proved that there is no sequence of less than three operations that make nums a semi-ordered permutation.

Example 3

1
2
3

Input: nums = [1,3,4,2,5]
Output: 0
Explanation: The permutation is already a semi-ordered permutation.

Constraints

  • 2 <= nums.length == n <= 50
  • 1 <= nums[i] <= 50
  • nums is a permutation.

Solution

Method 1 – Greedy Index Calculation

Intuition

To make the permutation semi-ordered, move 1 to the front and n to the end using adjacent swaps. If 1 is before n, their moves don’t interfere. If 1 is after n, moving 1 to the front shifts n right by 1, so we need one less move for n.

Approach

  1. Find the index of 1 (i1) and n (in_) in nums.
  2. If i1 < in_, answer is i1 + (n - 1 - in_).
  3. If i1 > in_, answer is i1 + (n - 1 - in_) - 1.
  4. Return the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int semiOrderedPermutation(vector<int>& nums) {
        int n = nums.size(), i1 = 0, in_ = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 1) i1 = i;
            if (nums[i] == n) in_ = i;
        }
        if (i1 < in_) return i1 + (n - 1 - in_);
        return i1 + (n - 1 - in_) - 1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func semiOrderedPermutation(nums []int) int {
    n := len(nums)
    i1, in_ := 0, 0
    for i, v := range nums {
        if v == 1 { i1 = i }
        if v == n { in_ = i }
    }
    if i1 < in_ {
        return i1 + (n - 1 - in_)
    }
    return i1 + (n - 1 - in_) - 1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int semiOrderedPermutation(int[] nums) {
        int n = nums.length, i1 = 0, in_ = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 1) i1 = i;
            if (nums[i] == n) in_ = i;
        }
        if (i1 < in_) return i1 + (n - 1 - in_);
        return i1 + (n - 1 - in_) - 1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun semiOrderedPermutation(nums: IntArray): Int {
        val n = nums.size
        var i1 = 0
        var in_ = 0
        for (i in nums.indices) {
            if (nums[i] == 1) i1 = i
            if (nums[i] == n) in_ = i
        }
        return if (i1 < in_) i1 + (n - 1 - in_) else i1 + (n - 1 - in_) - 1
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def semiOrderedPermutation(self, nums: list[int]) -> int:
        n = len(nums)
        i1 = nums.index(1)
        in_ = nums.index(n)
        if i1 < in_:
            return i1 + (n - 1 - in_)
        return i1 + (n - 1 - in_) - 1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn semi_ordered_permutation(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let i1 = nums.iter().position(|&x| x == 1).unwrap();
        let in_ = nums.iter().position(|&x| x == n as i32).unwrap();
        if i1 < in_ {
            (i1 + (n - 1 - in_)) as i32
        } else {
            (i1 + (n - 1 - in_) - 1) as i32
        }
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    semiOrderedPermutation(nums: number[]): number {
        const n = nums.length;
        const i1 = nums.indexOf(1);
        const in_ = nums.indexOf(n);
        if (i1 < in_) return i1 + (n - 1 - in_);
        return i1 + (n - 1 - in_) - 1;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n = length of nums. We scan the array once.
  • 🧺 Space complexity: O(1), only a few variables are used.