1722. Minimize Hamming Distance After Swap Operations

Array
Union Find
Hash Table

TIME

O(n * α(n))

SPACE

O(n)

Intuition

If indices can swap (directly or transitively), elements at those indices can be freely rearranged. Use Union-Find to identify connected components of indices.

Solution

Union-Find: Build connected components from allowedSwaps
Group by component: Collect source and target values for each component
Match greedily: For each component, count how many target values exist in source values

# Union-Find to group swappable indices
for a, b in allowedSwaps:
    union(a, b)

# Group indices by root
groups = defaultdict(list)
for i in range(n):
    groups[find(i)].append(i)

# For each group, count unmatched positions
hamming = 0
for indices in groups.values():
    source_count = Counter(source[i] for i in indices)
    for i in indices:
        if source_count[target[i]] > 0:
            source_count[target[i]] -= 1
        else:
            hamming += 1

Why This Works

Connected indices form a group where any permutation is achievable
For each group, we optimally match source values to target values
Unmatched positions contribute to Hamming distance

Complexity

Time: O(n × α(n)) where α is inverse Ackermann (near-constant)
Space: O(n)

Edge Cases

No allowed swaps → count mismatches directly
All indices connected → full flexibility
Duplicate values in arrays

Code

from typing import List
from collections import defaultdict, Counter


class Solution:
    def minimumHammingDistance(
        self, source: List[int], target: List[int], allowedSwaps: List[List[int]]
    ) -> int:
        """
        1722. Minimize Hamming Distance After Swap Operations
        Time: O(n * α(n))
        Space: O(n)
        """
        n = len(source)
        parent = list(range(n))
        rank = [0] * n

        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x: int, y: int) -> None:
            px, py = find(x), find(y)
            if px == py:
                return
            if rank[px] < rank[py]:
                px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]:
                rank[px] += 1

        # Build connected components
        for a, b in allowedSwaps:
            union(a, b)

        # Group indices by root
        groups = defaultdict(list)
        for i in range(n):
            groups[find(i)].append(i)

        # Count unmatched positions
        hamming = 0
        for indices in groups.values():
            source_count = Counter(source[i] for i in indices)
            for i in indices:
                if source_count[target[i]] > 0:
                    source_count[target[i]] -= 1
                else:
                    hamming += 1

        return hamming

import java.util.*;

/**
 * 1722. Minimize Hamming Distance After Swap Operations
 * Time: O(n * α(n))
 * Space: O(n)
 */
class Solution {
    private int[] parent;
    private int[] rank;

    public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
        int n = source.length;
        parent = new int[n];
        rank = new int[n];

        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }

        // Build connected components
        for (int[] swap : allowedSwaps) {
            union(swap[0], swap[1]);
        }

        // Group indices by root
        Map<Integer, List<Integer>> groups = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int root = find(i);
            groups.computeIfAbsent(root, k -> new ArrayList<>()).add(i);
        }

        // Count unmatched positions
        int hamming = 0;
        for (List<Integer> indices : groups.values()) {
            Map<Integer, Integer> sourceCount = new HashMap<>();
            for (int i : indices) {
                sourceCount.merge(source[i], 1, Integer::sum);
            }

            for (int i : indices) {
                int t = target[i];
                if (sourceCount.getOrDefault(t, 0) > 0) {
                    sourceCount.put(t, sourceCount.get(t) - 1);
                } else {
                    hamming++;
                }
            }
        }

        return hamming;
    }

    private int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    private void union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return;

        if (rank[px] < rank[py]) {
            int temp = px;
            px = py;
            py = temp;
        }
        parent[py] = px;
        if (rank[px] == rank[py]) {
            rank[px]++;
        }
    }
}