Skip to main content
Talentd

Semi-Ordered Permutation - Solution & Explanation

EasyArraySimulation15 min read
Practice this problem

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 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.

Approach Overview

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.

Approach 1: Sliding Elements to Correct Position

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) - we make a single pass to find positions.
Space Complexity: O(1) - no additional space required beyond input.

Try this approach in the editor →

Approach 2: Bubble Sort-like Movement

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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

Try this approach in the editor →

Approach 3: 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.

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).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Elements to Correct Position

Time Complexity: O(n) - we make a single pass to find positions.
Space Complexity: O(1) - no additional space required beyond input.

Bubble Sort-like Movement

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

Find the Positions of 1 and n—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Bubble Sort-like MovementO(n²)O(1)When demonstrating how adjacent swaps physically move elements step by step
Sliding Elements to Correct PositionO(n)O(1)Best general solution; compute swap counts directly using element positions

Video Solution

6424. Semi-Ordered Permutation | Leetcode Weekly Contest 348 | Solution Code. • Optimization • 834 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Semi-Ordered Permutation easy or hard?
Semi-Ordered Permutation is categorized as an Easy problem. The main challenge is recognizing that the minimum number of adjacent swaps equals the distance each element must travel, with a small adjustment when the elements cross.
How to solve Semi-Ordered Permutation in O(n)?
Scan the array to find pos1 (index of 1) and posN (index of n). The swaps needed are pos1 to bring 1 to the front and (n - 1 - posN) to push n to the end. If posN is less than pos1, subtract one because moving 1 left shifts n right by one position. The final formula is pos1 + (n - 1 - posN) - (posN < pos1 ? 1 : 0).
Semi-Ordered Permutation Python or Java solution?
Both Python and Java implementations follow the same logic: iterate through the array to find the indices of 1 and n, compute the swap formula, and return the result. The algorithm remains O(n) time and O(1) space regardless of the language.
What is the best approach for Semi-Ordered Permutation?
The best approach tracks the indices of 1 and n and calculates how many adjacent swaps each element needs to reach its target position. Move 1 to index 0 and n to index n-1 using positional distance. If n appears before 1, subtract one swap because moving 1 left shifts n right automatically. This solution runs in O(n) time and O(1) space.
Is Semi-Ordered Permutation asked at Google/Amazon/Meta?
Semi-Ordered Permutation represents a typical array simulation problem seen in coding interviews. Variants of adjacent swap counting and element positioning appear in interview question sets from companies like Amazon and Google, especially in early screening rounds.
What data structure is used in Semi-Ordered Permutation?
The problem primarily uses a simple array traversal. No additional data structures such as hash maps or stacks are required because the permutation property guarantees that the values 1 and n appear exactly once.
What is the time complexity of Semi-Ordered Permutation?
The optimal solution runs in O(n) time because it scans the array once to locate the positions of 1 and n. The swap count is then computed using simple arithmetic. Space complexity remains O(1) since only a few index variables are used.

Ready to solve this problem?

Practice Semi-Ordered Permutation with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays