Welcome to Subscribe On Youtube
2717. SemiOrdered Permutation
Description
You are given a 0indexed permutation of n
integers nums
.
A permutation is called semiordered 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 semiordered permutation:
 Pick two adjacent elements in
nums
, then swap them.
Return the minimum number of operations to make nums
a semiordered permutation.
A permutation is a sequence of integers from 1
to n
of length n
containing each number exactly once.
Example 1:
Input: nums = [2,1,4,3] Output: 2 Explanation: We can make the permutation semiordered 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 semiordered permutation.
Example 2:
Input: nums = [2,4,1,3] Output: 3 Explanation: We can make the permutation semiordered 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 semiordered permutation.
Example 3:
Input: nums = [1,3,4,2,5] Output: 0 Explanation: The permutation is already a semiordered permutation.
Constraints:
2 <= nums.length == n <= 50
1 <= nums[i] <= 50
nums is a permutation.
Solutions
Solution 1: Find the Positions of 1 and n
We can first find the indices $i$ and $j$ of $1$ and $n$, respectively. Then, based on the relative positions of $i$ and $j$, we can determine the number of swaps required.
If $i < j$, the number of swaps required is $i + n  j  1$. If $i > j$, the number of swaps required is $i + n  j  2$.
The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.

class Solution { public int semiOrderedPermutation(int[] nums) { int n = nums.length; int i = 0, j = 0; for (int k = 0; k < n; ++k) { if (nums[k] == 1) { i = k; } if (nums[k] == n) { j = k; } } int k = i < j ? 1 : 2; return i + n  j  k; } }

class Solution { public: int semiOrderedPermutation(vector<int>& nums) { int n = nums.size(); int i = find(nums.begin(), nums.end(), 1)  nums.begin(); int j = find(nums.begin(), nums.end(), n)  nums.begin(); int k = i < j ? 1 : 2; return i + n  j  k; } };

class Solution: def semiOrderedPermutation(self, nums: List[int]) > int: n = len(nums) i = nums.index(1) j = nums.index(n) k = 1 if i < j else 2 return i + n  j  k

func semiOrderedPermutation(nums []int) int { n := len(nums) var i, j int for k, x := range nums { if x == 1 { i = k } if x == n { j = k } } k := 1 if i > j { k = 2 } return i + n  j  k }

function semiOrderedPermutation(nums: number[]): number { const n = nums.length; const i = nums.indexOf(1); const j = nums.indexOf(n); const k = i < j ? 1 : 2; return i + n  j  k; }

impl Solution { pub fn semi_ordered_permutation(nums: Vec<i32>) > i32 { let mut i = 0; let mut j = 0; let mut n = nums.len(); for idx in 0..n { if nums[idx] == 1 { i = idx; } if nums[idx] == (n as i32) { j = idx; } } let mut ans = i  1 + n  j; if i > j { ans = i  1 + n  j  1; } ans as i32 } }