Skip to main content
Talentd

Minimize Hamming Distance After Swap Operations - Solution & Explanation

MediumArrayDepth-First SearchUnion Find16 min readAsked at: Google, Bloomberg, Sumologic
Practice this problem

Problem Statement

You are given two integer arrays, source and target, both of length n. You are also given an array allowedSwaps where each allowedSwaps[i] = [ai, bi] indicates that you are allowed to swap the elements at index ai and index bi (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 <= 105
  • 1 <= source[i], target[i] <= 105
  • 0 <= allowedSwaps.length <= 105
  • allowedSwaps[i].length == 2
  • 0 <= ai, bi <= n - 1
  • ai != bi

Approach Overview

Problem Overview: You are given two arrays source and target, plus a list of index pairs that can be swapped any number of times. The task is to minimize the Hamming distance (number of mismatched positions) after performing any valid swaps.

The key observation: if indices are connected through allowed swaps, you can rearrange values freely inside that connected group. The problem reduces to grouping indices and checking how many values can be matched within each group.

Approach 1: Union-Find (Disjoint Set) Approach (O(n α(n) + m) time, O(n) space)

Use a Union-Find structure to group indices connected by swap operations. For every pair (a, b), union their sets so all reachable indices belong to the same component. Once groups are built, collect the values of source for each component and count frequencies using a hash map. Iterate through the same indices in target and reduce counts when matches exist. Any remaining unmatched elements contribute to the Hamming distance. Union-Find is efficient here because it quickly merges components and finds their representative roots.

Approach 2: Breadth-First Search (BFS) on Swap Graph (O(n + m) time, O(n + m) space)

Model the swap pairs as a graph where each index is a node and edges represent allowed swaps. Use BFS (or DFS) to discover connected components. For each component, gather all indices reachable from the starting node. Within that group, build a frequency map of source values and try to match them against target. Decrease counts when matches occur; unmatched values add to the final Hamming distance. This approach works well when you prefer explicit graph traversal over a disjoint-set structure.

Both approaches rely on the same insight: swaps allow arbitrary permutations inside each connected component. Instead of simulating swaps, you treat each component as a bucket of indices and maximize value matches.

Recommended for interviews: The Union-Find solution is the expected approach. It shows you recognize the hidden connected-component structure in swap operations. BFS/DFS demonstrates the same reasoning but with graph traversal. Interviewers typically prefer Union-Find because it scales well and directly models connectivity problems often seen with array index relationships.

Approach 1: Union-Find (Disjoint Set) Approach

This approach uses a union-find data structure to group indices in the source array where swaps are allowed. The objective is to find connected components in the index graph defined by allowed swaps. Once we have the components, we can focus on minimizing the Hamming distance within each component by checking if elements at corresponding indices can be rearranged to match the target array.

The Python solution first initializes a union-find (disjoint set) data structure to manage connection between indices as defined by allowedSwaps. It uses union operations to connect indices and find operations to determine the connected component for each index. After identifying all components, for each component, it checks how elements from the source can match the target, thereby calculating any unmatched elements to determine the minimal Hamming distance.

Code

PythonJavaC++C

Python

Java

C++

C

Complexity

Time Complexity: O(n log n) due to path compression in union-find
Space Complexity: O(n) to store the parent and rank arrays

Try this approach in the editor →

Approach 2: Breadth-First Search (BFS) Approach

In this approach, treat each index as a node in a graph and swaps as edges connecting these nodes. Use BFS to traverse and identify connected components of indices in the source array. Once components are identified, adjust the source array to match the target in a minimized Hamming fashion.

The Python solution represents the allowed swaps as an adjacency list. It uses BFS to find connected components, then compares source and target elements within those components and calculates misalignments to compute the final Hamming distance.

Code

Python

Python

Complexity

Time Complexity: O(n + e), where e is the number of allowed swaps
Space Complexity: O(n + e) for graph and visited status

Try this approach in the editor →

Approach 3: Union-Find + Hash Table

We can consider each index as a node, and the element corresponding to each index as the value of the node. Then each element [a_i, b_i] in the given allowedSwaps represents an edge between index a_i and b_i. Therefore, we can use a union-find set to maintain these connected components.

After obtaining each connected component, we use a two-dimensional hash table cnt to count the number of occurrences of each element in each connected component. Finally, for each element in the array target, if its occurrence count in the corresponding connected component is greater than 0, we decrease its count by 1, otherwise, we increase the answer by 1.

The time complexity is O(n times log n) or O(n times \alpha(n)), and the space complexity is O(n). Here, n is the length of the array, and \alpha is the inverse Ackermann function.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Union-Find (Disjoint Set) Approach

Time Complexity: O(n log n) due to path compression in union-find
Space Complexity: O(n) to store the parent and rank arrays

Breadth-First Search (BFS) Approach

Time Complexity: O(n + e), where e is the number of allowed swaps
Space Complexity: O(n + e) for graph and visited status

Union-Find + Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Union-Find (Disjoint Set)O(n α(n) + m)O(n)Best general solution when many swap pairs exist and components must be merged efficiently
BFS Graph TraversalO(n + m)O(n + m)Useful when treating swaps as an explicit graph and exploring connected components directly

Video Solution

Minimize Hamming Distance After Swap Operations | Detailed | Simple Steps | Leetcode 1722 | MIK • codestorywithMIK • 8,663 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimize Hamming Distance After Swap Operations easy or hard?
The problem is classified as Medium difficulty. The implementation is straightforward once you recognize that swap operations create connected components. The challenge lies in identifying that you should group indices and compare value frequencies rather than simulate swaps.
Minimize Hamming Distance After Swap Operations Python/Java solution
The solution builds connected components using Union-Find or BFS, then counts frequencies of source values inside each component. While iterating through target values, matches reduce the frequency counts and unmatched elements increase the Hamming distance. The same logic translates directly to Python, Java, C++, or C with hash maps and a disjoint-set structure.
How to solve Minimize Hamming Distance After Swap Operations in O(n)?
Treat the swap pairs as edges connecting indices and find connected components using Union-Find or BFS. For each component, count frequencies of values from the source array and match them with values in the target array within that same component. Only unmatched elements contribute to the Hamming distance. With efficient Union-Find operations, the runtime is effectively near-linear.
What is the best approach for Minimize Hamming Distance After Swap Operations?
The Union-Find (Disjoint Set) approach is the most efficient and commonly expected solution. It groups indices that can reach each other through swap operations, forming connected components. Within each component, values can be freely rearranged, so you compare frequency counts of source and target values. The complexity is O(n α(n) + m) time with O(n) space.
Is Minimize Hamming Distance After Swap Operations asked at Google/Amazon/Meta?
This type of problem appears in interviews at companies like Google, Amazon, and Meta because it tests understanding of graph connectivity and Union-Find structures. Candidates must recognize that repeated swaps form connected components. Identifying this transformation is the core interview insight.
What data structure is used in Minimize Hamming Distance After Swap Operations?
The primary data structure is Union-Find (Disjoint Set Union) to track connected components of indices. Hash maps are also used to store frequency counts of values within each component. Alternatively, adjacency lists and BFS/DFS can be used to find components in the swap graph.
What is the time complexity of Minimize Hamming Distance After Swap Operations?
The optimal Union-Find solution runs in O(n α(n) + m) time, where n is the array length and m is the number of allowed swaps. The α(n) term comes from the inverse Ackermann function used in path compression. BFS or DFS approaches run in O(n + m) time by explicitly traversing the swap graph.

Ready to solve this problem?

Practice Minimize Hamming Distance After Swap Operations with our built-in code editor and test cases.

Practice on FleetCode
Previous

Make Lexicographically Smallest Array by Swapping Elements

Next

Smallest String With Swaps