You are given an unordered array consisting of consecutive integers [1, 2, 3, ..., n] without any duplicates. You are allowed to swap any two elements. Find the minimum number of swaps required to sort the array in ascending order
Eg

Input:
nums = {2, 8, 5, 4}
Output:
1
Explaination:
swap 8 with 4.

Input:
nums = {2,4,5,1,3}
Output:
3

My Approach:

• Store the elements value and their corresponding index in a pair and we have a vector of pairs
• now sort the vector according to their value
• Now traverse this vector V and compare V[i].second & i
• If equal that means they were at the same position in the orignal array so dont do anything else swap V[i] with V[ V[i].second]
• Now it may happen that even after swapping the element is not in the correct position so we do i--
• In a way we first sort the array and then compare it with the orignal array to to find the swaps

	int minSwaps(vector<int>&nums)
	{
	    vector<pair<int,int>> v;
	    int n=nums.size();
	    for(int i=0;i<n;i++)
	    {
	        v.push_back({nums[i],i});
	    }
	    sort(v.begin(),v.end());
	    int swaps=0;
	    for(int i=0;i<n;i++)
	    {
	        if(v[i].second==i) continue;
	        else {
	            swaps++;
	            swap(v[i],v[v[i].second]);
	            i--;
	        }
	    }
	    return swaps;
	}

Note : This code passed all testcases on hackerrank rank & gfg but failed on coding ninja idk what's wrong there
Working Code :

Another Approach (Ideally ) :

• This can be easily done by visualizing the problem as a graph. We will have n nodes and an edge directed from node i to node j if the element at i’th index must be present at j’th index in the sorted array.
• The graph will now contain many non-intersecting cycles. Now a cycle with 2 nodes will only require 1 swap to reach the correct ordering, similarly, a cycle with 3 nodes will only require 2 swaps to do so.
• so ans+=(cycle_size-1) for every cycle
  Graph for {4, 3, 2, 1} :
  
• Time Complexity: O(n Log n)
• Auxiliary Space: O(n)
  Code

int minSwaps(int n, vector<int> a)
{
    pair<int, int> p[n];
	vector<bool> visited(n, false);
    
    for (int i = 0; i < n; i++)
    {
        p[i].first = a[i];
        
        // Storing the original position of a[i]
        p[i].second = i;
    }
    
    sort(p, p+n);
    int ans = 0;
    
    for (int i = 0; i < n; i++)
    {	
    	//visited[i]=true indicates that index i belongs to a cycle that is already counted
        
        //p[i].second = i denotes that the ith element was at its correct position
        
        if (visited[i] || p[i].second == i)
            continue;
            
        int cycle_size = 0;
        int j = i;
        
        //Counting the size of the cycle
        while (!visited[j])
        {
            visited[j] = 1;
            j = p[j].second;
            cycle_size++;
        }
        
        ans += (cycle_size - 1);
    }
    
    return ans;
    
}