Teaching Kids Programming – Minimum Swaps to Get Semi-Ordered Permutation

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Example 1:
Input: nums = [2,1,4,3]
Output: 2
Explanation: We can make the permutation semi-ordered using these sequence of operations:
1 – swap i = 0 and j = 1. The permutation becomes [1,2,4,3].
2 – swap i = 2 and j = 3. The permutation becomes [1,2,3,4].
It can be proved that there is no sequence of less than two operations that make nums a semi-ordered permutation.

Example 2:
Input: nums = [2,4,1,3]
Output: 3
Explanation: We can make the permutation semi-ordered using these sequence of operations:
1 – swap i = 1 and j = 2. The permutation becomes [2,1,4,3].
2 – swap i = 0 and j = 1. The permutation becomes [1,2,4,3].
3 – swap i = 2 and j = 3. The permutation becomes [1,2,3,4].
It can be proved that there is no sequence of less than three operations that make nums a semi-ordered permutation.

Example 3:
Input: nums = [1,3,4,2,5]
Output: 0
Explanation: The permutation is already a semi-ordered permutation.

Constraints:
2 <= nums.length == n <= 50
1 <= nums[i] <= 50
nums is a permutation.

In this blog post, we’ll explore a problem from LeetCode – Semi-Ordered Permutation. We will dive into the problem statement, understand the constraints and work our way through a Python solution. The goal here is to help you gain a clear understanding of this problem and how it can be solved effectively.

Minimum Swaps to Get Semi-Ordered Permutation

Problem Statement
In the Semi-Ordered Permutation problem, we 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. The challenge here is to convert this permutation into a semi-ordered permutation with the least number of operations.

In each operation, you can pick two adjacent elements in nums and swap them. The goal is to return the minimum number of operations to make nums a semi-ordered permutation​1​.

Let’s break this down with an example:

Consider the input nums = [2,1,4,3]. To convert it into a semi-ordered permutation, we need at least 2 operations:

Swap i = 0 and j = 1. The permutation becomes [1,2,4,3].
Swap i = 2 and j = 3. The permutation becomes [1,2,3,4]​1​.

Constraints

Before diving into the solution, let’s understand the constraints of the problem:
The length of nums is equal to n and lies in the range 2 <= n <= 50.
Each element in nums is a unique integer from 1 to n​.

Solution

Now let’s discuss the provided Python solution:

1
2
3
4
5
6
7
8

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

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

In the solution, we first find the indices of 1 and n in the array. The number of operations required will be the sum of the distances of 1 and n from the ends of the array. If 1 is to the left of n (i.e., a < b), we return a + n – 1 – b. If 1 is to the right of n, we save one operation because when n and 1 meet in the middle, one swap moves two. So, we return a + n – b – 2.

This solution capitalizes on the fact that our target is a semi-ordered permutation where 1 is at the start and n is at the end. By locating these two numbers and calculating the steps needed to move them to their required positions, we can find the minimum operations needed.

The time complexity is O(N) since we need to find the number 1 and n in the unsorted array. The space complexity is O(1) constant.

The index function will find the index of the given array, if the element is not in the array, it will throw an ValueError Exception.

Conclusion

The Semi-Ordered Permutation problem is a great example of how we can leverage the properties of the problem (in this case, the definition of a semi-ordered permutation) to find an efficient solution. By understanding the underlying pattern, we can often come up with a solution that is more intuitive and efficient than a brute-force approach.

Keep practicing and happy coding!

–EOF (The Ultimate Computing & Technology Blog) —