Leetcode 1722. Minimize Hamming Distance After Swap Operations
Problem Explanation
You are given three integer arrays: source, target, and allowedSwaps. The source and target arrays have the same length, n, and represent two different sequences of integers. The allowedSwaps array contains pairs of indices in the source array that you are allowed to swap the elements in those indices.
The goal is to minimize the Hamming distance between source and target by performing any number of swap operations on the source array using the allowed swaps. The Hamming distance of two arrays of the same length is the number of positions where the elements are different. In other words, it is the number of indices i such that source[i] != target[i].
Solution Approach
To solve this problem, we can use the Union-Find data structure, which is a data structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets. The main operations provided by the Union-Find data structure are "Find" which determines which subset a particular element is in, and "Union" which joins two subsets into a single subset. In this context, "Find" translates to finding the group or connected components of a particular index, and "Union" translates to merging two groups or connected components based on the allowed swaps.
For each allowed swap in the allowedSwaps array, we can perform a union operation on the indices in the corresponding pair of the swap. After performing all union operations, we can create a mapping of connected components to a dictionary containing the frequency of the elements within that connected component in both the source and target arrays. We can then iterate through the mappings calculating the minimum possible Hamming distance by finding the number of elements that can't be matched between the source and target arrays within each connected component.
Solution in Python
1class Solution:
2 def minimumHammingDistance(self, source, target, allowedSwaps):
3 n = len(source)
4
5 # Define the Find function for the Union-Find structure
6 def find(x):
7 if x != parent[x]:
8 parent[x] = find(parent[x])
9 return parent[x]
10
11 # Initialize the Union-Find structure
12 parent = list(range(n))
13
14 # Perform Union operations for the allowed swaps
15 for i, j in allowedSwaps:
16 parent[find(i)] = find(j)
17
18 # Create the mappings of connected components to a dictionary
19 # containing frequencies of elements in the source and target arrays
20 groups_source = {}
21 groups_target = {}
22
23 for i in range(n):
24 root = find(i)
25
26 if root not in groups_source:
27 groups_source[root] = {}
28 groups_target[root] = {}
29
30 groups_source[root][source[i]] = groups_source[root].get(source[i], 0) + 1
31 groups_target[root][target[i]] = groups_target[root].get(target[i], 0) + 1
32
33 # Calculate the minimum possible Hamming distance
34 hamming_distance = 0
35 for root in groups_source:
36 for val in groups_source[root]:
37 hamming_distance += max(0, groups_source[root][val] - groups_target[root].get(val, 0))
38
39 return hamming_distance
Solution in Java
1import java.util.*;
2
3class Solution {
4 public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
5 int n = source.length;
6
7 // Initialize the Union-Find structure
8 int[] parent = new int[n];
9 for (int i = 0; i < n; i++) {
10 parent[i] = i;
11 }
12
13 // Define the Find function for the Union-Find structure
14 int find(int x) {
15 if (x != parent[x]) {
16 parent[x] = find(parent[x]);
17 }
18 return parent[x];
19 }
20
21 // Perform Union operations for the allowed swaps
22 for (int[] swap : allowedSwaps) {
23 parent[find(swap[0])] = find(swap[1]);
24 }
25
26 // Create the mappings of connected components to a dictionary
27 // containing frequencies of elements in the source and target arrays
28 Map<Integer, Map<Integer, Integer>> groups_source = new HashMap<>();
29 Map<Integer, Map<Integer, Integer>> groups_target = new HashMap<>();
30
31 for (int i = 0; i < n; i++) {
32 int root = find(i);
33
34 groups_source.putIfAbsent(root, new HashMap<>());
35 groups_target.putIfAbsent(root, new HashMap<>());
36
37 groups_source.get(root).put(source[i], groups_source.get(root).getOrDefault(source[i], 0) + 1);
38 groups_target.get(root).put(target[i], groups_target.get(root).getOrDefault(target[i], 0) + 1);
39 }
40
41 // Calculate the minimum possible Hamming distance
42 int hamming_distance = 0;
43 for (int root : groups_source.keySet()) {
44 for (int val : groups_source.get(root).keySet()) {
45 hamming_distance += Math.max(0, groups_source.get(root).get(val) - groups_target.get(root).getOrDefault(val, 0));
46 }
47 }
48
49 return hamming_distance;
50 }
51}
Solution in JavaScript
1class Solution {
2 minimumHammingDistance(source, target, allowedSwaps) {
3 const n = source.length;
4
5 // Define the Find function for the Union-Find structure
6 function find(x) {
7 if (x !== parent[x]) {
8 parent[x] = find(parent[x]);
9 }
10 return parent[x];
11 }
12
13 // Initialize the Union-Find structure
14 const parent = [];
15 for (let i = 0; i < n; i++) {
16 parent[i] = i;
17 }
18
19 // Perform Union operations for the allowed swaps
20 for (const swap of allowedSwaps) {
21 parent[find(swap[0])] = find(swap[1]);
22 }
23
24 // Create the mappings of connected components to a dictionary
25 // containing frequencies of elements in the source and target arrays
26 const groups_source = {};
27 const groups_target = {};
28
29 for (let i = 0; i < n; i++) {
30 const root = find(i);
31
32 if (!groups_source[root]) {
33 groups_source[root] = {};
34 groups_target[root] = {};
35 }
36
37 if (!groups_source[root][source[i]]) {
38 groups_source[root][source[i]] = 0;
39 }
40 groups_source[root][source[i]]++;
41
42 if (!groups_target[root][target[i]]) {
43 groups_target[root][target[i]] = 0;
44 }
45 groups_target[root][target[i]]++;
46 }
47
48 // Calculate the minimum possible Hamming distance
49 let hamming_distance = 0;
50 for (const root in groups_source) {
51 for (const val in groups_source[root]) {
52 hamming_distance += Math.max(0, groups_source[root][val] - (groups_target[root][val] || 0));
53 }
54 }
55
56 return hamming_distance;
57 }
58}
Solution in C++
1#include <vector>
2#include <unordered_map>
3
4class Solution {
5public:
6 int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
7 int n = source.size();
8
9 // Define the Find function for the Union-Find structure
10 function<int(int)> find = [&](int x) {
11 if (x != parent[x]) {
12 parent[x] = find(parent[x]);
13 }
14 return parent[x];
15 };
16
17 // Initialize the Union-Find structure
18 vector<int> parent(n);
19 for (int i = 0; i < n; i++) {
20 parent[i] = i;
21 }
22
23 // Perform Union operations for the allowed swaps
24 for (auto& swap : allowedSwaps) {
25 parent[find(swap[0])] = find(swap[1]);
26 }
27
28 // Create the mappings of connected components to a dictionary
29 // containing frequencies of elements in the source and target arrays
30 unordered_map<int, unordered_map<int, int>> groups_source, groups_target;
31
32 for (int i = 0; i < n; i++) {
33 int root = find(i);
34
35 groups_source[root][source[i]]++;
36 groups_target[root][target[i]]++;
37 }
38
39 // Calculate the minimum possible Hamming distance
40 int hamming_distance = 0;
41 for (auto& it : groups_source) {
42 int root = it.first;
43 for (auto& it2 : it.second) {
44 int val = it2.first;
45 int cnt = it2.second;
46 hamming_distance += max(0, cnt - groups_target[root][val]);
47 }
48 }
49
50 return hamming_distance;
51 }
52
53private:
54 vector<int> parent;
55};
Solution in C#
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int MinimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
6 int n = source.Length;
7
8 // Define the Find function for the Union-Find structure
9 int Find(int x) {
10 if (x != parent[x]) {
11 parent[x] = Find(parent[x]);
12 }
13 return parent[x];
14 }
15
16 // Initialize the Union-Find structure
17 int[] parent = new int[n];
18 for (int i = 0; i < n; i++) {
19 parent[i] = i;
20 }
21
22 // Perform Union operations for the allowed swaps
23 foreach (int[] swap in allowedSwaps) {
24 parent[Find(swap[0])] = Find(swap[1]);
25 }
26
27 // Create the mappings of connected components to a dictionary
28 // containing frequencies of elements in the source and target arrays
29 Dictionary<int, Dictionary<int, int>> groups_source = new Dictionary<int, Dictionary<int, int>>();
30 Dictionary<int, Dictionary<int, int>> groups_target = new Dictionary<int, Dictionary<int, int>>();
31
32 for (int i = 0; i < n; i++) {
33 int root = Find(i);
34
35 if (!groups_source.ContainsKey(root)) {
36 groups_source[root] = new Dictionary<int, int>();
37 groups_target[root] = new Dictionary<int, int>();
38 }
39
40 if (!groups_source[root].ContainsKey(source[i])) {
41 groups_source[root][source[i]] = 0;
42 }
43 groups_source[root][source[i]]++;
44
45 if (!groups_target[root].ContainsKey(target[i])) {
46 groups_target[root][target[i]] = 0;
47 }
48 groups_target[root][target[i]]++;
49 }
50
51 // Calculate the minimum possible Hamming distance
52 int hamming_distance = 0;
53 foreach (int root in groups_source.Keys) {
54 foreach (int val in groups_source[root].Keys) {
55 int difference = groups_source[root][val] - groups_target[root].GetValueOrDefault(val, 0);
56 hamming_distance += Math.Max(0, difference);
57 }
58 }
59
60 return hamming_distance;
61 }
62}
In this article, we've provided a detailed problem explanation and solution approach to minimize the Hamming distance between two integer arrays, source and target, using the allowed swaps. We've implemented the solution using the Union-Find data structure. The solution has been provided in six different languages - Python, Java, JavaScript, C++, C#, and Ruby.
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.