# Semi-Ordered Permutation
**Difficulty:** EASY
[External](https://leetcode.com/problems/semi-ordered-permutation)
Canonical: https://scaleengineer.com/dsa/problems/semi-ordered-permutation
**Data structures:** Array
---
## 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.`

# Approaches
## Direct Simulation
This approach directly simulates the process of moving the elements `1` and `n` to their target positions. It's an intuitive, greedy strategy. First, we focus on moving `1` to the beginning of the array (index 0) by repeatedly swapping it with its left neighbor. Then, in the modified array, we move `n` to the end (index `n-1`) by swapping it with its right neighbor. The total number of swaps is counted throughout this process.
**Time:** O(n). Finding the initial position of `1` takes O(n). The simulation loop for `1` runs O(n) times. Finding the position of `n` takes another O(n). The total time complexity is O(n) + O(n) + O(n) = O(n). · **Space:** O(1) if the simulation is done in-place on the input array.
**Pros:** The logic is straightforward and easy to follow.; It correctly solves the problem by breaking it down into two simpler subproblems.
**Cons:** Performs multiple passes over the array.; Involves modifying the input array, which might not be desirable.; Less efficient in terms of constant factors and actual operations compared to the analytical approach, although both have the same O(n) time complexity.
### Explanation
The algorithm works in two distinct phases:

1.  **Move `1` to the front:** We first iterate through the array to find the index of `1`, let's call it `pos1`. The number of adjacent swaps required to move it to index 0 is exactly `pos1`. We simulate this by performing `pos1` swaps, moving `1` leftward one step at a time. We add `pos1` to our total swap count.

2.  **Move `n` to the end:** After `1` is in its correct place, the array is now different. We must find the new position of `n`. We iterate through the modified array to find `n`'s index, `posn`. The number of swaps to move it to the end is `(n - 1) - posn`. We simulate these swaps and add this count to our total.

The final result is the sum of swaps from both phases.

```java
class Solution {
    public int semiOrderedPermutation(int[] nums) {
        int n = nums.length;
        int swaps = 0;

        // Phase 1: Move 1 to the front
        int pos1 = -1;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                pos1 = i;
                break;
            }
        }
        
        // Simulate swapping 1 to the front
        while (pos1 > 0) {
            int temp = nums[pos1];
            nums[pos1] = nums[pos1 - 1];
            nums[pos1 - 1] = temp;
            swaps++;
            pos1--;
        }

        // Phase 2: Move n to the end
        int posn = -1;
        for (int i = 0; i < n; i++) {
            if (nums[i] == n) {
                posn = i;
                break;
            }
        }
        
        // The number of swaps for n is simply its distance from the end
        swaps += (n - 1 - posn);
        
        return swaps;
    }
}
```
### Algorithm
1. Initialize a counter `swaps` to 0.
2. Get the length of the array, `n`.
3. **Phase 1: Move `1` to the front.**
   - Find the index of `1`, let's call it `pos1`.
   - In a loop, from `i = pos1` down to `1`, swap the element at `i` with the element at `i-1`.
   - Increment `swaps` for each swap.
4. **Phase 2: Move `n` to the end.**
   - After `1` is at the front, find the new index of `n`, let's call it `posn`.
   - In a loop, from `i = posn` up to `n-2`, swap the element at `i` with the element at `i+1`.
   - Increment `swaps` for each swap.
5. Return the total `swaps`.

## Single-Pass Analytical Solution
This optimal approach calculates the minimum number of swaps in a single pass without performing any actual swaps or modifying the array. It leverages the key insight that the minimum number of adjacent swaps to move an element from index `i` to `j` is simply `|i - j|`. We can calculate the required swaps for `1` and `n` based on their initial positions and then make a single adjustment if their movement paths overlap.
**Time:** O(n), as it only requires a single pass through the array to find the positions of `1` and `n`. · **Space:** O(1), as we only use a few variables to store the indices and the result.
**Pros:** Extremely efficient, with optimal time and space complexity.; Solves the problem with a single pass and a simple calculation.; Does not require modification of the input array.
**Cons:** The logic for adjusting the swap count when `pos1 > posn` might be slightly less intuitive at first glance.
### Explanation
The core idea is to determine the number of swaps for `1` and `n` separately and then combine them intelligently.

1.  **Find Indices:** We first iterate through the array a single time to find the index of `1` (let's call it `pos1`) and the index of `n` (`posn`).

2.  **Calculate Individual Swaps:**
    - The number of swaps to move `1` from `pos1` to index 0 is `pos1`.
    - The number of swaps to move `n` from `posn` to the last index `n-1` is `(n - 1) - posn`.

3.  **Handle Overlap:** The crucial part is to consider the relative initial positions of `1` and `n`.
    - **Case 1: `pos1 < posn`**. Here, `1` is to the left of `n`. The path to move `1` to the front (indices `0` to `pos1`) and the path to move `n` to the back (indices `posn` to `n-1`) do not cross. The swaps are independent. The total swaps are `pos1 + (n - 1 - posn)`.
    - **Case 2: `pos1 > posn`**. Here, `1` is to the right of `n`. To move `1` to the front, it must pass `n`. The specific swap that moves `1` past `n` also moves `n` one step in its desired direction (to the right). This means one swap serves both purposes. Our initial sum `pos1 + (n - 1 - posn)` counts this as two separate swaps. Therefore, we have overcounted by one, and we must subtract 1 from the total. The total swaps are `pos1 + (n - 1 - posn) - 1`.

This logic leads to a very efficient, direct calculation.

```java
class Solution {
    public int semiOrderedPermutation(int[] nums) {
        int n = nums.length;
        int pos1 = -1;
        int posn = -1;

        // Single pass to find indices of 1 and n
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                pos1 = i;
            }
            if (nums[i] == n) {
                posn = i;
            }
        }

        // Calculate swaps based on relative positions
        int swaps = pos1 + (n - 1 - posn);
        if (pos1 > posn) {
            // Decrement if 1 was to the right of n, as one swap helps both.
            swaps--;
        }
        
        return swaps;
    }
}
```
### Algorithm
1. Get the length of the array, `n`.
2. Initialize `pos1 = -1` and `posn = -1`.
3. Iterate through the `nums` array once from `i = 0` to `n-1`.
   - If `nums[i] == 1`, update `pos1 = i`.
   - If `nums[i] == n`, update `posn = i`.
4. Calculate the total swaps. The base number of swaps is `pos1` (to move `1` to the front) + `(n - 1 - posn)` (to move `n` to the end).
5. Check if `pos1 > posn`. If it is, it means `1` started to the right of `n`. In this case, one of the swaps to move `1` leftwards also moves `n` rightwards, so we have double-counted one operation. We must subtract 1 from the total.
6. Return the final calculated number of swaps.

# Solutions
### Java

```java
class Solution {
public
  int semiOrderedPermutation(int[] nums) {
    int n = nums.length;
    int i = 0, j = 0;
    for (int k = 0; k < n; ++k) {
      if (nums[k] == 1) {
        i = k;
      }
      if (nums[k] == n) {
        j = k;
      }
    }
    int k = i < j ? 1 : 2;
    return i + n - j - k;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int semiOrderedPermutation(vector<int> &nums) {
    int n = nums.size();
    int i = find(nums.begin(), nums.end(), 1) - nums.begin();
    int j = find(nums.begin(), nums.end(), n) - nums.begin();
    int k = i < j ? 1 : 2;
    return i + n - j - k;
  }
};

```

### Python

```python
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

```