LeetCode 2717 - Semi-Ordered Permutation

The problem gives us a permutation nums of length n. A permutation means the array contains every integer from 1 to n exactly once. A permutation is considered semi-ordered when: - The first element is 1 - The last element is n We are allowed to repeatedly swap adjacent elements.

leetcodeeasyarraysimulation

LeetCode Problem 2717

Difficulty: 🟢 Easy
Topics: Array, Simulation

Solution

LeetCode 2717 - Semi-Ordered Permutation

Problem Understanding

The problem gives us a permutation nums of length n. A permutation means the array contains every integer from 1 to n exactly once.

A permutation is considered semi-ordered when:

  • The first element is 1
  • The last element is n

We are allowed to repeatedly swap adjacent elements. Each adjacent swap counts as one operation. The goal is to determine the minimum number of adjacent swaps needed to transform the given permutation into a semi-ordered permutation.

The important detail is that we do not care about the ordering of the middle elements. The only requirements are:

  • 1 must end up at index 0
  • n must end up at index n - 1

Because only adjacent swaps are allowed, moving an element by one position costs one operation.

The input size is very small:

  • 2 <= n <= 50

This means even less efficient solutions could pass, but the problem has a direct mathematical observation that leads to a very clean optimal solution.

There are several important edge cases to keep in mind.

If 1 is already at the front and n is already at the back, the answer is 0.

If 1 appears after n, moving 1 leftward can shift n one position left. This interaction is easy to overlook and is the main tricky part of the problem.

Because the array is guaranteed to be a valid permutation, we never need to worry about duplicates or missing values.

Approaches

Brute Force Approach

A brute force approach would explicitly simulate adjacent swaps.

We could repeatedly:

  1. Move 1 toward the front using adjacent swaps.
  2. Move n toward the end using adjacent swaps.
  3. Count every swap performed.

This works because adjacent swaps directly model the allowed operation. Every swap decreases the distance between the target element and its desired position by exactly one.

However, simulation is more complicated than necessary. We do not actually need to modify the array step by step because the number of swaps required can be computed directly from the positions of 1 and n.

Although the constraints are small enough that simulation would pass, it introduces unnecessary implementation complexity.

Optimal Observation

The key insight is that adjacent swaps behave like distance movement.

If:

  • 1 is currently at index pos1
  • n is currently at index posN

then:

  • Moving 1 to index 0 requires pos1 swaps
  • Moving n to index n - 1 requires (n - 1 - posN) swaps

At first glance, the answer seems to be:

pos1 + (n - 1 - posN)

However, there is one important interaction.

If pos1 > posN, then 1 starts to the right of n.

When we move 1 leftward, it must cross over n. That crossing shifts n one position to the left automatically. As a result, n becomes closer to the end by one step, so we save one swap overall.

Therefore:

  • If pos1 < posN, answer is:
pos1 + (n - 1 - posN)
  • If pos1 > posN, answer is:
pos1 + (n - 1 - posN) - 1

This gives an elegant linear-time solution.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Simulates adjacent swaps directly
Optimal O(n) O(1) Computes answer directly from positions

Algorithm Walkthrough

  1. Traverse the array once to find:
  • The index of 1
  • The index of n

These are the only two values that matter for the final arrangement. 2. Compute how many swaps are needed to move 1 to the front.

Since adjacent swaps move an element by one position at a time, moving 1 from index pos1 to index 0 requires exactly pos1 swaps. 3. Compute how many swaps are needed to move n to the end.

The last valid index is n - 1. If n is currently at posN, then it needs:

(n - 1 - posN)

swaps. 4. Add both values together.

This gives the total swaps assuming the movements do not interfere with each other. 5. Handle the overlap case.

If 1 starts to the right of n, then moving 1 leftward causes it to pass over n.

During that crossing, n automatically shifts one position left. That effectively saves one future swap when moving n to the end.

Therefore subtract 1 when:

pos1 > posN
  1. Return the final result.

Why it works

Adjacent swaps move elements one position at a time, so the minimum number of swaps needed to move an element to a target index equals the distance between the current and target positions.

The only complication is that moving one target element can affect the position of the other. When 1 crosses over n, the position of n changes by one automatically, reducing the required swaps by one. Accounting for this interaction guarantees the minimum possible operation count.

Python Solution

from typing import List

class Solution:
    def semiOrderedPermutation(self, nums: List[int]) -> int:
        n = len(nums)

        pos1 = nums.index(1)
        posN = nums.index(n)

        swaps = pos1 + (n - 1 - posN)

        if pos1 > posN:
            swaps -= 1

        return swaps

The implementation first determines the array length because we need the value n and the last index n - 1.

The index() method is then used to locate the positions of 1 and n. Since the array is guaranteed to be a valid permutation, both values are guaranteed to exist.

The base number of swaps is computed as:

distance to move 1 left
+
distance to move n right

Finally, the overlap adjustment is applied. If 1 originally appears after n, we subtract one because moving 1 leftward already shifts n closer to its destination.

The solution is concise because the mathematical observation eliminates the need for explicit simulation.

Go Solution

func semiOrderedPermutation(nums []int) int {
    n := len(nums)

    pos1 := 0
    posN := 0

    for i, value := range nums {
        if value == 1 {
            pos1 = i
        }

        if value == n {
            posN = i
        }
    }

    swaps := pos1 + (n - 1 - posN)

    if pos1 > posN {
        swaps--
    }

    return swaps
}

The Go implementation follows the exact same logic as the Python solution.

Unlike Python, Go does not have a built-in index() method for slices, so we manually iterate through the array to find the positions of 1 and n.

All calculations use standard integers. Since the constraints are tiny, integer overflow is not a concern.

Worked Examples

Example 1

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

Step 1: Find positions

Value Position
1 1
4 2

Here:

n = 4
pos1 = 1
posN = 2

Step 2: Compute swaps

Moves needed for 1:

1

Moves needed for 4:

3 - 2 = 1

Total:

1 + 1 = 2

Since:

pos1 < posN

there is no overlap adjustment.

Final Answer

2

Example 2

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

Step 1: Find positions

Value Position
1 2
4 1

So:

pos1 = 2
posN = 1

Step 2: Compute swaps

Moves for 1:

2

Moves for 4:

3 - 1 = 2

Initial total:

2 + 2 = 4

Step 3: Apply overlap correction

Since:

pos1 > posN

subtract 1:

4 - 1 = 3

Final Answer

3

Example 3

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

Step 1: Find positions

Value Position
1 0
5 4

Step 2: Compute swaps

Moves for 1:

0

Moves for 5:

4 - 4 = 0

Total:

0

Final Answer

0

Complexity Analysis

Measure Complexity Explanation
Time O(n) One pass is used to locate 1 and n
Space O(1) Only a few variables are stored

The algorithm only scans the array once and performs constant-time arithmetic afterward. No auxiliary data structures proportional to input size are needed.

Test Cases

from typing import List

class Solution:
    def semiOrderedPermutation(self, nums: List[int]) -> int:
        n = len(nums)

        pos1 = nums.index(1)
        posN = nums.index(n)

        swaps = pos1 + (n - 1 - posN)

        if pos1 > posN:
            swaps -= 1

        return swaps

solution = Solution()

assert solution.semiOrderedPermutation([2,1,4,3]) == 2  # basic example
assert solution.semiOrderedPermutation([2,4,1,3]) == 3  # overlap case
assert solution.semiOrderedPermutation([1,3,4,2,5]) == 0  # already valid

assert solution.semiOrderedPermutation([1,2]) == 0  # smallest already ordered
assert solution.semiOrderedPermutation([2,1]) == 1  # smallest possible swap

assert solution.semiOrderedPermutation([3,1,2]) == 1  # move 1 left only
assert solution.semiOrderedPermutation([1,2,3,4]) == 0  # already semi-ordered
assert solution.semiOrderedPermutation([4,1,2,3]) == 1  # move 4 right only

assert solution.semiOrderedPermutation([2,3,4,5,1]) == 7  # 1 at end
assert solution.semiOrderedPermutation([5,1,2,3,4]) == 4  # n at front

assert solution.semiOrderedPermutation([3,2,1,4]) == 2  # move 1 to front
assert solution.semiOrderedPermutation([4,2,3,1]) == 5  # both need movement

Test Case Summary

Test Why
[2,1,4,3] Standard example without overlap
[2,4,1,3] Tests overlap adjustment
[1,3,4,2,5] Already semi-ordered
[1,2] Smallest valid ordered permutation
[2,1] Smallest unordered permutation
[3,1,2] Only 1 needs movement
[1,2,3,4] Completely ordered array
[4,1,2,3] Only n needs movement
[2,3,4,5,1] Maximum movement for 1
[5,1,2,3,4] Maximum movement for n
[3,2,1,4] 1 far from front
[4,2,3,1] Both targets heavily displaced

Edge Cases

One important edge case occurs when the array is already semi-ordered. In this situation, 1 is already at index 0 and n is already at index n - 1. A buggy implementation might still perform unnecessary calculations or swaps. The current implementation handles this naturally because both required movement distances become zero.

Another critical edge case happens when 1 appears after n. This is the main tricky scenario in the problem. A naive formula that simply adds both movement distances would overcount by one because moving 1 leftward automatically shifts n left during the crossing. The implementation explicitly checks pos1 > posN and subtracts one to correct this.

A third important edge case is the smallest possible input size, where n = 2. With only two elements, there are very few possible configurations, and indexing mistakes become more noticeable. The implementation works correctly because the formulas remain valid even at minimal size. For example, [2,1] requires exactly one adjacent swap.

Another subtle case occurs when only one target element is misplaced. For example, if 1 is already at the front but n is not at the end, the formula correctly computes zero swaps for 1 and only counts the movement needed for n. The same logic works symmetrically when n is already correctly positioned.