You are given three things:
sourcetarget of the same length as sourceallowedSwaps where each element is a pair of indices [i, j] indicating you are allowed to swap source[i] with source[j] any number of timessource such that the Hamming distance between source and target is minimized. The Hamming distance is the number of positions i where source[i] != target[i].
allowedSwaps)allowedSwaps
At first glance, one might consider trying all permutations of source using allowed swaps, but this quickly becomes infeasible for large arrays due to the factorial number of possibilities.
However, a key insight is that swaps are only allowed between certain indices, forming groups of indices that can be freely permuted among themselves. If two indices are connected (directly or indirectly) via allowed swaps, their values can be rearranged in any order within that group.
Therefore, the problem can be broken down into:
source values to best match the target values at those same indicesLet's break down the solution step by step:
allowedSwaps, each group represents a set of indices whose values can be rearranged freely among themselves.source and target at those indices (using hash maps or arrays).source and in target.
Sample Input:
source = [1,2,3,4]
target = [2,1,4,5]
allowedSwaps = [[0,1],[2,3]]
Step 1: Find Connected Components
- [0,1] means indices 0 and 1 are connected.
- [2,3] means indices 2 and 3 are connected.
- So, there are two components: {0,1} and {2,3}.
Step 2: For Each Component, Compare Source and Target
- For {0,1}:
source = [1,2]target = [2,1]source to match target exactly (swap 1 and 2), so 0 mismatches here.source = [3,4]target = [4,5]
Brute-force Approach:
- Try all permutations of source within allowed swaps: This is factorial time in the size of each component, which is infeasible.
Optimized Approach:
- Union-Find: Each union and find operation is almost O(1) (amortized), so for N elements and M swaps: O(N + M).
- Grouping and Counting: For each index, we process it a constant number of times: O(N).
- Total: O(N + M), where N is length of source and M is number of allowed swaps.
- Space Complexity: O(N) for Union-Find, O(N) for hash maps.
This is efficient and scalable for large arrays.
The key insight is to decompose the array into connected groups based on allowed swaps, then optimally match values within each group to minimize mismatches. By using Union-Find to identify these groups and hash maps to count and match values, we reduce a potentially exponential problem to linear time. This approach is elegant because it leverages the structure of the problem and avoids unnecessary computation.
from collections import defaultdict, Counter
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]]
x = self.parent[x]
return x
def union(self, x, y):
self.parent[self.find(x)] = self.find(y)
class Solution:
def minimumHammingDistance(self, source, target, allowedSwaps):
n = len(source)
uf = UnionFind(n)
for i, j in allowedSwaps:
uf.union(i, j)
groups = defaultdict(list)
for i in range(n):
groups[uf.find(i)].append(i)
res = 0
for indices in groups.values():
src_counter = Counter([source[i] for i in indices])
tgt_counter = Counter([target[i] for i in indices])
# Number of matches is sum of min counts for each value
matches = 0
for val in src_counter:
matches += min(src_counter[val], tgt_counter.get(val, 0))
res += len(indices) - matches
return res
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
using namespace std;
class UnionFind {
public:
vector<int> parent;
UnionFind(int n) : parent(n) {
for (int i = 0; i < n; ++i) parent[i] = i;
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
void unite(int x, int y) {
parent[find(x)] = find(y);
}
};
class Solution {
public:
int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
int n = source.size();
UnionFind uf(n);
for (auto& swap : allowedSwaps) {
uf.unite(swap[0], swap[1]);
}
unordered_map<int, vector<int>> groups;
for (int i = 0; i < n; ++i) {
groups[uf.find(i)].push_back(i);
}
int res = 0;
for (auto& [root, indices] : groups) {
unordered_map<int, int> src_count, tgt_count;
for (int idx : indices) {
src_count[source[idx]]++;
tgt_count[target[idx]]++;
}
int matches = 0;
for (auto& [val, cnt] : src_count) {
matches += min(cnt, tgt_count[val]);
}
res += indices.size() - matches;
}
return res;
}
};
import java.util.*;
class UnionFind {
int[] parent;
public UnionFind(int n) {
parent = new int[n];
for (int i = 0; i < n; ++i) parent[i] = i;
}
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public void union(int x, int y) {
parent[find(x)] = find(y);
}
}
class Solution {
public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
int n = source.length;
UnionFind uf = new UnionFind(n);
for (int[] swap : allowedSwaps) {
uf.union(swap[0], swap[1]);
}
Map<Integer, List<Integer>> groups = new HashMap<>();
for (int i = 0; i < n; ++i) {
int root = uf.find(i);
groups.computeIfAbsent(root, k -> new ArrayList<>()).add(i);
}
int res = 0;
for (List<Integer> indices : groups.values()) {
Map<Integer, Integer> srcCount = new HashMap<>();
Map<Integer, Integer> tgtCount = new HashMap<>();
for (int idx : indices) {
srcCount.put(source[idx], srcCount.getOrDefault(source[idx], 0) + 1);
tgtCount.put(target[idx], tgtCount.getOrDefault(target[idx], 0) + 1);
}
int matches = 0;
for (int val : srcCount.keySet()) {
matches += Math.min(srcCount.get(val), tgtCount.getOrDefault(val, 0));
}
res += indices.size() - matches;
}
return res;
}
}
class UnionFind {
constructor(n) {
this.parent = Array(n).fill(0).map((_, i) => i);
}
find(x) {
if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
return this.parent[x];
}
union(x, y) {
this.parent[this.find(x)] = this.find(y);
}
}
var minimumHammingDistance = function(source, target, allowedSwaps) {
const n = source.length;
const uf = new UnionFind(n);
for (const [i, j] of allowedSwaps) {
uf.union(i, j);
}
const groups = {};
for (let i = 0; i < n; ++i) {
const root = uf.find(i);
if (!(root in groups)) groups[root] = [];
groups[root].push(i);
}
let res = 0;
for (const indices of Object.values(groups)) {
const srcCount = new Map();
const tgtCount = new Map();
for (const idx of indices) {
srcCount.set(source[idx], (srcCount.get(source[idx]) || 0) + 1);
tgtCount.set(target[idx], (tgtCount.get(target[idx]) || 0) + 1);
}
let matches = 0;
for (const [val, cnt] of srcCount.entries()) {
matches += Math.min(cnt, tgtCount.get(val) || 0);
}
res += indices.length - matches;
}
return res;
};