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.
This approach uses a union-find data structure to group indices in the source array where swaps are allowed. The objective is to find connected components in the index graph defined by allowed swaps. Once we have the components, we can focus on minimizing the Hamming distance within each component by checking if elements at corresponding indices can be rearranged to match the target array.
The Python solution first initializes a union-find (disjoint set) data structure to manage connection between indices as defined by allowedSwaps. It uses union operations to connect indices and find operations to determine the connected component for each index. After identifying all components, for each component, it checks how elements from the source can match the target, thereby calculating any unmatched elements to determine the minimal Hamming distance.
Time Complexity: O(n log n) due to path compression in union-find
Space Complexity: O(n) to store the parent and rank arrays
In this approach, treat each index as a node in a graph and swaps as edges connecting these nodes. Use BFS to traverse and identify connected components of indices in the source array. Once components are identified, adjust the source array to match the target in a minimized Hamming fashion.
The Python solution represents the allowed swaps as an adjacency list. It uses BFS to find connected components, then compares source and target elements within those components and calculates misalignments to compute the final Hamming distance.
Python
Time Complexity: O(n + e), where e is the number of allowed swaps
Space Complexity: O(n + e) for graph and visited status
We can consider each index as a node, and the element corresponding to each index as the value of the node. Then each element [a_i, b_i] in the given allowedSwaps represents an edge between index a_i and b_i. Therefore, we can use a union-find set to maintain these connected components.
After obtaining each connected component, we use a two-dimensional hash table cnt to count the number of occurrences of each element in each connected component. Finally, for each element in the array target, if its occurrence count in the corresponding connected component is greater than 0, we decrease its count by 1, otherwise, we increase the answer by 1.
The time complexity is O(n times log n) or O(n times \alpha(n)), and the space complexity is O(n). Here, n is the length of the array, and \alpha is the inverse Ackermann function.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Union-Find (Disjoint Set) Approach | Time Complexity: O(n log n) due to path compression in union-find |
| Breadth-First Search (BFS) Approach | Time Complexity: O(n + e), where e is the number of allowed swaps |
| Union-Find + Hash Table | — |
| 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 |
Minimize Hamming Distance After Swap Operations || Leetcode • Pepcoding • 3,560 views views
Watch 9 more video solutions →Practice Minimize Hamming Distance After Swap Operations with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor