# Algorithm to find minimum amount of swaps to convert array A into array B with repeated elements

I'm trying to create an algorithm that finds the minimum number of swaps to convert array A into array B. In this case the arrays can only contain the numbers 0, 1 or 2.

So for example: given a = [0, 2, 1, 2] and b = [1, 2, 0, 2]. The minimum number of swaps to convert a into b is 1, namely swap a[0] and a[2].

I've tried implenting the "Minimum number of swaps required to sort an array" algorithm (from geeksforgeeks), but this returns a higher number of swaps than expected.

Some test cases that failed:

a = [1, 1, 0, 2, 0, 1, 0, 1, 1, 1, 2, 2, 0, 2, 2, 0, 0, 2, 0, 1, 2]
b = [2, 2, 0, 1, 0, 1, 1, 2, 1, 0, 2, 0, 1, 1, 0, 2, 2, 0, 1, 2, 0]
expected: <9> but was <16>

a = [0, 0, 1, 2, 1, 2, 1, 1, 2, 2]
b = [2, 0, 2, 2, 1, 2, 1, 1, 1, 0]
expected: <2> but was <4>


Code:

import java.io.*;
import java.util.*;

class GfG {
// Function returns the
// minimum number of swaps
// required to convert array a to array b
public static int minSwaps(int[] a, int[] b)
{
int len = a.length;
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < len; i++)
map.put(a[i], i);

// Initialize result
int ans = 0;
for (int i = 0; i < len; i++) {
// If the ith element of array a is already equal to the ith element of array b
// then we don't need to swap anything, so we can move to the next element
if (a[i] == b[i])
continue;

// If we need to swap the ith element of array a with some other element
// then we can find that element in array a using the index of the ith element of array b
// that we stored in the map earlier
int j = map.get(b[i]);

// Swap the ith element of array a with the jth element
int temp = a[i];
a[i] = a[j];
a[j] = temp;

// Update the index of the swapped element in the map
map.put(a[j], j);

ans++;
}
return ans;
}
}

// Driver class
class MinSwaps {
// Driver program to test the above function
public static void main(String[] args)
{
int[] a = { 0, 0, 1, 2, 1, 2, 1, 1, 2, 2 }; // for example
int[] b = { 2, 0, 2, 2, 1, 2, 1, 1, 1, 0 }; // for example
GfG g = new GfG();
System.out.println(g.minSwaps(a, b));
}
}


Ignore already correct A-values. If you can correct two A-values by swapping them, do so. This leaves you with 3-cycles, all 0→1→2→0 or all 0→2→1→0. Each can be corrected with two swaps.

Python implementation, where I keep count of the different mismatches:

from collections import Counter

def solve(A, B):
ctr = Counter()
swaps = 0
for a, b in zip(A, B):
if a != b:
if ctr[b, a]:
ctr[b, a] -= 1
swaps += 1
else:
ctr[a, b] += 1
print(swaps + ctr.total() // 3 * 2)

solve([1, 1, 0, 2, 0, 1, 0, 1, 1, 1, 2, 2, 0, 2, 2, 0, 0, 2, 0, 1, 2], [2, 2, 0, 1, 0, 1, 1, 2, 1, 0, 2, 0, 1, 1, 0, 2, 2, 0, 1, 2, 0])
solve([0, 0, 1, 2, 1, 2, 1, 1, 2, 2], [2, 0, 2, 2, 1, 2, 1, 1, 1, 0])


Attempt This Online!