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 != biThis 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.
Java
C++
C
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.
Time Complexity: O(n + e), where e is the number of allowed swaps
Space Complexity: O(n + e) for graph and visited status
| 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 |
Minimize Hamming Distance After Swap Operations || Leetcode • Pepcoding • 3,375 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