algoadvance

Leetcode 2717. Semi

Problem Statement

Given a permutation of integers from 1 to n, a permutation is called semi-ordered if and only if the first element is 1 and the last element is n.

You need to determine the minimum number of swaps required to make the given permutation semi-ordered.

Example

Clarifying Questions

  1. What is the range of the number of elements n?
    • Assume 1 <= n <= 1000.
  2. Can there be duplicate elements in the permutation?
    • No, since it’s a permutation, each number from 1 to n appears exactly once.
  3. Is there any restriction on the maximum number of swaps?
    • The task is just to find the minimum number of swaps required.

Strategy

  1. Identify positions of 1 and n: Locate the positions of the smallest and largest element in the array.
  2. Calculate required swaps:
    • If the position of 1 is not already at the beginning (index of 1 != 0), calculate the minimum swaps to bring 1 to the start of the array.
    • If the position of n is not already at the end (index of n != n-1), calculate the minimum swaps to bring n to the end of the array.
  3. Adjust for overlap: Consider the case where moving 1 and n might interfere with each other.

Code Implementation in C++

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

int minSwapsToSemiOrdered(vector<int>& nums) {
    int n = nums.size();
    int posOne = -1, posN = -1;
    
    // Finding the position of 1 and n in the array
    for (int i = 0; i < n; ++i) {
        if (nums[i] == 1) posOne = i;
        if (nums[i] == n) posN = i;
        if (posOne != -1 && posN != -1) break;
    }
    
    int swapsToFront = posOne;
    int swapsToEnd = (n - 1 - posN);
    
    // If the `1` is initially at the front or `n` is initially at the end
    if (posOne < posN) {
        // They don't interfere
        return swapsToFront + swapsToEnd;
    } else {
        // They interfere, reduce one swap since one element will be moved into a position that affects the other directly
        return swapsToFront + swapsToEnd - 1;
    }
}

int main() {
    vector<int> nums = {2, 1, 3, 4};  // You can change this for different inputs
    cout << "Minimum number of swaps to make semi-ordered: " << minSwapsToSemiOrdered(nums) << endl;
    return 0;
}

Time Complexity

The time complexity of this solution is O(n) due to the single pass needed to find the positions of 1 and n. After that, the required swaps calculation is constant time, O(1). Hence, the overall complexity is O(n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI