Easy Solution Beats 100% (C++)
IntuitionFirst, find the indexes of the elements 1 and n, where n is the length of the array. Then, find the distance from index 0 to the index of 1, and the di
# Intuition
First, find the indexes of the elements $1$ and $n$, where $n$ is the length of the array. Then, find the distance from index $0$ to the index of $1$, and the distance between index $n$ and the index of $n$.
# Approach
One way to solve this is by iterating over the array to find the indexes of $1$ and $n$. Once found, loop over the array a second time, this time swapping the elements until the array is semi-ordered, counting the amount of swaps and returning it. This results in $O(n)$ time complexity and takes constant space.

This solution works just fine, however, there is a few optimizations we can make. First, we can break out of the searching loop early once we have found both indexes. More importantly, we can completely avoid the second loop by just calculating the amount of moves it would take, rather than counting. To do so, add the distances from index $0$ to the index of $1$ and index $n-1$ to the index of $n$. Its important to remember that if the index of $n$ comes before the index of $1$, they either are or will be adjacent to each other while swapping elements. This means you can swap them both at once, taking once less move.

# Complexity
- Time complexity:
$$O(n)$$

- Space complexity:
$$O(1)$$

# Code
```cpp []
class Solution {
public:
    int semiOrderedPermutation(vector<int>& nums) {
        const int n = nums.size();
        // in this case the array is already semi ordered
        if(nums[0] == 1 && nums[n-1] == n) return 0;


        int indexN = -1; // index of n
        int index1 = -1; // index of 1

        // search for indexes
        for(int i = 0; i < n; ++i) {
            int num = nums[i];

            if(num == 1)
                index1 = i;
            
            if(num == n)
                indexN = i;

            // break early once both have been found
            if(indexN != -1 && index1 != -1)
                break;
        } 
        
        int moves = 0;
        moves += (n - indexN - 1); // subtract 1 here since you want the index n-1, not n
        moves += (index1);

        // in this case they are / will be adjacent, 
        // so you can make one less move by swapping both at once
        if(indexN < index1) 
            --moves;

        return moves;
    }
};
```


This is my first solution, so please provide feedback!
['C++']