Watch 10 video solutions for Minimize Hamming Distance After Swap Operations, a medium level problem involving Array, Depth-First Search, Union Find. This walkthrough by Pepcoding has 3,560 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 Overview: You are given two arrays source and target, plus a list of index pairs that can be swapped any number of times. The task is to minimize the Hamming distance (number of mismatched positions) after performing any valid swaps.
The key observation: if indices are connected through allowed swaps, you can rearrange values freely inside that connected group. The problem reduces to grouping indices and checking how many values can be matched within each group.
Approach 1: Union-Find (Disjoint Set) Approach (O(n α(n) + m) time, O(n) space)
Use a Union-Find structure to group indices connected by swap operations. For every pair (a, b), union their sets so all reachable indices belong to the same component. Once groups are built, collect the values of source for each component and count frequencies using a hash map. Iterate through the same indices in target and reduce counts when matches exist. Any remaining unmatched elements contribute to the Hamming distance. Union-Find is efficient here because it quickly merges components and finds their representative roots.
Approach 2: Breadth-First Search (BFS) on Swap Graph (O(n + m) time, O(n + m) space)
Model the swap pairs as a graph where each index is a node and edges represent allowed swaps. Use BFS (or DFS) to discover connected components. For each component, gather all indices reachable from the starting node. Within that group, build a frequency map of source values and try to match them against target. Decrease counts when matches occur; unmatched values add to the final Hamming distance. This approach works well when you prefer explicit graph traversal over a disjoint-set structure.
Both approaches rely on the same insight: swaps allow arbitrary permutations inside each connected component. Instead of simulating swaps, you treat each component as a bucket of indices and maximize value matches.
Recommended for interviews: The Union-Find solution is the expected approach. It shows you recognize the hidden connected-component structure in swap operations. BFS/DFS demonstrates the same reasoning but with graph traversal. Interviewers typically prefer Union-Find because it scales well and directly models connectivity problems often seen with array index relationships.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Union-Find (Disjoint Set) | O(n α(n) + m) | O(n) | Best general solution when many swap pairs exist and components must be merged efficiently |
| BFS Graph Traversal | O(n + m) | O(n + m) | Useful when treating swaps as an explicit graph and exploring connected components directly |