Minimum Swaps To Make Identical Array

Moderate
0/80
profile
Contributed by
11 upvotes
Asked in companies
WalmartGoogleAmazon

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
4
5 6 4 10
4 6 10 5
3
1 2 3
1 3 2
Sample Output 1:
2
1
Explanation for Sample Input 1:
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.

For the second test case, ‘A’ = [1, 2, 3], ‘B’ = [1, 3, 2], here in the second array we can swap 3 with 2 to form [1, 2, 3] which is identical to ‘A’. Hence the answer is 1.
Sample Input 2:
2
5
1 2 3 4 0
0 4 3 2 1
4
1 2 3 4
1 2 3 4
Sample Output 2:
2
0
Hint

 Try Storing the indices of all the elements in the first array.

Approaches (1)
Storing Indices

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)’.
Time Complexity

O( N * log( N ) ), where N is the length of the array.

 

We are iterating over the array, costing O(N) time. To sort the position array will cost O(N*log(N)) time.

Hence the overall time complexity is O(N*log(N)).

Space Complexity

O( N ), where N is the length of the array.

 

We maintain a map of positions and an array of pairs that will cost O(N) space each.

Hence the overall space complexity is O(N)

Code Solution
(100% EXP penalty)
Minimum Swaps To Make Identical Array
Full screen
Console