Minimize Hamming Distance After Swap Operations solution and explanation
Google
9 more videos on this problem
Minimize Hamming Distance After Swap Operations | Detailed | Simple Steps | Leetcode 1722 | MIKcodestorywithMIK · 37:28 · 8K views
Leetcode 1722. Minimize Hamming Distance After Swap OperationsFraz · 14:25 · 4K views
leetcode 1722 | Minimize Hamming Distance After Swap Operations | Leetcode POTD | DSU | DSACode With Vick · 23:30 · 1K views
1722. Minimize Hamming Distance After Swap Operations | Leetcode Daily - PythonLeetcode Daily · 6:33 · 1K views
LeetCode 1722. Minimize Hamming Distance After Swap OperationsHappy Coding · 16:50 · 1K views
LeetCode 1722. Minimize Hamming Distance After Swap Operations | Visualization | PythonAH Tech · 8:44 · 702 views
Minimize Hamming Distance After Swap Operations | LeetCode 1722 | DSU | Java Code | Developer CoderDeveloper Coder · 21:45 · 634 views
Leetcode 1722. Minimize Hamming Distance After Swap OperationsExpertFunda · 18:36 · 495 views
Minimize Hamming Distance After Swap Operations | LeetCode 1722 - Pythonimpoldev · 15:03 · 491 views
1722. Minimize Hamming Distance After Swap Operations (Leetcode Medium)Programming Live with Larry · 16:17 · 485 views
The problem
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
Approach overview
Problem Overview: You are given two arrays source and target, plus a list of index pairs that can be swapped any number of times. The task is to minimize the Hamming distance (number of mismatched positions) after performing any valid swaps.
The key observation: if indices are connected through allowed swaps, you can rearrange values freely inside that connected group. The problem reduces to grouping indices and checking how many values can be matched within each group.
Approach 1: Union-Find (Disjoint Set) Approach (O(n α(n) + m) time, O(n) space)
Use a Union-Find structure to group indices connected by swap operations. For every pair (a, b), union their sets so all reachable indices belong to the same component. Once groups are built, collect the values of source for each component and count frequencies using a hash map. Iterate through the same indices in target and reduce counts when matches exist. Any remaining unmatched elements contribute to the Hamming distance. Union-Find is efficient here because it quickly merges components and finds their representative roots.
Approach 2: Breadth-First Search (BFS) on Swap Graph (O(n + m) time, O(n + m) space)
Model the swap pairs as a graph where each index is a node and edges represent allowed swaps. Use BFS (or DFS) to discover connected components. For each component, gather all indices reachable from the starting node. Within that group, build a frequency map of source values and try to match them against target. Decrease counts when matches occur; unmatched values add to the final Hamming distance. This approach works well when you prefer explicit graph traversal over a disjoint-set structure.
Both approaches rely on the same insight: swaps allow arbitrary permutations inside each connected component. Instead of simulating swaps, you treat each component as a bucket of indices and maximize value matches.
Recommended for interviews: The Union-Find solution is the expected approach. It shows you recognize the hidden connected-component structure in swap operations. BFS/DFS demonstrates the same reasoning but with graph traversal. Interviewers typically prefer Union-Find because it scales well and directly models connectivity problems often seen with array index relationships.
Approach 1: Union-Find (Disjoint Set) Approach
This approach uses a union-find data structure to group indices in the source array where swaps are allowed. The objective is to find connected components in the index graph defined by allowed swaps. Once we have the components, we can focus on minimizing the Hamming distance within each component by checking if elements at corresponding indices can be rearranged to match the target array.
class UnionFind:
def __init__(self, size):
self.root = list(range(size))
self.rank = [1] * size
def find(self, x):
if self.root[x] == x:
return x
self.root[x] = self.find(self.root[x])
return self.root[x]
def union(self, x, y):
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
if self.rank[rootX] > self.rank[rootY]:
self.root[rootY] = rootX
elif self.rank[rootX] < self.rank[rootY]:
self.root[rootX] = rootY
else:
self.root[rootY] = rootX
self.rank[rootX] += 1
def connected(self, x, y):
return self.find(x) == self.find(y)
from collections import defaultdict
def minimumHammingDistance(source, target, allowedSwaps):
n = len(source)
uf = UnionFind(n)
for a, b in allowedSwaps:
uf.union(a, b)
components = defaultdict(list)
for i in range(n):
root = uf.find(i)
components[root].append(i)
distance = 0
for comp in components.values():
source_count = defaultdict(int)
target_count = defaultdict(int)
for i in comp:
source_count[source[i]] += 1
target_count[target[i]] += 1
for value in source_count:
if value in target_count:
distance += max(0, source_count[value] - target_count[value])
else:
distance += source_count[value]
return distanceimport java.util.*;
class Solution {
class UnionFind {
private int[] root;
private int[] rank;
public UnionFind(int size) {
root = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
root[i] = i;
rank[i] = 1;
}
}
public int find(int x) {
if (root[x] == x) return x;
return root[x] = find(root[x]);
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
root[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
root[rootX] = rootY;
} else {
root[rootY] = rootX;
rank[rootX] += 1;
}
}
}
}
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>> components = new HashMap<>();
for (int i = 0; i < n; i++) {
int root = uf.find(i);
components.computeIfAbsent(root, k -> new ArrayList<>()).add(i);
}
int distance = 0;
for (List<Integer> comp : components.values()) {
Map<Integer, Integer> sourceCount = new HashMap<>();
Map<Integer, Integer> targetCount = new HashMap<>();
for (int i : comp) {
sourceCount.put(source[i], sourceCount.getOrDefault(source[i], 0) + 1);
targetCount.put(target[i], targetCount.getOrDefault(target[i], 0) + 1);
}
for (int key : sourceCount.keySet()) {
if (targetCount.containsKey(key)) {
distance += Math.max(0, sourceCount.get(key) - targetCount.get(key));
} else {
distance += sourceCount.get(key);
}
}
}
return distance;
}
}#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
class UnionFind {
public:
vector<int> root;
vector<int> rank;
UnionFind(int size) {
root.resize(size);
rank.resize(size, 1);
for (int i = 0; i < size; ++i) {
root[i] = i;
}
}
int find(int x) {
if (root[x] == x) return x;
return root[x] = find(root[x]);
}
void unionSet(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
root[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
root[rootX] = rootY;
} else {
root[rootY] = rootX;
rank[rootX] += 1;
}
}
}
};
int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
int n = source.size();
UnionFind uf(n);
for (auto& swap : allowedSwaps) {
uf.unionSet(swap[0], swap[1]);
}
unordered_map<int, vector<int>> components;
for (int i = 0; i < n; ++i) {
int root = uf.find(i);
components[root].push_back(i);
}
int distance = 0;
for (auto& comp : components) {
unordered_map<int, int> sourceCount, targetCount;
for (int i : comp.second) {
sourceCount[source[i]]++;
targetCount[target[i]]++;
}
for (auto& entry : sourceCount) {
int val = entry.first;
int countMismatch = max(0, entry.second - targetCount[val]);
distance += countMismatch;
}
}
return distance;
}#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
int *root;
int *rank;
} UnionFind;
UnionFind* createUnionFind(int size) {
UnionFind* uf = (UnionFind*) malloc(sizeof(UnionFind));
uf->root = (int*) malloc(size * sizeof(int));
uf->rank = (int*) malloc(size * sizeof(int));
for (int i = 0; i < size; ++i) {
uf->root[i] = i;
uf->rank[i] = 1;
}
return uf;
}
int find(UnionFind* uf, int x) {
if (uf->root[x] == x) return x;
return uf->root[x] = find(uf, uf->root[x]);
}
void unionSet(UnionFind* uf, int x, int y) {
int rootX = find(uf, x);
int rootY = find(uf, y);
if (rootX != rootY) {
if (uf->rank[rootX] > uf->rank[rootY]) {
uf->root[rootY] = rootX;
} else if (uf->rank[rootX] < uf->rank[rootY]) {
uf->root[rootX] = rootY;
} else {
uf->root[rootY] = rootX;
uf->rank[rootX] += 1;
}
}
}
int minimumHammingDistance(int* source, int* target, int n, int** allowedSwaps, int swSize, int* swColSize) {
UnionFind* uf = createUnionFind(n);
for (int i = 0; i < swSize; ++i) {
unionSet(uf, allowedSwaps[i][0], allowedSwaps[i][1]);
}
int** components = (int**) malloc(n * sizeof(int*));
int* componentSize = (int*) malloc(n * sizeof(int));
for (int i = 0; i < n; ++i) {
componentSize[i] = 0;
}
for (int i = 0; i < n; ++i) {
int root = find(uf, i);
if (componentSize[root] == 0) {
components[root] = (int*) malloc(n * sizeof(int));
}
components[root][componentSize[root]++] = i;
}
int distance = 0;
for (int i = 0; i < n; ++i) {
if (componentSize[i] > 0) {
int* sourceCount = (int*) malloc(100001 * sizeof(int));
int* targetCount = (int*) malloc(100001 * sizeof(int));
memset(sourceCount, 0, 100001 * sizeof(int));
memset(targetCount, 0, 100001 * sizeof(int));
for (int j = 0; j < componentSize[i]; ++j) {
int idx = components[i][j];
sourceCount[source[idx]]++;
targetCount[target[idx]]++;
}
for (int j = 0; j < 100001; ++j) {
if (sourceCount[j] > targetCount[j]) {
distance += sourceCount[j] - targetCount[j];
}
}
free(sourceCount);
free(targetCount);
free(components[i]);
}
}
free(componentSize);
free(components);
free(uf->root);
free(uf->rank);
free(uf);
return distance;
}The Python solution first initializes a union-find (disjoint set) data structure to manage connection between indices as defined by allowedSwaps. It uses union operations to connect indices and find operations to determine the connected component for each index. After identifying all components, for each component, it checks how elements from the source can match the target, thereby calculating any unmatched elements to determine the minimal Hamming distance.
Time Complexity: O(n log n) due to path compression in union-find
Space Complexity: O(n) to store the parent and rank arrays
Approach 2: Breadth-First Search (BFS) Approach
In this approach, treat each index as a node in a graph and swaps as edges connecting these nodes. Use BFS to traverse and identify connected components of indices in the source array. Once components are identified, adjust the source array to match the target in a minimized Hamming fashion.
from collections import deque, defaultdict
def minimumHammingDistance(source, target, allowedSwaps):
n = len(source)
adj_list = defaultdict(list)
for u, v in allowedSwaps:
adj_list[u].append(v)
adj_list[v].append(u)
visited = [False] * n
min_distance = 0
for start in range(n):
if not visited[start]:
queue = deque([start])
indices = []
while queue:
node = queue.popleft()
if not visited[node]:
visited[node] = True
indices.append(node)
for neighbor in adj_list[node]:
if not visited[neighbor]:
queue.append(neighbor)
source_count = defaultdict(int)
target_count = defaultdict(int)
for index in indices:
source_count[source[index]] += 1
target_count[target[index]] += 1
for val in source_count:
min_distance += max(0, source_count[val] - target_count[val])
return min_distanceThe Python solution represents the allowed swaps as an adjacency list. It uses BFS to find connected components, then compares source and target elements within those components and calculates misalignments to compute the final Hamming distance.
Time Complexity: O(n + e), where e is the number of allowed swaps
Space Complexity: O(n + e) for graph and visited status
Approach 3: Union-Find + Hash Table
We can consider each index as a node, and the element corresponding to each index as the value of the node. Then each element [a_i, b_i] in the given allowedSwaps represents an edge between index a_i and b_i. Therefore, we can use a union-find set to maintain these connected components.
After obtaining each connected component, we use a two-dimensional hash table cnt to count the number of occurrences of each element in each connected component. Finally, for each element in the array target, if its occurrence count in the corresponding connected component is greater than 0, we decrease its count by 1, otherwise, we increase the answer by 1.
The time complexity is O(n times log n) or O(n times \alpha(n)), and the space complexity is O(n). Here, n is the length of the array, and \alpha is the inverse Ackermann function.
function minimumHammingDistance(
source: number[],
target: number[],
allowedSwaps: number[][],
): number {
const n = source.length;
const p: number[] = Array.from({ length: n }, (_, i) => i);
const find = (x: number): number => {
if (p[x] !== x) {
p[x] = find(p[x]);
}
return p[x];
};
for (const [a, b] of allowedSwaps) {
p[find(a)] = find(b);
}
const cnt: Map<number, Map<number, number>> = new Map();
for (let i = 0; i < n; ++i) {
const j = find(i);
if (!cnt.has(j)) {
cnt.set(j, new Map());
}
const m = cnt.get(j)!;
m.set(source[i], (m.get(source[i]) ?? 0) + 1);
}
let ans = 0;
for (let i = 0; i < n; ++i) {
const j = find(i);
const m = cnt.get(j)!;
m.set(target[i], (m.get(target[i]) ?? 0) - 1);
if (m.get(target[i])! < 0) {
++ans;
}
}
return ans;
}func minimumHammingDistance(source []int, target []int, allowedSwaps [][]int) (ans int) {
n := len(source)
p := make([]int, n)
for i := range p {
p[i] = i
}
var find func(int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
for _, a := range allowedSwaps {
p[find(a[0])] = find(a[1])
}
cnt := map[int]map[int]int{}
for i, x := range source {
j := find(i)
if cnt[j] == nil {
cnt[j] = map[int]int{}
}
cnt[j][x]++
}
for i, x := range target {
j := find(i)
cnt[j][x]--
if cnt[j][x] < 0 {
ans++
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Union-Find (Disjoint Set) Approach | Time Complexity: O(n log n) due to path compression in union-find |
| Breadth-First Search (BFS) Approach | Time Complexity: O(n + e), where e is the number of allowed swaps |
| Union-Find + Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Union-Find (Disjoint Set) | O(n α(n) + m) | O(n) | Best general solution when many swap pairs exist and components must be merged efficiently |
| BFS Graph Traversal | O(n + m) | O(n + m) | Useful when treating swaps as an explicit graph and exploring connected components directly |
Frequently asked questions
Is Minimize Hamming Distance After Swap Operations easy or hard?
The problem is classified as Medium difficulty. The implementation is straightforward once you recognize that swap operations create connected components. The challenge lies in identifying that you should group indices and compare value frequencies rather than simulate swaps.
Minimize Hamming Distance After Swap Operations Python/Java solution
The solution builds connected components using Union-Find or BFS, then counts frequencies of source values inside each component. While iterating through target values, matches reduce the frequency counts and unmatched elements increase the Hamming distance. The same logic translates directly to Python, Java, C++, or C with hash maps and a disjoint-set structure.
How to solve Minimize Hamming Distance After Swap Operations in O(n)?
Treat the swap pairs as edges connecting indices and find connected components using Union-Find or BFS. For each component, count frequencies of values from the source array and match them with values in the target array within that same component. Only unmatched elements contribute to the Hamming distance. With efficient Union-Find operations, the runtime is effectively near-linear.
What is the best approach for Minimize Hamming Distance After Swap Operations?
The Union-Find (Disjoint Set) approach is the most efficient and commonly expected solution. It groups indices that can reach each other through swap operations, forming connected components. Within each component, values can be freely rearranged, so you compare frequency counts of source and target values. The complexity is O(n α(n) + m) time with O(n) space.
Is Minimize Hamming Distance After Swap Operations asked at Google/Amazon/Meta?
This type of problem appears in interviews at companies like Google, Amazon, and Meta because it tests understanding of graph connectivity and Union-Find structures. Candidates must recognize that repeated swaps form connected components. Identifying this transformation is the core interview insight.
What data structure is used in Minimize Hamming Distance After Swap Operations?
The primary data structure is Union-Find (Disjoint Set Union) to track connected components of indices. Hash maps are also used to store frequency counts of values within each component. Alternatively, adjacency lists and BFS/DFS can be used to find components in the swap graph.
What is the time complexity of Minimize Hamming Distance After Swap Operations?
The optimal Union-Find solution runs in O(n α(n) + m) time, where n is the array length and m is the number of allowed swaps. The α(n) term comes from the inverse Ackermann function used in path compression. BFS or DFS approaches run in O(n + m) time by explicitly traversing the swap graph.