# Minimize Hamming Distance After Swap Operations
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimize-hamming-distance-after-swap-operations)
Canonical: https://scaleengineer.com/dsa/problems/minimize-hamming-distance-after-swap-operations
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array
---
## 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.length`
* `1 <= n <= 105`
* `1 <= source[i], target[i] <= 105`
* `0 <= allowedSwaps.length <= 105`
* `allowedSwaps[i].length == 2`
* `0 <= ai, bi <= n - 1`
* `ai != bi`

# Approaches
## Graph Traversal using DFS/BFS
This approach models the problem as a graph problem. The indices of the array `0, 1, ..., n-1` are the vertices of the graph. An edge exists between two indices `u` and `v` if a swap `[u, v]` is allowed. The `allowedSwaps` array defines the edges.
The key insight is that any two indices in the same connected component are mutually swappable. This is because if `u` can be swapped with `v`, and `v` with `w`, you can move the element from `u` to `v`, then the original element at `v` to `w`, and so on. This means within a connected component of indices, we can arrange the `source` elements at those indices in any permutation we like.
To minimize the Hamming distance, for each connected component, we should arrange the `source` elements to match the `target` elements as much as possible. The maximum number of matches we can achieve in a component is limited by the multiset of numbers available from `source` at those indices.
**Time:** `O(n + S)`, where `n` is the length of the arrays and `S` is the number of allowed swaps. Building the adjacency list takes `O(S)`. The graph traversal visits each vertex and edge once, taking `O(n + S)`. Processing each component involves creating frequency maps and counting matches, which takes time proportional to the component's size. Summed over all components, this is `O(n)`. · **Space:** `O(n + S)`. The adjacency list requires `O(S)` space. The `visited` array, recursion stack for DFS (or queue for BFS), and the data structures for storing component indices and frequency counts can take up to `O(n)` space in the worst case.
**Pros:** It's a direct and intuitive application of graph traversal algorithms.; The logic is relatively easy to follow if you are familiar with DFS or BFS.
**Cons:** The space complexity depends on the number of swaps `S`, which can be large.; It might be slightly less performant than a DSU-based solution due to the overhead of building an explicit graph and managing recursion/queues.
### Explanation
The algorithm proceeds by first identifying these connected components using a standard graph traversal algorithm like Depth-First Search (DFS) or Breadth-First Search (BFS).
1.  **Build Graph:** Construct an adjacency list representation of the graph. For each pair `[u, v]` in `allowedSwaps`, add an edge between `u` and `v`.
2.  **Traverse and Process Components:** Iterate through each index from `0` to `n-1`. If an index hasn't been visited yet, it marks the start of a new connected component.
3.  **Find Component:** Start a traversal (e.g., DFS) from the unvisited index to find all indices belonging to its connected component. Keep track of visited indices to avoid processing them again.
4.  **Count Matches:** For each discovered component:
    a.  Collect all `source` values at the component's indices into a frequency map (e.g., a `HashMap`). This map tells us which numbers are available and how many of each.
    b.  Iterate through the component's indices again. For each index `j`, look at the required value `target[j]`. If this value is present in our frequency map (i.e., its count is greater than 0), we can make a match. We increment our total match count and decrement the frequency of that value in the map to signify it has been used.
5.  **Calculate Distance:** After iterating through all indices and processing all components, the total number of matches is found. The minimum Hamming distance is the total number of elements `n` minus the total number of matches.
```java
class Solution {
    public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
        int n = source.length;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] swap : allowedSwaps) {
            adj.get(swap[0]).add(swap[1]);
            adj.get(swap[1]).add(swap[0]);
        }

        boolean[] visited = new boolean[n];
        int matches = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                List<Integer> componentIndices = new ArrayList<>();
                dfs(i, adj, visited, componentIndices);
                
                Map<Integer, Integer> sourceCounts = new HashMap<>();
                for (int index : componentIndices) {
                    sourceCounts.put(source[index], sourceCounts.getOrDefault(source[index], 0) + 1);
                }

                for (int index : componentIndices) {
                    if (sourceCounts.getOrDefault(target[index], 0) > 0) {
                        matches++;
                        sourceCounts.put(target[index], sourceCounts.get(target[index]) - 1);
                    }
                }
            }
        }

        return n - matches;
    }

    private void dfs(int u, List<List<Integer>> adj, boolean[] visited, List<Integer> component) {
        visited[u] = true;
        component.add(u);
        for (int v : adj.get(u)) {
            if (!visited[v]) {
                dfs(v, adj, visited, component);
            }
        }
    }
}
```
### Algorithm
- Build an adjacency list for a graph with `n` vertices from the `allowedSwaps`.
- Initialize a `visited` array of size `n` to `false`.
- Initialize `total_matches = 0`.
- Loop from `i = 0` to `n-1`:
    - If `i` is not visited:
        - Start a DFS/BFS from `i` to find all indices in the connected component.
        - Store these indices in a list `component_indices`.
        - Create a frequency map `source_counts` of `source` values for indices in `component_indices`.
        - For each `index` in `component_indices`:
            - If `target[index]` is in `source_counts` with a positive count:
                - Increment `total_matches`.
                - Decrement the count of `target[index]` in `source_counts`.
- Return `n - total_matches`.

