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
Semi-Ordered Permutation: Move 1 to Front, n to BackINPUT2413nums = [2, 4, 1, 3]1 moves to front4 moves to backOUTPUT1234result = [1, 2, 3, 4] (semi-ordered)Minimum operations: 3Formula: pos_1 + (n-1-pos_n) - (overlap ? 1 : 0)
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
Asked in
Google 12 Meta 8 Amazon 6
31.5K Views
Medium Frequency
~15 min Avg. Time
850 Likes
Ln 1, Col 1
Smart Actions
💡 Explanation
AI Ready
💡 Suggestion Tab to accept Esc to dismiss
// Output will appear here after running code
Code Editor Closed
Click the red button to reopen