Minimize Hamming Distance After Swap Operations

Med

#1578Time: `O(n + S)`, where `n` is the length of the arrays and `S` is the number of allowed swaps. Building the adjacency list takes `O(S)`. The graph traversal visits each vertex and edge once, taking `O(n + S)`. Processing each component involves creating frequency maps and counting matches, which takes time proportional to the component's size. Summed over all components, this is `O(n)`.Space: `O(n + S)`. The adjacency list requires `O(S)` space. The `visited` array, recursion stack for DFS (or queue for BFS), and the data structures for storing component indices and frequency counts can take up to `O(n)` space in the worst case.

Algorithms

Depth-First Search Union Find

Data structures

Array

Prompt

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.length
1 <= n <= 10⁵
1 <= source[i], target[i] <= 10⁵
0 <= allowedSwaps.length <= 10⁵
allowedSwaps[i].length == 2
0 <= a_i, b_i <= n - 1
a_i != b_i

Approaches

2 approaches with complexity analysis and trade-offs.

This approach models the problem as a graph problem. The indices of the array 0, 1, ..., n-1 are the vertices of the graph. An edge exists between two indices u and v if a swap [u, v] is allowed. The allowedSwaps array defines the edges. The key insight is that any two indices in the same connected component are mutually swappable. This is because if u can be swapped with v, and v with w, you can move the element from u to v, then the original element at v to w, and so on. This means within a connected component of indices, we can arrange the source elements at those indices in any permutation we like. To minimize the Hamming distance, for each connected component, we should arrange the source elements to match the target elements as much as possible. The maximum number of matches we can achieve in a component is limited by the multiset of numbers available from source at those indices.

Algorithm

Build an adjacency list for a graph with n vertices from the allowedSwaps.
Initialize a visited array of size n to false.
Initialize total_matches = 0.
Loop from i = 0 to n-1:
- If i is not visited:
  - Start a DFS/BFS from i to find all indices in the connected component.
  - Store these indices in a list component_indices.
  - Create a frequency map source_counts of source values for indices in component_indices.
  - For each index in component_indices:
    - If target[index] is in source_counts with a positive count:
      - Increment total_matches.
      - Decrement the count of target[index] in source_counts.
Return n - total_matches.

Walkthrough

The algorithm proceeds by first identifying these connected components using a standard graph traversal algorithm like Depth-First Search (DFS) or Breadth-First Search (BFS).

Build Graph: Construct an adjacency list representation of the graph. For each pair [u, v] in allowedSwaps, add an edge between u and v.
Traverse and Process Components: Iterate through each index from 0 to n-1. If an index hasn't been visited yet, it marks the start of a new connected component.
Find Component: Start a traversal (e.g., DFS) from the unvisited index to find all indices belonging to its connected component. Keep track of visited indices to avoid processing them again.
Count Matches: For each discovered component: a. Collect all source values at the component's indices into a frequency map (e.g., a HashMap). This map tells us which numbers are available and how many of each. b. Iterate through the component's indices again. For each index j, look at the required value target[j]. If this value is present in our frequency map (i.e., its count is greater than 0), we can make a match. We increment our total match count and decrement the frequency of that value in the map to signify it has been used.
Calculate Distance: After iterating through all indices and processing all components, the total number of matches is found. The minimum Hamming distance is the total number of elements n minus the total number of matches.

1class Solution {2    public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {3        int n = source.length;4        List<List<Integer>> adj = new ArrayList<>();5        for (int i = 0; i < n; i++) {6            adj.add(new ArrayList<>());7        }8        for (int[] swap : allowedSwaps) {9            adj.get(swap[0]).add(swap[1]);10            adj.get(swap[1]).add(swap[0]);11        }12 13        boolean[] visited = new boolean[n];14        int matches = 0;15 16        for (int i = 0; i < n; i++) {17            if (!visited[i]) {18                List<Integer> componentIndices = new ArrayList<>();19                dfs(i, adj, visited, componentIndices);20                21                Map<Integer, Integer> sourceCounts = new HashMap<>();22                for (int index : componentIndices) {23                    sourceCounts.put(source[index], sourceCounts.getOrDefault(source[index], 0) + 1);24                }25 26                for (int index : componentIndices) {27                    if (sourceCounts.getOrDefault(target[index], 0) > 0) {28                        matches++;29                        sourceCounts.put(target[index], sourceCounts.get(target[index]) - 1);30                    }31                }32            }33        }34 35        return n - matches;36    }37 38    private void dfs(int u, List<List<Integer>> adj, boolean[] visited, List<Integer> component) {39        visited[u] = true;40        component.add(u);41        for (int v : adj.get(u)) {42            if (!visited[v]) {43                dfs(v, adj, visited, component);44            }45        }46    }47}