## Disjoint Set Union (DSU)
A more optimized approach uses the Disjoint Set Union (DSU) data structure, also known as Union-Find. This data structure is highly efficient for problems involving partitioning a set of elements into a number of disjoint, non-overlapping sets. In our case, the elements are the indices `0, 1, ..., n-1`, and we want to group them into sets where indices within the same set are mutually swappable.
The DSU data structure provides two main operations: `find`, which determines the set an element belongs to (by returning a representative or "root" element), and `union`, which merges two sets.
**Time:** `O((n + S) * α(n))`, where `α(n)` is the extremely slow-growing inverse Ackermann function. For all practical purposes, `α(n)` is a small constant (less than 5). Thus, the complexity is nearly linear, `O(n + S)`. The DSU operations take `O(S * α(n))`, and the loops for processing values take `O(n * α(n))`. · **Space:** `O(n)`. The DSU structure itself (parent and rank arrays) takes `O(n)` space. The map `componentSourceCounts` will store `n` values distributed among different component frequency maps, so its total size is also `O(n)`. This is an improvement over the graph traversal approach, which requires `O(n + S)` space.
**Pros:** Highly efficient in both time and space.; The space complexity is independent of the number of swaps `S`.; Often faster in practice due to optimized `find` and `union` operations and better memory locality.
**Cons:** Requires knowledge of the Disjoint Set Union data structure, which is more specialized than basic graph traversals.
### Explanation
The algorithm uses DSU to efficiently group the indices and then calculates the matches within each group.
1.  **Initialize DSU:** Create a DSU structure for `n` indices. Initially, each index is in its own set.
2.  **Build Sets:** Iterate through the `allowedSwaps`. For each swap `[u, v]`, call `dsu.union(u, v)`. This merges the sets containing `u` and `v`. After this step, all indices that belong to the same connected component will be in the same set in the DSU structure.
3.  **Group Values by Component:** We need to know the multiset of `source` values available in each component. We can use a `Map` where keys are the root of each component and values are frequency maps of the `source` numbers in that component. We iterate from `i = 0` to `n-1`, find the root of `i`'s component using `dsu.find(i)`, and update the frequency map for that root with `source[i]`.
4.  **Count Matches:** Initialize `matches = 0`. Iterate again from `i = 0` to `n-1`. For each index `i`, find its component's root `r = dsu.find(i)`. Check the `target[i]` value against the frequency map of `source` values for component `r`. If `target[i]` is available (count > 0), we've found a match. Increment `matches` and decrement the count of `target[i]` in the map.
5.  **Calculate Distance:** The minimum Hamming distance is `n - matches`.
This method avoids explicitly building a graph and storing component indices in lists, making it more space-efficient.
```java
class DSU {
    private int[] parent;
    private int[] rank;

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

    public int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        return parent[i] = find(parent[i]); // Path compression
    }

    public void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            // Union by rank
            if (rank[rootI] > rank[rootJ]) {
                parent[rootJ] = rootI;
            } else if (rank[rootI] < rank[rootJ]) {
                parent[rootI] = rootJ;
            } else {
                parent[rootJ] = rootI;
                rank[rootI]++;
            }
        }
    }
}

class Solution {
    public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
        int n = source.length;
        DSU dsu = new DSU(n);
        for (int[] swap : allowedSwaps) {
            dsu.union(swap[0], swap[1]);
        }

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

        int matches = 0;
        for (int i = 0; i < n; i++) {
            int root = dsu.find(i);
            Map<Integer, Integer> counts = componentSourceCounts.get(root);
            if (counts.getOrDefault(target[i], 0) > 0) {
                matches++;
                counts.put(target[i], counts.get(target[i]) - 1);
            }
        }

        return n - matches;
    }
}
```
### Algorithm
- Initialize a DSU structure with `n` elements.
- For each swap `[u, v]` in `allowedSwaps`, perform `dsu.union(u, v)`.
- Create a map `componentSourceCounts` to store frequency maps of `source` values for each component.
- Loop from `i = 0` to `n-1`:
    - Find the root `r = dsu.find(i)`.
    - Increment the count of `source[i]` in the frequency map corresponding to root `r`.
- Initialize `matches = 0`.
- Loop from `i = 0` to `n-1`:
    - Find the root `r = dsu.find(i)`.
    - Get the frequency map for root `r`.
    - If the count for `target[i]` in this map is positive:
        - Increment `matches`.
        - Decrement the count of `target[i]` in the map.
- Return `n - matches`.

# Solutions
### Java

```java
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 ]; } }
```

### CPP

```cpp
class Solution { public: int minimumHammingDistance ( vector < int >& source , vector < int >& target , vector < vector < int >>& allowedSwaps ) { int n = source . size (); vector < int > p ( n ); iota ( p . begin (), p . end (), 0 ); function < int ( int ) > find = [ & ]( int x ) { return x == p [ x ] ? x : p [ x ] = find ( p [ x ]); }; for ( auto & a : allowedSwaps ) { p [ find ( a [ 0 ])] = find ( a [ 1 ]); } unordered_map < int , unordered_map < int , int >> cnt ; for ( int i = 0 ; i < n ; ++ i ) { ++ cnt [ find ( i )][ source [ i ]]; } int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { if ( -- cnt [ find ( i )][ target [ i ]] < 0 ) { ++ ans ; } } return ans ; } };
```

### Python

```python
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
```