Semi-Ordered Permutation

Difficulty: Easy | Acceptance: 64.20% | Paid: No Topics: Array, Simulation

You are given a permutation of the integers from 1 to n. A permutation is called semi-ordered if the first element is 1 and the last element is n.

You can perform the following operation any number of times:

Choose two adjacent elements and swap them.

Return the minimum number of operations needed to make the permutation semi-ordered.

Examples

Input: nums = [2,1,4,3]
Output: 2
Explanation: We can swap 2 and 1, then swap 4 and 3.

Input: nums = [2,1,3]
Output: 2
Explanation: We can swap 2 and 1, then swap 3 and 1.

Input: nums = [1,3,2]
Output: 1
Explanation: We can swap 3 and 2.

Constraints

2 <= nums.length <= 50
nums is a permutation of integers from 1 to nums.length.

• Direct Position Calculation
• Simulation

Direct Position Calculation

Intuition The minimum swaps to move 1 to index 0 equals its current position, and moving n to index n-1 requires (n-1 - position of n) swaps. If 1 is to the right of n, moving 1 left shifts n right by one, requiring one less swap.

Steps

• Find the index of 1 (pos1) and index of n (posN)
• Calculate swaps as pos1 + (n-1 - posN)
• If pos1 > posN, subtract 1 from total (since moving 1 past n shifts n right)

class Solution:
    def semiOrderedPermutation(self, nums: List[int]) -> int:
        n = len(nums)
        pos1 = nums.index(1)
        posN = nums.index(n)
        ans = pos1 + (n - 1 - posN)
        if pos1 > posN:
            ans -= 1
        return ans

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Optimal solution with single pass to find positions

Simulation

Intuition Simulate the actual swapping process: repeatedly swap 1 with its left neighbor until it reaches index 0, then swap n with its right neighbor until it reaches index n-1, counting each swap.

Steps

• Make a copy of the array to avoid modifying input
• While 1 is not at index 0, find its position and swap with left neighbor, increment count
• While n is not at last index, find its position and swap with right neighbor, increment count
• Return total swap count

class Solution:
    def semiOrderedPermutation(self, nums: List[int]) -> int:
        n = len(nums)
        arr = nums.copy()
        swaps = 0
        
        while arr[0] != 1:
            pos1 = arr.index(1)
            arr[pos1], arr[pos1 - 1] = arr[pos1 - 1], arr[pos1]
            swaps += 1
        
        while arr[-1] != n:
            posN = arr.index(n)
            arr[posN], arr[posN + 1] = arr[posN + 1], arr[posN]
            swaps += 1
        
        return swaps

Complexity

• Time: O(n²)
• Space: O(n)
• Notes: More intuitive but less efficient due to repeated index searches and array copies