Problem Statement

Given an array of n distinct elements, find the minimum number of swaps required to sort the array.

Examples:

Input: {4, 3, 2, 1}
Output: 2
Explanation: Swap index 0 with 3 and 1 with 2 to
              form the sorted array {1, 2, 3, 4}.

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

Problem Link

Minimum number of swaps required to sort an array - GeeksforGeeks

Code

// C++ program to find
// minimum number of swaps
// required to sort an array
#include<bits/stdc++.h>

using namespace std;

// Function returns the
// minimum number of swaps
// required to sort the array
int minSwaps(int arr[], int n)
{
	// Create an array of
	// pairs where first
	// element is array element
	// and second element
	// is position of first element
	pair<int, int> arrPos[n];
	for (int i = 0; i < n; i++)
	{
		arrPos[i].first = arr[i];
		arrPos[i].second = i;
	}

	// Sort the array by array
	// element values to
	// get right position of
	// every element as second
	// element of pair.
	sort(arrPos, arrPos + n);

	// To keep track of visited elements.
	// Initialize
	// all elements as not visited or false.
	vector<bool> vis(n, false);

	// Initialize result
	int ans = 0;

	// Traverse array elements
	for (int i = 0; i < n; i++)
	{
		// already swapped and corrected or
		// already present at correct pos
		if (vis[i] || arrPos[i].second == i)
			continue;

		// find out the number of node in
		// this cycle and add in ans
		int cycle_size = 0;
		int j = i;
		while (!vis[j])
		{
			vis[j] = 1;

			// move to next node
			j = arrPos[j].second;
			cycle_size++;
		}

		// Update answer by adding current cycle.
		if (cycle_size > 0)
		{
			ans += (cycle_size - 1);
		}
	}

	// Return result
	return ans;
}

// Driver program to test the above function
int main()
{
	int arr[] = {1, 5, 4, 3, 2};
	int n = (sizeof(arr) / sizeof(int));
	cout << minSwaps(arr, n);
	return 0;
}

Using Map

class Solution 
{
    public:
    //Function to find the minimum number of swaps required to sort the array. 
	int minSwaps(vector<int>&nums)
	{
	    int n = nums.size();
	    unordered_map<int,int> m;
	    
	    vector<int> org = nums;
	    sort(nums.begin(),nums.end());
	    
	    for(int i=0;i<n;i++)
	    {
	        m[nums[i]] = i;
	    }
	    int swaps = 0;
	    for(int i=0;i<n;i++)
	    {
	        while(i!=m[org[i]])
	        {
	            swap(org[i],org[m[org[i]]]);
	            swaps++;
	        }
	    }
	    
	    return swaps;
	}
};