Semi-Ordered Permutation

In this problem, we are given an array of numbers, which is a permutation of the integers from 1 to ’n’. Our task is to make this permutation “semi-ordered” by moving the number 1 to the start and the number ’n’ to the end using the least number of swaps of adjacent elements.

Here’s an explanation of the steps:

1. Find the position of the number 1 in the array. Let’s say this position is ‘i’. It will take ‘i’ swaps to move 1 to the start of the array because in each swap, we can move 1 one position closer to the start.

2. Similarly, find the position of the number ’n’. If this position is ‘j’, we need ’n - j - 1’ swaps to move ’n’ to the end of the array. We subtract ‘j’ from ’n’ to calculate the number of steps from the end, and we subtract 1 because the array is 0-indexed.

3. Add the numbers of swaps calculated in steps 1 and 2. This will be the minimum number of operations needed to make the permutation semi-ordered, in most cases.

4. There’s one special case we need to consider: when the position of 1 is further along in the array than the position of ’n’. In this scenario, when we’re moving 1 towards the start and ’n’ towards the end, there will be a point where 1 and ’n’ are next to each other and we can swap them in one operation, rather than two. So, if the position of 1 is greater than the position of ’n’, we subtract 1 from our answer to account for this simultaneous swap.

That’s it. The answer is the minimum number of operations required to make the given permutation semi-ordered.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

from typing import List

class Solution:
    def semiOrderedPermutation(self, nums: List[int]) -> int:
        imin = 0
        imax = len(nums)
        n = len(nums)

        for i in range(n):
            if nums[i] == 1:
                imin = i
            if nums[i] == n:
                imax = i

        if imin < imax:
            return (imin + n - imax - 1)
        return (imin + n - imax - 1) - 1

We maintain two variables, imin and imax, to keep track of the indices of 1 and n in nums. We iterate over nums and update imin and imax whenever we find 1 and n respectively. If imin is less than imax, we return (imin + n - imax - 1). Otherwise, we return (imin + n - imax - 1) - 1. The -1 in the latter return statement is to adjust for the fact that imax is to the left of imin in the array.