Semi-Ordered Permutation Solution in Python

Problem Description

Welcome to the world of permutations, where numbers dance around like they’re at a party, but only the numbers 1 and n (the smallest and largest) are allowed to be in their rightful places! The problem at hand is to determine how many moves it takes to semi-order a permutation of numbers from 1 to n.

Imagine you’re at a party, and you have to arrange your friends in a line. Your best friend (1) is at the back, and the party pooper (n) is at the front. You need to figure out how many moves it takes to get them to their correct positions without causing a scene.

In simpler terms, given a list of integers from 1 to n, you need to find out how many swaps are required to place 1 at the start and n at the end of the list.

Code Solution

class Solution:
    def semiOrderedPermutation(self, nums: list[int]) -> int:
        n = len(nums)
        index1 = nums.index(1)
        indexN = nums.index(n)
        return index1 + (n - 1 - indexN) - int(index1 > indexN)
    

Approach Explanation

The code works by first determining the positions of 1 and n in the list. It then calculates how many moves are needed to get 1 to the front and n to the back. The logic is simple: add the index of 1 to the number of positions left for n, and adjust for any overlap if 1 is ahead of n.

Time and Space Complexity

Real-World Example

Let’s say you’re organizing a race. The runners are numbered from 1 to n, and you need to ensure that the fastest runner (1) is at the starting line and the slowest (n) is at the finish line. The number of moves you need to make to get them there is akin to solving the Semi-Ordered Permutation problem.