2717. Semi-Ordered Permutation - Solution

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

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

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

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

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

The problem

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.

Python

def min_swaps(nums):
    n = len(nums)
    pos1 = posN = 0
    for i in range(n):
        if nums[i] == 1:
            pos1 = i
        if nums[i] == n:
            posN = i
    return pos1 + (n - 1 - posN) - (1 if pos1 > posN else 0)

nums = [2, 1, 4, 3]
print(min_swaps(nums))

Java

public class Solution {
    public static int minSwaps(int[] nums) {
        int pos1 = 0, posN = 0, n = nums.length;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 1) pos1 = i;
            if (nums[i] == n) posN = i;
        }
        return pos1 + (n - 1 - posN) - (pos1 > posN ? 1 : 0);
    }
    public static void main(String[] args) {
        int[] nums = {2, 1, 4, 3};
        System.out.println(minSwaps(nums));
    }
}

C++

#include <iostream>
#include <vector>

int minSwaps(std::vector<int>& nums) {
    int n = nums.size();
    int pos1 = 0, posN = 0;
    for (int i = 0; i < n; ++i) {
        if (nums[i] == 1) pos1 = i;
        if (nums[i] == n) posN = i;
    }
    return pos1 + (n - 1 - posN) - (pos1 > posN);
}

int main() {
    std::vector<int> nums = {2, 1, 4, 3};
    std::cout << minSwaps(nums) << std::endl;
    return 0;
}

JavaScript

function minSwaps(nums) {
    const n = nums.length;
    let pos1 = 0, posN = 0;
    for (let i = 0; i < n; ++i) {
        if (nums[i] === 1) pos1 = i;
        if (nums[i] === n) posN = i;
    }
    return pos1 + (n - 1 - posN) - (pos1 > posN ? 1 : 0);
}

const nums = [2, 1, 4, 3];
console.log(minSwaps(nums));

#include <stdio.h>

int minSwaps(int* nums, int n) {
    int pos1 = 0, posN = 0;
    for (int i = 0; i < n; ++i) {
        if (nums[i] == 1) pos1 = i;
        if (nums[i] == n) posN = i;
    }
    return pos1 + (n - 1 - posN) - (pos1 > posN);
}

int main() {
    int nums[] = {2, 1, 4, 3};
    int n = sizeof(nums) / sizeof(nums[0]);
    printf("%d\n", minSwaps(nums, n));
    return 0;
}

using System;

public class Solution {
    public static int MinSwaps(int[] nums) {
        int n = nums.Length;
        int pos1 = 0, posN = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 1) pos1 = i;
            if (nums[i] == n) posN = i;
        }
        return pos1 + (n - 1 - posN) - (pos1 > posN ? 1 : 0);
    }

    public static void Main() {
        int[] nums = {2, 1, 4, 3};
        Console.WriteLine(MinSwaps(nums));
    }
}

This Python solution employs a linear scan to find positions of '1' and 'n'. We compute and return the swap count using the same formula. Clear and straightforward implementation leveraging Python's list structure.

Complexity

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

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.

Python

def min_swaps(nums):
    n = len(nums)
    pos1 = posN = steps = 0
    while nums[pos1] != 1:
        pos1 += 1
    steps += pos1
    while nums[posN] != n:
        posN += 1
    steps += (n - 1 - posN)
    if pos1 > posN:
        steps -= 1
    return steps

nums = [2, 1, 4, 3]
print(min_swaps(nums))

Java

public class Solution {
    public static int minSwaps(int[] nums) {
        int n = nums.length;
        int pos1 = 0, posN = 0, steps = 0;
        while (nums[pos1] != 1) pos1++;
        steps += pos1;
        while (nums[posN] != n) posN++;
        steps += (n - 1 - posN);
        if (pos1 > posN) steps--;
        return steps;
    }

    public static void main(String[] args) {
        int[] nums = {2, 1, 4, 3};
        System.out.println(minSwaps(nums));
    }
}

