Semi-Ordered Permutation

Problem Description

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 operation of swapping two adjacent elements in nums as many times as you want until you make nums a semi-ordered permutation. Return the minimum number of operations to make nums a semi-ordered permutation.

Key Insights

• A permutation is semi-ordered if it starts with 1 and ends with n.
• The number of swaps needed depends on the positions of 1 and n in the array.
• If 1 is to the right of n, then the total number of swaps will be the sum of the distances of 1 and n from their desired positions.
• Swapping adjacent elements will incrementally move 1 to the front and n to the back.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we will identify the positions of the numbers 1 and n in the array. We then calculate the number of swaps required to move 1 to the front (position 0) and n to the back (position n-1). If 1 is located after n in the array, we need to account for the overlap when counting the swaps.

1. Find the index of 1 (index_of_one).
2. Find the index of n (index_of_n).
3. Calculate the number of swaps needed to bring 1 to the front and n to the back.
4. Adjust the count if necessary based on the relative positions of 1 and n.

Code Solutions