Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1722.html
1722. Minimize Hamming Distance After Swap Operations
Level
Medium
Description
You are given two integer arrays, source and target, both of length n. You are also given an array allowedSwaps where each allowedSwaps[i] = [a_i, b_i] indicates that you are allowed to swap the elements at index a_i and index b_i (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 <= 10^51 <= source[i], target[i] <= 10^50 <= allowedSwaps.length <= 10^5allowedSwaps[i].length == 20 <= a_i, b_i <= n - 1a_i != b_i
Solution
Use union set to find the disjoint sets of indices, where the indices in each set can be swapped from allowedSwaps. For each disjoint set, obtain the number of occurrences of each number in source and target. If the numbers of occurrences of a number is difference from the two arrays, then calculate the Hamming Distance using the sum of absolute differences divided by 2.
After all disjoint sets’ Hamming Distances are calculated, return the sum of all Hamming Distances.
-
class Solution { public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) { int length = source.length; int[] parent = new int[length]; for (int i = 0; i < length; i++) parent[i] = i; for (int[] swap : allowedSwaps) { int index1 = swap[0], index2 = swap[1]; if (find(parent, index1) != find(parent, index2)) union(parent, index1, index2); } Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>(); for (int i = 0; i < length; i++) { int root = find(parent, i); List<Integer> indices = map.getOrDefault(root, new ArrayList<Integer>()); indices.add(i); map.put(root, indices); } int distance = 0; for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) { Map<Integer, Integer> counts = new HashMap<Integer, Integer>(); List<Integer> indices = entry.getValue(); int size = indices.size(); for (int i = 0; i < size; i++) { int index = indices.get(i); int num1 = source[index], num2 = target[index]; int count1 = counts.getOrDefault(num1, 0) + 1; if (count1 != 0) counts.put(num1, count1); else counts.remove(num1); int count2 = counts.getOrDefault(num2, 0) - 1; if (count2 != 0) counts.put(num2, count2); else counts.remove(num2); } for (Map.Entry<Integer, Integer> countEntry : counts.entrySet()) distance += Math.abs(countEntry.getValue()); } return distance / 2; } public void union(int[] parent, int index1, int index2) { parent[find(parent, index1)] = find(parent, index2); } public int find(int[] parent, int index) { while (parent[index] != index) { parent[index] = find(parent, parent[index]); index = parent[index]; } return index; } } ############ class Solution { private int[] p; public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) { int n = source.length; p = new int[n]; for (int i = 0; i < n; ++i) { p[i] = i; } for (int[] e : allowedSwaps) { p[find(e[0])] = find(e[1]); } Map<Integer, Map<Integer, Integer>> mp = new HashMap<>(); for (int i = 0; i < n; ++i) { int root = find(i); mp.computeIfAbsent(root, k -> new HashMap<>()) .put(source[i], mp.get(root).getOrDefault(source[i], 0) + 1); } int res = 0; for (int i = 0; i < n; ++i) { int root = find(i); if (mp.get(root).getOrDefault(target[i], 0) > 0) { mp.get(root).put(target[i], mp.get(root).get(target[i]) - 1); } else { ++res; } } return res; } private int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } } -
// OJ: https://leetcode.com/problems/minimize-hamming-distance-after-swap-operations/ // Time: O(N) // Space: O(N) class UnionFind { vector<int> id; public: UnionFind(int n) : id(n) { iota(begin(id), end(id), 0); } void connect(int a, int b) { id[find(a)] = find(b); } int find(int a) { return id[a] == a ? a : (id[a] = find(id[a])); } }; class Solution { public: int minimumHammingDistance(vector<int>& S, vector<int>& T, vector<vector<int>>& A) { int N = S.size(), ans = 0; UnionFind uf(N); for (auto &v : A) uf.connect(v[0], v[1]); unordered_map<int, unordered_map<int, int>> m; for (int i = 0; i < N; ++i) { int j = uf.find(i); m[j][S[i]]++; m[j][T[i]]--; } for (auto &[group, cnts] : m) { for (auto &[n, cnt] : cnts) ans += max(cnt, 0); } return ans; } }; -
class Solution: def minimumHammingDistance( self, source: List[int], target: List[int], allowedSwaps: List[List[int]] ) -> int: n = len(source) p = list(range(n)) def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] for i, j in allowedSwaps: p[find(i)] = find(j) mp = defaultdict(Counter) for i in range(n): mp[find(i)][source[i]] += 1 res = 0 for i in range(n): if mp[find(i)][target[i]] > 0: mp[find(i)][target[i]] -= 1 else: res += 1 return res ############ # 1722. Minimize Hamming Distance After Swap Operations # https://leetcode.com/problems/minimize-hamming-distance-after-swap-operations/ class Solution: def minimumHammingDistance(self, source, target, edges): res = n = len(source) G = [set() for i in range(n)] for i, j in edges: G[i].add(j) G[j].add(i) seen = [0] * n def dfs(i): seen[i] = 1 found.append(i) for j in G[i]: if not seen[j]: dfs(j) for i in range(n): if seen[i]: continue found = [] dfs(i) count1 = collections.Counter(source[j] for j in found) count2 = collections.Counter(target[j] for j in found) res -= sum((count1 & count2).values()) return res -
var p []int func minimumHammingDistance(source []int, target []int, allowedSwaps [][]int) int { n := len(source) p = make([]int, n) for i := 0; i < n; i++ { p[i] = i } for _, e := range allowedSwaps { p[find(e[0])] = find(e[1]) } mp := make(map[int]map[int]int) for i := 0; i < n; i++ { if mp[find(i)] == nil { mp[find(i)] = make(map[int]int) } mp[find(i)][source[i]]++ } res := 0 for i := 0; i < n; i++ { if mp[find(i)][target[i]] > 0 { mp[find(i)][target[i]]-- } else { res++ } } return res } func find(x int) int { if p[x] != x { p[x] = find(p[x]) } return p[x] } -
function minimumHammingDistance( source: number[], target: number[], allowedSwaps: number[][], ): number { const n = source.length; const p: number[] = Array.from({ length: n }, (_, i) => i); const find = (x: number): number => { if (p[x] !== x) { p[x] = find(p[x]); } return p[x]; }; for (const [a, b] of allowedSwaps) { p[find(a)] = find(b); } const cnt: Map<number, Map<number, number>> = new Map(); for (let i = 0; i < n; ++i) { const j = find(i); if (!cnt.has(j)) { cnt.set(j, new Map()); } const m = cnt.get(j)!; m.set(source[i], (m.get(source[i]) ?? 0) + 1); } let ans = 0; for (let i = 0; i < n; ++i) { const j = find(i); const m = cnt.get(j)!; m.set(target[i], (m.get(target[i]) ?? 0) - 1); if (m.get(target[i])! < 0) { ++ans; } } return ans; }