Minimize Hamming Distance After Swap Operations

What the problem is really asking

We are given two arrays, source and target.

Some index pairs are swappable. The important detail is that swaps can be done any number of times and in any order.

So if index 0 can swap with 1, and index 1 can swap with 4, then indices 0, 1, and 4 form one connected group. Inside that group, values from source can be rearranged freely.

The goal is to minimize how many positions still differ from target.

Key insight

This is not really a swap simulation problem.

It is a connected components problem.

Every connected component of indices behaves like one bucket:

• the values from source inside that component can be permuted however we want
• values cannot move from one component to another
• for each component, we only care about matching frequencies

So for each component, count the values available in source. Then scan target. If the component still has the needed value, use it. Otherwise, this index must contribute 1 to the Hamming distance.

Approach

Use Union Find.

1. Create one DSU node for every index.
2. Union every pair from allowedSwaps.
3. For every index i, find its component root and count source[i] inside that root.
4. Scan target.
5. For every index i, check whether its component has one unused target[i].
6. If yes, consume that value.
7. If no, increase the answer.

import java.util.HashMap;
import java.util.Map;

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;
        }

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

        Map<Integer, Map<Integer, Integer>> counts = new HashMap<>();

        for (int i = 0; i < n; i++) {
            int root = find(i);
            counts.putIfAbsent(root, new HashMap<>());
            Map<Integer, Integer> freq = counts.get(root);
            freq.put(source[i], freq.getOrDefault(source[i], 0) + 1);
        }

        int answer = 0;

        for (int i = 0; i < n; i++) {
            int root = find(i);
            Map<Integer, Integer> freq = counts.get(root);
            int available = freq.getOrDefault(target[i], 0);

            if (available > 0) {
                freq.put(target[i], available - 1);
            } else {
                answer++;
            }
        }

        return answer;
    }

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

        return parent[node];
    }

    private void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);

        if (rootA == rootB) {
            return;
        }

        if (rank[rootA] < rank[rootB]) {
            parent[rootA] = rootB;
        } else if (rank[rootA] > rank[rootB]) {
            parent[rootB] = rootA;
        } else {
            parent[rootB] = rootA;
            rank[rootA]++;
        }
    }
}

Dry run

Take:

source = [1, 2, 3, 4]
target = [2, 1, 4, 5]
allowedSwaps = [[0, 1], [2, 3]]

The allowed swaps create two components:

• component A: indices 0, 1
• component B: indices 2, 3

For component A:

• source values are {1, 2}
• target wants {2, 1}
• both can be matched

For component B:

• source values are {3, 4}
• target wants {4, 5}
• 4 can be matched
• 5 cannot be matched

So the minimum Hamming distance is 1.

Why Union Find fits perfectly

Allowed swaps are edges between indices.

If two indices are connected by a path, we can move values across that path using repeated swaps. That means the exact edge order does not matter after we build the connected components.

Union Find gives us those components efficiently, even when n and allowedSwaps.length are both up to 100000.

Common mistakes

1. Simulating the swaps

There can be too many possible swap sequences. We only need to know which indices are connected.

2. Comparing whole-array frequencies

Overall frequencies are not enough. Values can only move inside their own connected component.

3. Forgetting duplicate values

Each matched value can be used only once. That is why we decrement the frequency after matching a target value.

Complexity

Let n be the length of the arrays and m be the number of allowed swaps.

Time Complexity: O((n + m) * alpha(n))

Here alpha(n) is the inverse Ackermann function from DSU operations, which is effectively constant in practice.

Space Complexity: O(n)

We store the DSU arrays and the frequency counts for component values.