Last Updated: 22 Jan, 2022

Minimum Swaps To Make Identical Array

Moderate

Asked in companies

Solve now

Problem statement

You are given two arrays, ‘A’ and ‘B’, with the same elements in a different order. Your task is to make ‘B’ identical to the ‘A’ by swapping the elements in array ‘B’. You have to find out the minimum number of swaps required.

For Example:

For the first test case, ‘A’ = [5, 6, 4, 10], ‘B’ = [4, 6, 10, 5], here in the ‘B’ we can swap 4 with 10 to form [10, 6, 4, 5] and we can then swap 10 with 5 to form the array [5, 6, 4, 10] which is identical to ‘A’. Hence the answer is 2.

Input Format:

The first input line contains a single integer  ‘T’ representing the number of test cases.

The first line of each test case contains a single integer ‘N’ representing the size of both arrays.

The second line of each test case contains ‘N’ space-separated integers representing the ‘A’ array elements.

The third line of each test case contains ‘N’ space-separated integers representing the ‘B’ array elements.

Output Format:

For each test case, print a single integer representing the minimum number of swaps required to make ‘B’ identical to ‘A’

Print a separate line for each test case.

Constraints:

1 ≤ T ≤ 10
1 ≤ N ≤ 1000
0 ≤ A[i], B[i] ≤ 10^9

Time Limit: 1 sec

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Solve now

Approaches

01 Approach

In this approach, we will try to store the indices of all the elements in the first array in the second array. Suppose the ith element in the first array is at jth position in the second array. In that case, we store B[i] = j, now we know the elements that should be at ith index in B is actually at B[i]th position.

So we have an array of current positions of elements at each index. If we sort this array with a minimum number of swaps, we would have put all the elements correctly. For example: if A = [5, 6, 4, 10] and B = [4, 6, 10, 5], after putting the indices we will have B = [2, 1, 3, 0], if we sort this array will put all the elements in positions they were in A.

We can count minimum swaps to sort the array by making the array into a graph where we will put an edge from the current position to the final position in the array and count the cycles in the graph.

To count the minimum number of swaps to sort the array, we will create a function swapsToSort(arr)

Algorithm:

In the swapsToSort(arr)
- Create an empty array ‘positions’
- Iterate ‘num’ through ‘arr’
  - Make pair of ‘num’ and it’s ‘index’ as ‘[num, index]’
  - Insert the above pair in ‘positions’
- Sort the ‘positions’ array
- Set ‘ans’ as 0, and create an empty array ‘visited’ equal to size ‘arr’, set all the False.
- Iterate i through all indices of ‘arr’
  - If’ visited[i]’ or ‘position[i][0]’ is equal to ‘i’, ‘continue’ the loop
  - Set ‘cycleSize’ to 0
  - Set ‘startNode’ as i
  - While’ visited[startNode]’ is ‘False’,
    - Set ‘visited[startNode]’ as ‘True’
    - Set ‘startNode’ as ‘positioin[0][i]’
    - ‘cycleSize’ increase by 1
  - Add ‘cycleSize’ - 1 to ‘ans’
- Return’ ans’
In the given functions
- Set ‘indices’ as map of integers.
- Iterate i through all the indices of ‘A’.
  - Set ‘indices[A[i]]’ as i.
- Iterate through all the indices of ‘B’.
  - Set ‘B[i]’ as ‘indices[A[i]]’.
- Return ‘swapsToSort(B)’.

Solve now