Semi-Ordered Permutation Solution in C++

Problem Description

The Semi-Ordered Permutation problem is akin to organizing your sock drawer, but instead, you have a list of numbers from 1 to n that are jumbled up. The objective is to determine how many moves it takes to position the number 1 at the front and the number n at the back.

Imagine you’re at a party, needing to get your friend in a bright red shirt (number 1) to the front of the line, while the guy in the Hawaiian shirt (number n) needs to be at the back. You can only move them around, and you want to do it in the least number of moves possible.

Code Solution

class Solution {
 public:
  int semiOrderedPermutation(vector& nums) {
    const int n = nums.size();
    const int index1 = find(nums.begin(), nums.end(), 1) - nums.begin();
    const int indexN = find(nums.begin(), nums.end(), n) - nums.begin();
    return index1 + (n - 1 - indexN) - (index1 > indexN ? 1 : 0);
  }
};

Approach

The approach is straightforward. First, we find the indices of the numbers 1 and n in the array. Then, we calculate how many moves it takes to get 1 to the front and n to the back. If 1 is ahead of n, we need to subtract one move because moving 1 to the front will also push n back one spot.

Time and Space Complexity

• Time Complexity: O(n) – We traverse the list a couple of times to find the indices of 1 and n.
• Space Complexity: O(1) – We’re not using any extra space that grows with the input size.

Real-World Example

Consider organizing a concert lineup. You have a list of performers, and you need to get the opening act (number 1) to the stage first and the headliner (number n) to the end of the lineup. You can only swap them around, and you want to do it efficiently. This problem mirrors that scenario!