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.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