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:
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 <= 501 <= nums[i] <= 50nums is a permutation.Problem Overview: You are given a permutation of numbers from 1 to n. The goal is to make the permutation semi-ordered, meaning 1 appears at the beginning of the array and n appears at the end. The only allowed operation is swapping adjacent elements. The task is to compute the minimum number of swaps required.
Approach 1: Bubble Sort-like Movement (O(n²) time, O(1) space)
This approach simulates how adjacent swaps move elements step by step. First locate the position of 1 and repeatedly swap it with the element to its left until it reaches index 0. Then locate n and repeatedly swap it to the right until it reaches index n-1. Each swap mirrors the behavior of a bubble sort pass where elements gradually shift toward their correct positions. The simulation is easy to reason about and closely follows the allowed operation, but repeated swaps make the worst‑case time complexity O(n²). This approach is useful when explaining the mechanics of adjacent swaps during interviews.
Approach 2: Sliding Elements to Correct Position (O(n) time, O(1) space)
The optimal observation is that you do not need to simulate every swap. Instead, compute how many swaps are required based on the positions of 1 and n. If pos1 is the index of 1, it needs exactly pos1 swaps to move to the front. If posN is the index of n, it needs (n - 1 - posN) swaps to reach the last position. A special case appears when n is positioned before 1; moving 1 left shifts n one step to the right automatically, so one swap is saved. The final formula becomes pos1 + (n - 1 - posN) - (posN < pos1 ? 1 : 0). This turns the problem into a single linear scan of the array combined with simple index arithmetic, which is why it runs in O(n) time.
The key insight is that adjacent swaps only shift elements by one position. Counting the distance each target element must travel gives the exact swap count without performing the swaps. This is a common technique in simulation problems where the final movement cost can be derived mathematically instead of simulated.
Recommended for interviews: The sliding-elements approach is the expected solution. Interviewers want to see the observation that swap counts equal positional distance and the adjustment when n appears before 1. Mentioning the bubble-style simulation first shows understanding of the mechanics, but deriving the O(n) formula demonstrates stronger algorithmic reasoning.
Calculate the number of swaps needed to bring '1' to the start of the array and 'n' to the end of the array. This approach minimizes the number of moves by directly calculating the distance '1' needs to travel to reach index 0 and how far 'n' needs to travel to reach the last index.
This function searches for the positions of elements '1' and 'n' in the array. The number of moves is calculated by summing the distance from '1' to the start and 'n' to the end. If '1' is positioned after 'n', we subtract one move since the swaps overlap.
Time Complexity: O(n) - we make a single pass to find positions.
Space Complexity: O(1) - no additional space required beyond input.
Another intuitive approach involves simulating the swaps in a step-by-step manner, similar to bubble sort. We bubble '1' to the start and 'n' to the end.
Using pointers to track swaps, first accumulate swaps to move '1' to index 0. Similarly, swap to push 'n' to the last position. Adjust final count if overlap occurs.
Time Complexity: O(n)
Space Complexity: O(1)
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.
If i < j, the number of swaps required is i + n - j - 1. If i > j, the number of swaps required is i + n - j - 2.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Sliding Elements to Correct Position | Time Complexity: O(n) - we make a single pass to find positions. |
| Bubble Sort-like Movement | Time Complexity: O(n) |
| Find the Positions of 1 and n | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bubble Sort-like Movement | O(n²) | O(1) | When demonstrating how adjacent swaps physically move elements step by step |
| Sliding Elements to Correct Position | O(n) | O(1) | Best general solution; compute swap counts directly using element positions |
6424. Semi-Ordered Permutation | Leetcode Weekly Contest 348 | Solution Code. • Optimization • 834 views views
Watch 9 more video solutions →Practice Semi-Ordered Permutation with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor