#2717

Easy

LeetCode Problem Workspace

Semi-Ordered Permutation

Find the minimum number of operations to convert a permutation into a semi-ordered permutation where 1 is first and n is last.

array simulation

Problem Statement

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 following operation any number of times: swap two elements of the permutation.

Your task is to return the minimum number of operations required to make the permutation semi-ordered. A permutation is a sequence of distinct numbers from 1 to n, and you must ensure that 1 is the first element and n is the last element of the array.

Examples

Example 1

Input: nums = [2,1,4,3]

Output: 2

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

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

The permutation is already a semi-ordered permutation.

Constraints

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

Solution Approach

Identify the Positions of 1 and n

The problem's main focus is to find the positions of 1 and n in the array. The key observation is that the position of 1 determines how far the rest of the elements must be moved. Similarly, the position of n influences how many swaps are needed to place it at the end of the array.

Calculate the Minimum Swaps Needed

Once you have the positions of 1 and n, the number of swaps can be determined. If both elements are out of place, the total number of swaps required will be the sum of moves for 1 and for n. Special cases occur if the two elements are overlapping or swapped to each other’s positions.

Optimize for Edge Cases

In some cases, the permutation may already be semi-ordered, meaning no swaps are needed. It's important to handle such edge cases where no operations are required, ensuring the algorithm runs efficiently.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this problem is O(n) because we need to find the positions of 1 and n, which takes linear time. The space complexity is O(1) since we only need a few variables to store the indices of 1 and n.

What Interviewers Usually Probe

Look for how well the candidate identifies the positions of 1 and n.
Evaluate if the candidate optimizes the number of swaps needed for edge cases.
Check how the candidate handles scenarios where the permutation is already semi-ordered.

Common Pitfalls or Variants

Common pitfalls

Candidates may not properly consider edge cases where the array is already semi-ordered.
There might be confusion with how to calculate the number of swaps when 1 and n are close to each other.
Not optimizing the number of operations in cases where no swaps are necessary.

Follow-up variants

What if the permutation is larger than 50 elements?
How would the problem change if the first and last elements were arbitrary numbers instead of 1 and n?
What if you were allowed to move elements around in groups rather than just swapping?

FAQ

What is the minimum number of operations to make nums a semi-ordered permutation?

The minimum number of operations is determined by finding the positions of 1 and n and calculating how many swaps are necessary to place 1 at the start and n at the end.

How do I handle the edge case where the permutation is already semi-ordered?

If the permutation is already semi-ordered, no swaps are needed, and the answer should be 0.

What if 1 and n are close to each other in the array?

If 1 and n are close to each other, the number of swaps required may be reduced. You should handle these cases by carefully calculating the moves needed for both numbers without unnecessary swaps.

What is the time complexity of solving this problem?

The time complexity is O(n), as you need to find the positions of 1 and n, which involves a single scan of the array.

Can this problem be solved in less than O(n) time?

No, this problem requires at least one scan through the array to find the positions of 1 and n, so O(n) is the best time complexity.

terminal

Solution

Solution 1: Find the Positions of 1 and n

We can first find the indices $i$ and $j$ of $1$ and $n$, respectively. Then, based on the relative positions of $i$ and $j$, we can determine the number of swaps required.

1

2

3

4

5

6

7

class Solution:
    def semiOrderedPermutation(self, nums: List[int]) -> int:
        n = len(nums)
        i = nums.index(1)
        j = nums.index(n)
        k = 1 if i < j else 2
        return i + n - j - k

Continue Practicing

#2744 find maximum number of string pairs #2751 robot collisions #2682 find the losers of the circular game