Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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 != biProblem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Union-Find
[1,2,3,4] [2,1,4,5] [[0,1],[2,3]]
[1,2,3,4] [1,3,2,4] []
[5,1,2,4,3] [1,5,4,2,3] [[0,4],[4,2],[1,3],[1,4]]
smallest-string-with-swaps)make-lexicographically-smallest-array-by-swapping-elements)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1722: Minimize Hamming Distance After Swap Operations
class Solution {
private int[] p;
public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
int n = source.length;
p = new int[n];
for (int i = 0; i < n; i++) {
p[i] = i;
}
for (int[] a : allowedSwaps) {
p[find(a[0])] = find(a[1]);
}
Map<Integer, Map<Integer, Integer>> cnt = new HashMap<>();
for (int i = 0; i < n; ++i) {
int j = find(i);
cnt.computeIfAbsent(j, k -> new HashMap<>()).merge(source[i], 1, Integer::sum);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
int j = find(i);
Map<Integer, Integer> t = cnt.get(j);
if (t.merge(target[i], -1, Integer::sum) < 0) {
++ans;
}
}
return ans;
}
private int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
}
// Accepted solution for LeetCode #1722: Minimize Hamming Distance After Swap Operations
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
}
# Accepted solution for LeetCode #1722: Minimize Hamming Distance After Swap Operations
class Solution:
def minimumHammingDistance(
self, source: List[int], target: List[int], allowedSwaps: List[List[int]]
) -> int:
def find(x: int) -> int:
if p[x] != x:
p[x] = find(p[x])
return p[x]
n = len(source)
p = list(range(n))
for a, b in allowedSwaps:
p[find(a)] = find(b)
cnt = defaultdict(Counter)
for i, x in enumerate(source):
j = find(i)
cnt[j][x] += 1
ans = 0
for i, x in enumerate(target):
j = find(i)
cnt[j][x] -= 1
ans += cnt[j][x] < 0
return ans
// Accepted solution for LeetCode #1722: Minimize Hamming Distance After Swap Operations
struct Solution;
use std::collections::HashMap;
use std::collections::HashSet;
struct UnionFind {
parent: Vec<usize>,
n: usize,
}
impl UnionFind {
fn new(n: usize) -> Self {
let parent = (0..n).collect();
UnionFind { parent, n }
}
fn find(&mut self, i: usize) -> usize {
let j = self.parent[i];
if i == j {
j
} else {
self.parent[i] = self.find(j);
self.parent[i]
}
}
fn union(&mut self, mut i: usize, mut j: usize) {
i = self.find(i);
j = self.find(j);
if i != j {
let min = i.min(j);
self.parent[i] = min;
self.parent[j] = min;
}
}
}
impl Solution {
fn minimum_hamming_distance(
source: Vec<i32>,
target: Vec<i32>,
allowed_swaps: Vec<Vec<i32>>,
) -> i32 {
let n = source.len();
let mut uf = UnionFind::new(n);
for swap in allowed_swaps {
let i = swap[0] as usize;
let j = swap[1] as usize;
uf.union(i, j);
}
let mut source_group: HashMap<usize, HashMap<i32, usize>> = HashMap::new();
let mut target_group: HashMap<usize, HashMap<i32, usize>> = HashMap::new();
let mut groups: HashMap<usize, HashSet<i32>> = HashMap::new();
for i in 0..n {
let g = uf.find(i);
*source_group
.entry(g)
.or_default()
.entry(source[i])
.or_default() += 1;
*target_group
.entry(g)
.or_default()
.entry(target[i])
.or_default() += 1;
groups.entry(g).or_default().insert(source[i]);
groups.entry(g).or_default().insert(target[i]);
}
let mut paired = 0;
for (g, vals) in &groups {
for x in vals {
let s_cnt = source_group[g].get(x).unwrap_or(&0);
let t_cnt = target_group[g].get(x).unwrap_or(&0);
paired += s_cnt.min(t_cnt);
}
}
(n - paired) as i32
}
}
#[test]
fn test() {
let source = vec![1, 2, 3, 4];
let target = vec![2, 1, 4, 5];
let allowed_swaps = vec_vec_i32![[0, 1], [2, 3]];
let res = 1;
assert_eq!(
Solution::minimum_hamming_distance(source, target, allowed_swaps),
res
);
let source = vec![1, 2, 3, 4];
let target = vec![1, 3, 2, 4];
let allowed_swaps = vec_vec_i32![];
let res = 2;
assert_eq!(
Solution::minimum_hamming_distance(source, target, allowed_swaps),
res
);
let source = vec![5, 1, 2, 4, 3];
let target = vec![1, 5, 4, 2, 3];
let allowed_swaps = vec_vec_i32![[0, 4], [4, 2], [1, 3], [1, 4]];
let res = 0;
assert_eq!(
Solution::minimum_hamming_distance(source, target, allowed_swaps),
res
);
}
// Accepted solution for LeetCode #1722: Minimize Hamming Distance After Swap Operations
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;
}
Use this to step through a reusable interview workflow for this problem.
Track components with a list or adjacency matrix. Each union operation may need to update all n elements’ component labels, giving O(n) per union. For n union operations total: O(n²). Find is O(1) with direct lookup, but union dominates.
With path compression and union by rank, each find/union operation takes O(α(n)) amortized time, where α is the inverse Ackermann function — effectively constant. Space is O(n) for the parent and rank arrays. For m operations on n elements: O(m × α(n)) total.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.