Complexity

Time

`O(n + S)`, where `n` is the length of the arrays and `S` is the number of allowed swaps. Building the adjacency list takes `O(S)`. The graph traversal visits each vertex and edge once, taking `O(n + S)`. Processing each component involves creating frequency maps and counting matches, which takes time proportional to the component's size. Summed over all components, this is `O(n)`.

Space

`O(n + S)`. The adjacency list requires `O(S)` space. The `visited` array, recursion stack for DFS (or queue for BFS), and the data structures for storing component indices and frequency counts can take up to `O(n)` space in the worst case.

Trade-offs

Pros

It's a direct and intuitive application of graph traversal algorithms.
The logic is relatively easy to follow if you are familiar with DFS or BFS.

Cons

The space complexity depends on the number of swaps S, which can be large.
It might be slightly less performant than a DSU-based solution due to the overhead of building an explicit graph and managing recursion/queues.

A more optimized approach uses the Disjoint Set Union (DSU) data structure, also known as Union-Find. This data structure is highly efficient for problems involving partitioning a set of elements into a number of disjoint, non-overlapping sets. In our case, the elements are the indices 0, 1, ..., n-1, and we want to group them into sets where indices within the same set are mutually swappable. The DSU data structure provides two main operations: find, which determines the set an element belongs to (by returning a representative or "root" element), and union, which merges two sets.

Algorithm

Initialize a DSU structure with n elements.
For each swap [u, v] in allowedSwaps, perform dsu.union(u, v).
Create a map componentSourceCounts to store frequency maps of source values for each component.
Loop from i = 0 to n-1:
- Find the root r = dsu.find(i).
- Increment the count of source[i] in the frequency map corresponding to root r.
Initialize matches = 0.
Loop from i = 0 to n-1:
- Find the root r = dsu.find(i).
- Get the frequency map for root r.
- If the count for target[i] in this map is positive:
  - Increment matches.
  - Decrement the count of target[i] in the map.
Return n - matches.

Walkthrough

The algorithm uses DSU to efficiently group the indices and then calculates the matches within each group.

Initialize DSU: Create a DSU structure for n indices. Initially, each index is in its own set.
Build Sets: Iterate through the allowedSwaps. For each swap [u, v], call dsu.union(u, v). This merges the sets containing u and v. After this step, all indices that belong to the same connected component will be in the same set in the DSU structure.
Group Values by Component: We need to know the multiset of source values available in each component. We can use a Map where keys are the root of each component and values are frequency maps of the source numbers in that component. We iterate from i = 0 to n-1, find the root of i's component using dsu.find(i), and update the frequency map for that root with source[i].
Count Matches: Initialize matches = 0. Iterate again from i = 0 to n-1. For each index i, find its component's root r = dsu.find(i). Check the target[i] value against the frequency map of source values for component r. If target[i] is available (count > 0), we've found a match. Increment matches and decrement the count of target[i] in the map.
Calculate Distance: The minimum Hamming distance is n - matches. This method avoids explicitly building a graph and storing component indices in lists, making it more space-efficient.

