Minimum swaps to make two arrays identical

Software Development
#1

Given two arrays that have the same values but in a different order, we need to make a second array the same as a first array using the minimum number of swaps.
Examples:

Input : arrA[] = {3, 6, 4, 8},
arrB[] = {4, 6, 8, 3}
Output : 2
we can make arrB to same as arrA in 2 swaps
which are shown below,
swap 4 with 8, arrB = {8, 6, 4, 3}
swap 8 with 3, arrB = {3, 6, 4, 8}

This problem can be solved by modifying the array B. We save the index of array A elements in array B i.e. if ith element of array A is at jth position in array B, then we will make arrB[i] = j
For above given example, modified array B will be, arrB = {3, 1, 0, 2}. This modified array represents the distribution of array A element in array B and our goal is to sort this modified array in a minimum number of swaps because after sorting only array B element will be aligned with array A elements.

So we count these swaps in a modified array and that will be our final answer.
Please see the below code for a better understanding.

  • C++
  • Java
  • Python3
  • C#
  • Javascript

// C++ program to make an array same to another

// using minimum number of swap

#include <bits/stdc++.h>

using namespace std;

// Function returns the minimum number of swaps

// required to sort the array

// This method is taken from below post

// https://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/

int minSwapsToSort( 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.

ans += (cycle_size - 1);

}

// Return result

return ans;

}

// method returns minimum number of swap to make

// array B same as array A

int minSwapToMakeArraySame( int a[], int b[], int n)

{

// map to store position of elements in array B

// we basically store element to index mapping.

map< int , int > mp;

for ( int i = 0; i < n; i++)

mp[b[i]] = i;

// now we're storing position of array A elements

// in array B.

for ( int i = 0; i < n; i++)

b[i] = mp[a[i]];

/* We can uncomment this section to print modified

b array

for (int i = 0; i < N; i++)

cout << b[i] << " ";

cout << endl; */

// returing minimum swap for sorting in modified

// array B as final answer

return minSwapsToSort(b, n);

}

// Driver code to test above methods

int main()

{

int a[] = {3, 6, 4, 8};

int b[] = {4, 6, 8, 3};

int n = sizeof (a) / sizeof ( int );

cout << minSwapToMakeArraySame(a, b, n);

return 0;

}

Output:

2