Description
You are given two integer arrays, source and target, both of length n. You are also given an array allowedSwaps where each allowedSwaps[i] = [ai, bi] indicates that you are allowed to swap the elements at index ai and index bi (0-indexed) of array source. Note that you can swap elements at a specific pair of indices multiple times and in any order.
The Hamming distance of two arrays of the same length, source and target, is the number of positions where the elements are different. Formally, it is the number of indices i for 0 <= i <= n-1 where source[i] != target[i] (0-indexed).
Return the minimum Hamming distance of source and target after performing any amount of swap operations on array source.
Example 1:
Input: source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]] Output: 1 Explanation: source can be transformed the following way: - Swap indices 0 and 1: source = [2,1,3,4] - Swap indices 2 and 3: source = [2,1,4,3] The Hamming distance of source and target is 1 as they differ in 1 position: index 3.
Example 2:
Input: source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = [] Output: 2 Explanation: There are no allowed swaps. The Hamming distance of source and target is 2 as they differ in 2 positions: index 1 and index 2.
Example 3:
Input: source = [5,1,2,4,3], target = [1,5,4,2,3], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]] Output: 0
Constraints:
n == source.length == target.length1 <= n <= 1051 <= source[i], target[i] <= 1050 <= allowedSwaps.length <= 105allowedSwaps[i].length == 20 <= ai, bi <= n - 1ai != bi
Solutions
This code calculates the minimum Hamming distance (number of positions that can't be matched) between two arrays when you're allowed to swap elements. It uses a Union-Find data structure to group indices that can be swapped together—either directly (via allowedSwaps) or transitively through other swaps. For each group of indices, it counts how many times each value appears in the source array at those positions. Then, going through each position in the target array, it checks whether the needed value exists within that position's group (using up one occurrence if found, or incrementing the Hamming distance if not). The result is the total count of positions where the target value can't be obtained through any allowed swaps, which represents the minimum mismatches you can achieve.
/**
* @param {number[]} source
* @param {number[]} target
* @param {number[][]} allowedSwaps
* @return {number}
*/
var minimumHammingDistance = function(source, target, allowedSwaps) {
const n = source.length;
const parent = Array.from({ length: n }, (_, i) => i);
const find = (x) => {
if (parent[x] !== x) {
parent[x] = find(parent[x]);
}
return parent[x];
};
const unite = (a, b) => {
parent[find(a)] = find(b);
};
for (const [a, b] of allowedSwaps) {
unite(a, b);
}
const groups = new Map();
for (let i = 0; i < n; i++) {
const root = find(i);
if (!groups.has(root)) {
groups.set(root, new Map());
}
const freq = groups.get(root);
freq.set(source[i], (freq.get(source[i]) || 0) + 1);
}
let hammingDist = 0;
for (let i = 0; i < n; i++) {
const root = find(i);
const freq = groups.get(root);
if ((freq.get(target[i]) || 0) > 0) {
freq.set(target[i], freq.get(target[i]) - 1);
} else {
hammingDist++;
}
}
return hammingDist;
};