Minimize Hamming Distance After Swap Operations — Solution
Minimize Hamming Distance After Swap Operations solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimize Hamming Distance After Swap Operations is a medium coding problem on arrays, depth-first search and union find, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Depth-First Search, Union Find
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given two integer arrays source and target of the same length n, and a list allowedSwaps where allowedSwaps[i] = [ai, bi] lets you swap the elements at indices ai and bi of source. Each allowed swap may be used any number of times, in any order.
The Hamming distance of two equal-length arrays is the number of indices i where they differ.
Return the smallest Hamming distance between source and target you can reach after performing any sequence of allowed swaps on source.
Example 1
Input: source = [5,1,2,4], target = [1,5,4,3], allowedSwaps = [[0,1],[2,3]]
Output: 1
Explanation: Swap indices 0, 1 and then 2, 3 to get `[1,5,4,2]`; only index 3 still differs.
Example 2
Input: source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = []
Output: 2
Example 3
Input: source = [3,1,2,2,5], target = [2,3,5,2,1], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]]
Output: 0
Explanation: All indices are linked, so `source` can be rearranged freely into `target`.
Constraints
n == source.length == target.length1 <= n <= 10^51 <= source[i], target[i] <= 10^50 <= allowedSwaps.length <= 10^5allowedSwaps[i].length == 20 <= ai, bi <= n - 1ai != bi
Hints for Minimize Hamming Distance After Swap Operations
Hint 1
If index a can swap with b, and b with c, then the values at a, b and c can be arranged in any order.
Hint 2
So the swaps split the indices into groups (connected components); inside a group the values of
sourcecan be permuted freely.Hint 3
Per group, count how many values of
sourcecan be matched with equal values oftargetat the group's indices; everything unmatched adds to the distance.
How to solve Minimize Hamming Distance After Swap Operations
Allowed swaps connect indices; within a connected group any permutation is reachable, so each group contributes size − (multiset overlap of its source and target values).
Approach
- Union the two indices of every allowed swap in a union-find.
- For each index
i, add the pair(root(i), source[i])to a counter. - For each index
i, look up(root(i), target[i]): if the counter is positive, decrement it (a match); otherwise the index will stay different, so add 1 to the answer.
Why it works
Transpositions along the edges of a connected graph generate every permutation of its vertices, so inside a component the source values can be placed anywhere. The best placement then matches as many target values as the two multisets have in common, which the greedy counter computes exactly; components are independent of each other.
Complexity
- Time —
O((n + s) · α(n)) - Space —
O(n)
Pitfalls
- Swaps are transitive — handling each listed pair in isolation undercounts what can be rearranged.
- Key the counter by component and value; a value matching in a different component does not count.
allowedSwapsmay be empty: then the answer is the plain Hamming distance.
Reference solution
Python
from typing import List
from collections import Counter
def minimumHammingDistance(source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:
n = len(source)
root = list(range(n))
def find(x):
while root[x] != x:
root[x] = root[root[x]]
x = root[x]
return x
for a, b in allowedSwaps:
ra, rb = find(a), find(b)
if ra != rb:
root[ra] = rb
count = Counter()
for i in range(n):
count[(find(i), source[i])] += 1
dist = 0
for i in range(n):
key = (find(i), target[i])
if count[key] > 0:
count[key] -= 1
else:
dist += 1
return distJava
public static int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
int n = source.length;
int[] root = new int[n];
for (int i = 0; i < n; i++) root[i] = i;
for (int[] s : allowedSwaps) {
int ra = mhFind(root, s[0]), rb = mhFind(root, s[1]);
if (ra != rb) root[ra] = rb;
}
Map<Long, Integer> count = new HashMap<>();
for (int i = 0; i < n; i++) count.merge((long) mhFind(root, i) * 100001L + source[i], 1, Integer::sum);
int dist = 0;
for (int i = 0; i < n; i++) {
long key = (long) mhFind(root, i) * 100001L + target[i];
Integer c = count.get(key);
if (c != null && c > 0) count.put(key, c - 1);
else dist++;
}
return dist;
}
static int mhFind(int[] root, int x) {
while (root[x] != x) { root[x] = root[root[x]]; x = root[x]; }
return x;
}C++
static int mhFind(vector<int>& root, int x) {
while (root[x] != x) { root[x] = root[root[x]]; x = root[x]; }
return x;
}
int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
int n = source.size();
vector<int> root(n);
for (int i = 0; i < n; i++) root[i] = i;
for (auto& s : allowedSwaps) {
int ra = mhFind(root, s[0]), rb = mhFind(root, s[1]);
if (ra != rb) root[ra] = rb;
}
unordered_map<long long, int> count;
for (int i = 0; i < n; i++) count[(long long)mhFind(root, i) * 100001LL + source[i]]++;
int dist = 0;
for (int i = 0; i < n; i++) {
long long key = (long long)mhFind(root, i) * 100001LL + target[i];
auto it = count.find(key);
if (it != count.end() && it->second > 0) it->second--;
else dist++;
}
return dist;
}JavaScript
var minimumHammingDistance = function(source, target, allowedSwaps) {
var n = source.length;
var root = [];
for (var i = 0; i < n; i++) root.push(i);
var find = function(x) {
while (root[x] !== x) { root[x] = root[root[x]]; x = root[x]; }
return x;
};
for (var s = 0; s < allowedSwaps.length; s++) {
var ra = find(allowedSwaps[s][0]), rb = find(allowedSwaps[s][1]);
if (ra !== rb) root[ra] = rb;
}
var count = new Map();
for (var j = 0; j < n; j++) {
var key = find(j) * 100001 + source[j];
count.set(key, (count.get(key) || 0) + 1);
}
var dist = 0;
for (var k = 0; k < n; k++) {
var key2 = find(k) * 100001 + target[k];
var c = count.get(key2) || 0;
if (c > 0) count.set(key2, c - 1);
else dist++;
}
return dist;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Depth-First Search (DFS)