1722. Minimize Hamming Distance After Swap Operations LeetCode Solution
In this guide, you will get 1722. Minimize Hamming Distance After Swap Operations LeetCode Solution with the best time and space complexity. The solution to Minimize Hamming Distance After Swap Operations problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimize Hamming Distance After Swap Operations
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.
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.
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
Complexity Analysis
Time Complexity: O(n\log^* n)
Space Complexity: O(n)
1722. Minimize Hamming Distance After Swap Operations LeetCode Solution in C++
class UnionFind {
public:
UnionFind(int n) : id(n), rank(n) {
iota(id.begin(), id.end(), 0);
}
void unionByRank(int u, int v) {
const int i = find(u);
const int j = find(v);
if (i == j)
return;
if (rank[i] < rank[j]) {
id[i] = j;
} else if (rank[i] > rank[j]) {
id[j] = i;
} else {
id[i] = j;
++rank[j];
}
}
int find(int u) {
return id[u] == u ? u : id[u] = find(id[u]);
}
private:
vector<int> id;
vector<int> rank;
};
class Solution {
public:
int minimumHammingDistance(vector<int>& source, vector<int>& target,
vector<vector<int>>& allowedSwaps) {
const int n = source.size();
int ans = 0;
UnionFind uf(n);
vector<unordered_map<int, int>> groupIdToCount(n);
for (const vector<int>& allowedSwap : allowedSwaps) {
const int a = allowedSwap[0];
const int b = allowedSwap[1];
uf.unionByRank(a, b);
}
for (int i = 0; i < n; ++i)
++groupIdToCount[uf.find(i)][source[i]];
for (int i = 0; i < n; ++i) {
const int groupId = uf.find(i);
unordered_map<int, int>& count = groupIdToCount[groupId];
if (!count.contains(target[i]))
++ans;
else if (--count[target[i]] == 0)
count.erase(target[i]);
}
return ans;
}
}; /* code provided by PROGIEZ */
1722. Minimize Hamming Distance After Swap Operations LeetCode Solution in Java
class UnionFind {
public UnionFind(int n) {
id = new int[n];
rank = new int[n];
for (int i = 0; i < n; ++i)
id[i] = i;
}
public void unionByRank(int u, int v) {
final int i = find(u);
final int j = find(v);
if (i == j)
return;
if (rank[i] < rank[j]) {
id[i] = j;
} else if (rank[i] > rank[j]) {
id[j] = i;
} else {
id[i] = j;
++rank[j];
}
}
public int find(int u) {
return id[u] == u ? u : (id[u] = find(id[u]));
}
private int[] id;
private int[] rank;
}
class Solution {
public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
final int n = source.length;
int ans = 0;
UnionFind uf = new UnionFind(n);
Map<Integer, Integer>[] groupIdToCount = new Map[n];
for (int i = 0; i < n; ++i)
groupIdToCount[i] = new HashMap<>();
for (int[] allowedSwap : allowedSwaps) {
final int a = allowedSwap[0];
final int b = allowedSwap[1];
uf.unionByRank(a, b);
}
for (int i = 0; i < n; ++i)
groupIdToCount[uf.find(i)].merge(source[i], 1, Integer::sum);
for (int i = 0; i < n; ++i) {
final int groupId = uf.find(i);
Map<Integer, Integer> count = groupIdToCount[groupId];
if (!count.containsKey(target[i]))
++ans;
else if (count.merge(target[i], -1, Integer::sum) == 0)
count.remove(target[i]);
}
return ans;
}
} // code provided by PROGIEZ
1722. Minimize Hamming Distance After Swap Operations LeetCode Solution in Python
class UnionFind:
def __init__(self, n: int):
self.id = list(range(n))
self.rank = [0] * n
def unionByRank(self, u: int, v: int) -> None:
i = self.find(u)
j = self.find(v)
if i == j:
return
if self.rank[i] < self.rank[j]:
self.id[i] = j
elif self.rank[i] > self.rank[j]:
self.id[j] = i
else:
self.id[i] = j
self.rank[j] += 1
def find(self, u: int) -> int:
if self.id[u] != u:
self.id[u] = self.find(self.id[u])
return self.id[u]
class Solution:
def minimumHammingDistance(
self,
source: list[int],
target: list[int],
allowedSwaps: list[list[int]],
) -> int:
n = len(source)
ans = 0
uf = UnionFind(n)
groupIdToCount = [collections.Counter() for _ in range(n)]
for a, b in allowedSwaps:
uf.unionByRank(a, b)
for i in range(n):
groupIdToCount[uf.find(i)][source[i]] += 1
for i in range(n):
groupId = uf.find(i)
count = groupIdToCount[groupId]
if target[i] not in count:
ans += 1
else:
count[target[i]] -= 1
if count[target[i]] == 0:
del count[target[i]]
return ans # code by PROGIEZ