1class DSU {2    private int[] parent;3    private int[] rank;4 5    public DSU(int n) {6        parent = new int[n];7        rank = new int[n];8        for (int i = 0; i < n; i++) {9            parent[i] = i;10        }11    }12 13    public int find(int i) {14        if (parent[i] == i) {15            return i;16        }17        return parent[i] = find(parent[i]); // Path compression18    }19 20    public void union(int i, int j) {21        int rootI = find(i);22        int rootJ = find(j);23        if (rootI != rootJ) {24            // Union by rank25            if (rank[rootI] > rank[rootJ]) {26                parent[rootJ] = rootI;27            } else if (rank[rootI] < rank[rootJ]) {28                parent[rootI] = rootJ;29            } else {30                parent[rootJ] = rootI;31                rank[rootI]++;32            }33        }34    }35}36 37class Solution {38    public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {39        int n = source.length;40        DSU dsu = new DSU(n);41        for (int[] swap : allowedSwaps) {42            dsu.union(swap[0], swap[1]);43        }44 45        Map<Integer, Map<Integer, Integer>> componentSourceCounts = new HashMap<>();46        for (int i = 0; i < n; i++) {47            int root = dsu.find(i);48            componentSourceCounts.putIfAbsent(root, new HashMap<>());49            Map<Integer, Integer> counts = componentSourceCounts.get(root);50            counts.put(source[i], counts.getOrDefault(source[i], 0) + 1);51        }52 53        int matches = 0;54        for (int i = 0; i < n; i++) {55            int root = dsu.find(i);56            Map<Integer, Integer> counts = componentSourceCounts.get(root);57            if (counts.getOrDefault(target[i], 0) > 0) {58                matches++;59                counts.put(target[i], counts.get(target[i]) - 1);60            }61        }62 63        return n - matches;64    }65}

Complexity

Time

`O((n + S) * α(n))`, where `α(n)` is the extremely slow-growing inverse Ackermann function. For all practical purposes, `α(n)` is a small constant (less than 5). Thus, the complexity is nearly linear, `O(n + S)`. The DSU operations take `O(S * α(n))`, and the loops for processing values take `O(n * α(n))`.

Space

`O(n)`. The DSU structure itself (parent and rank arrays) takes `O(n)` space. The map `componentSourceCounts` will store `n` values distributed among different component frequency maps, so its total size is also `O(n)`. This is an improvement over the graph traversal approach, which requires `O(n + S)` space.

Trade-offs

Pros

Highly efficient in both time and space.
The space complexity is independent of the number of swaps S.
Often faster in practice due to optimized find and union operations and better memory locality.

Cons

Requires knowledge of the Disjoint Set Union data structure, which is more specialized than basic graph traversals.

Solutions

Solution

1class 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 [] a : allowedSwaps ) { p [ find ( a [ 0 ])] = find ( a [ 1 ]); } Map < Integer , Map < Integer , Integer >> cnt = new HashMap <>(); for ( int i = 0 ; i < n ; ++ i ) { int j = find ( i ); cnt . computeIfAbsent ( j , k -> new HashMap <>()). merge ( source [ i ], 1 , Integer: : sum ); } int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { int j = find ( i ); Map < Integer , Integer > t = cnt . get ( j ); if ( t . merge ( target [ i ], - 1 , Integer: : sum ) < 0 ) { ++ ans ; } } return ans ; } private int find ( int x ) { if ( p [ x ] != x ) { p [ x ] = find ( p [ x ]); } return p [ x ]; } }

1class Solution { public: int minimumHammingDistance ( vector < int >& source , vector < int >& target , vector < vector < int >>& allowedSwaps ) { int n = source . size (); vector < int > p ( n ); iota ( p . begin (), p . end (), 0 ); function < int ( int ) > find = [ & ]( int x ) { return x == p [ x ] ? x : p [ x ] = find ( p [ x ]); }; for ( auto & a : allowedSwaps ) { p [ find ( a [ 0 ])] = find ( a [ 1 ]); } unordered_map < int , unordered_map < int , int >> cnt ; for ( int i = 0 ; i < n ; ++ i ) { ++ cnt [ find ( i )][ source [ i ]]; } int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { if ( -- cnt [ find ( i )][ target [ i ]] < 0 ) { ++ ans ; } } return ans ; } };

1class Solution : def minimumHammingDistance ( self , source : List [ int ], target : List [ int ], allowedSwaps : List [ List [ int ]] ) -> int : def find ( x : int ) -> int : if p [ x ] != x : p [ x ] = find ( p [ x ]) return p [ x ] n = len ( source ) p = list ( range ( n )) for a , b in allowedSwaps : p [ find ( a )] = find ( b ) cnt = defaultdict ( Counter ) for i , x in enumerate ( source ): j = find ( i ) cnt [ j ][ x ] += 1 ans = 0 for i , x in enumerate ( target ): j = find ( i ) cnt [ j ][ x ] -= 1 ans += cnt [ j ][ x ] < 0 return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem