Semi-Ordered Permutation - 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 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.
Input & Output
Example 1 — Basic Case
$
Input:
nums = [2,1,4,3]
›
Output:
1
💡 Note:
We need 1 to be at position 0 and 4 to be at position 3. Currently 1 is at position 1, so we need 1 swap to move it left. 4 is already at position 3, so no swaps needed for 4. Total: 1 operation.
Example 2 — Multiple Swaps
$
Input:
nums = [2,4,1,3]
›
Output:
3
💡 Note:
1 is at position 2, needs 2 swaps to reach position 0. 4 is at position 1, needs 2 swaps to reach position 3. But since 1 is to the right of 4, we can optimize by 1 swap. Total: 2 + 2 - 1 = 3 operations.
Example 3 — Already Semi-ordered
$
Input:
nums = [1,3,2,4]
›
Output:
0
💡 Note:
1 is already at position 0 and 4 is already at position 3. The array is already semi-ordered, so 0 operations needed.
Constraints
- 2 ≤ nums.length ≤ 50
- 1 ≤ nums[i] ≤ nums.length
- nums is a permutation of integers from 1 to n
Visualization
Tap to expand
Understanding the Visualization
1
Input
Permutation array where 1 and n may not be in correct positions
2
Process
Calculate minimum adjacent swaps to move 1 to front and n to back
3
Output
Return the minimum number of operations needed
Key Takeaway
🎯 Key Insight: Calculate swaps mathematically: find positions, apply formula, handle overlap when 1 is after n
💡
Explanation
AI Ready
💡 Suggestion
Tab
to accept
Esc
to dismiss
// Output will appear here after running code