LeetCode 1722: Minimize Hamming Distance After Swap Operations
Problem Description
Explanation
To solve this problem, we can create disjoint sets for each connected component formed by the allowed swaps. Then, for each element in the source array, we check if it belongs to the same connected component as its corresponding element in the target array. If they belong to the same connected component, we decrement the count of differences between the arrays.
- Create a disjoint set data structure to keep track of connected components.
- Union all the pairs in allowedSwaps to form connected components.
- For each element in source and target arrays, check if they belong to the same connected component.
- Calculate the Hamming distance by counting the positions where the elements are different.
Time Complexity: O(n * alpha(n)) where n is the length of the arrays and alpha(n) is the inverse Ackermann function (almost constant). Space Complexity: O(n) for the disjoint set data structure.
Solutions
class Solution {
public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
int n = source.length;
int[] parent = new int[n];
Arrays.fill(parent, -1);
for (int[] swap : allowedSwaps) {
int root1 = find(parent, swap[0]);
int root2 = find(parent, swap[1]);
if (root1 != root2) {
parent[root1] = root2;
}
}
Map<Integer, Map<Integer, Integer>> groups = new HashMap<>();
for (int i = 0; i < n; i++) {
int root = find(parent, i);
groups.computeIfAbsent(root, k -> new HashMap<>()).merge(source[i], 1, Integer::sum);
}
int hammingDistance = 0;
for (int i = 0; i < n; i++) {
int root = find(parent, i);
Map<Integer, Integer> group = groups.get(root);
if (group.containsKey(target[i]) && group.get(target[i]) > 0) {
group.put(target[i], group.get(target[i]) - 1);
} else {
hammingDistance++;
}
}
return hammingDistance;
}
private int find(int[] parent, int node) {
if (parent[node] == -1) {
return node;
}
parent[node] = find(parent, parent[node]);
return parent[node];
}
}Loading editor...