C++

#include <iostream>
#include <vector>

int minSwaps(std::vector<int>& nums) {
    int n = nums.size();
    int pos1 = 0, posN = 0, steps = 0;
    // Bubble 1 to the front
    while (nums[pos1] != 1) ++pos1;
    steps += pos1;
    // Bubble n to the back
    while (nums[posN] != n) ++posN;
    steps += (n - 1 - posN);
    if (pos1 > posN) --steps;
    return steps;
}

int main() {
    std::vector<int> nums = {2, 1, 4, 3};
    std::cout << minSwaps(nums) << std::endl;
    return 0;
}

JavaScript

function minSwaps(nums) {
    const n = nums.length;
    let pos1 = 0, posN = 0, steps = 0;
    while (nums[pos1] !== 1) pos1++;
    steps += pos1;
    while (nums[posN] !== n) posN++;
    steps += (n - 1 - posN);
    if (pos1 > posN) steps--;
    return steps;
}

const nums = [2, 1, 4, 3];
console.log(minSwaps(nums));

#include <stdio.h>

int minSwaps(int* nums, int n) {
    int pos1 = 0, posN = 0, steps = 0;
    // Bubble 1 to the front
    while (nums[pos1] != 1) ++pos1;
    steps += pos1;
    // Bubble n to the back
    while (nums[posN] != n) ++posN;
    steps += (n - 1 - posN);
    if (pos1 > posN) --steps;
    return steps;
}

int main() {
    int nums[] = {2, 1, 4, 3};
    int n = sizeof(nums) / sizeof(nums[0]);
    printf("%d\n", minSwaps(nums, n));
    return 0;
}

using System;

public class Solution {
    public static int MinSwaps(int[] nums) {
        int n = nums.Length;
        int pos1 = 0, posN = 0, steps = 0;
        while (nums[pos1] != 1) pos1++;
        steps += pos1;
        while (nums[posN] != n) posN++;
        steps += (n - 1 - posN);
        if (pos1 > posN) steps--;
        return steps;
    }

    public static void Main() {
        int[] nums = {2, 1, 4, 3};
        Console.WriteLine(MinSwaps(nums));
    }
}

Utilizing Python's while loop to iteratively derive the necessary swaps, checking conditions for index-based tasks during the execution.

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

TypeScript

function semiOrderedPermutation(nums: number[]): number {
    const n = nums.length;
    const i = nums.indexOf(1);
    const j = nums.indexOf(n);
    const k = i < j ? 1 : 2;
    return i + n - j - k;
}

func semiOrderedPermutation(nums []int) int {
	n := len(nums)
	var i, j int
	for k, x := range nums {
		if x == 1 {
			i = k
		}
		if x == n {
			j = k
		}
	}
	k := 1
	if i > j {
		k = 2
	}
	return i + n - j - k
}

Rust

impl Solution {
    pub fn semi_ordered_permutation(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let (mut i, mut j) = (0, 0);

        for k in 0..n {
            if nums[k] == 1 {
                i = k;
            }
            if nums[k] == (n as i32) {
                j = k;
            }
        }

        let k = if i < j { 1 } else { 2 };
        (i + n - j - k) as i32
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Sliding Elements to Correct Position	Time Complexity: O(n) Space Complexity: O(1)
Bubble Sort-like Movement	Time Complexity: O(n) Space Complexity: O(1)
Find the Positions of 1 and n	–

Complexity analysis

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

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.

Semi-Ordered Permutation solution and explanation

The problem

Approach overview

Approach 1: Sliding Elements to Correct Position

Approach 2: Bubble Sort-like Movement

Approach 3: Find the Positions of 1 and n

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Semi-Ordered Permutation solution and explanation

The problem

Approach overview

Approach 1: Sliding Elements to Correct Position

Approach 2: Bubble Sort-like Movement

Approach 3: Find the Positions of 1 and n

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems