1722. Minimize Hamming Distance After Swap Operations

Intuition

Elements that can be swapped freely (via allowed swaps) form connected components. Within each component, any arrangement is possible. For each target[i], check if source has a matching value in the same component.

Algorithm

1Build Union-Find from allowedSwaps. Group all source[i] values by their component root.
2For each target[i]: look up its component root and check if that value exists in the component's frequency map. If yes: consume one count. If no: increment Hamming distance.

Common Pitfalls

•Union-Find with path compression + union by rank. O((n + k) α(n)) time. Consuming from frequency map prevents double-matching.

1722.cs

public class Solution
{
    public int MinimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps)
    {
        int n = source.Length;
        int ans = 0;
        UnionFind uf = new UnionFind(n);
        Dictionary<int, int>[] groupIdToCount = new Dictionary<int, int>[n];

        for (int i = 0; i < n; ++i)
            groupIdToCount[i] = new Dictionary<int, int>();

        foreach (var allowedSwap in allowedSwaps)
        {
            int a = allowedSwap[0];
            int b = allowedSwap[1];
            uf.UnionByRank(a, b);
        }

        for (int i = 0; i < n; ++i)
        {
            int groupId = uf.Find(i);
            if (!groupIdToCount[groupId].ContainsKey(source[i]))
                groupIdToCount[groupId][source[i]] = 0;
            groupIdToCount[groupId][source[i]]++;
        }

        for (int i = 0; i < n; ++i)
        {
            int groupId = uf.Find(i);
            var count = groupIdToCount[groupId];
            if (!count.ContainsKey(target[i]))
                ans++;
            else
            {
                count[target[i]]--;
                if (count[target[i]] == 0)
                    count.Remove(target[i]);
            }
        }

        return ans;
    }
}

class UnionFind
{
    private int[] id;
    private int[] rank;

    public UnionFind(int n)
    {
        id = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; ++i)
            id[i] = i;
    }

    public void UnionByRank(int u, int v)
    {
        int i = Find(u);
        int j = Find(v);
        if (i == j)
            return;
        if (rank[i] < rank[j])
            id[i] = j;
        else if (rank[i] > rank[j])
            id[j] = i;
        else
        {
            id[i] = j;
            ++rank[j];
        }
    }

    public int Find(int u)
    {
        if (id[u] == u) 
            return u;
        return id[u] = Find(id[u]);
    }
}

Was this solution helpful?