LeetCode 1722: Minimize Hamming Distance After Swap Operations Solution

Master LeetCode problem 1722 (Minimize Hamming Distance After Swap Operations), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1722. Minimize Hamming Distance After Swap Operations

Medium

Array Depth-First Search Union Find

Problem Explanation

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.

Solution Code

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];
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1722 (Minimize Hamming Distance After Swap Operations)?

This page provides optimized solutions for LeetCode problem 1722 (Minimize Hamming Distance After Swap Operations) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1722 (Minimize Hamming Distance After Swap Operations)?

The time complexity for LeetCode 1722 (Minimize Hamming Distance After Swap Operations) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1722 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1722 in Java, C++, or Python.

Back to LeetCode Solutions