LeetCode 2717. Semi-Ordered Permutation Solution in Java, C++, Python & More | Explanation + Code

Description

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 make nums a semi-ordered 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 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:

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:

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.

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

PythonJavaC++GoTypeScriptRust

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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

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; }(code-box)

impl Solution { pub fn semi_ordered_permutation(nums: Vec<i32>) -> i32 { let n = nums.len(); let (mut i, mut j) = (0, 0); for k in 0..n { if nums[k] == 1 { i = k; } if nums[k] == (n as i32) { j = k; } } let k = if i < j { 1 } else { 2 }; (i + n - j - k) as i32 } }(code-box)