Problem Description

You have two integer arrays source and target, both with the same length n. You're also given an array allowedSwaps where each element allowedSwaps[i] = [a_i, b_i] represents that you can swap the elements at positions a_i and b_i in the source array (using 0-based indexing). You can perform these swaps multiple times and in any order you want.

The Hamming distance between two arrays of equal length is the count of positions where the elements differ. In other words, it's the number of indices i where source[i] != target[i].

Your task is to find the minimum Hamming distance between source and target after performing any number of allowed swap operations on the source array.

For example, if you can swap elements at indices that are connected through the allowed swaps, you want to rearrange the source array optimally to match as many positions with target as possible. The positions that still don't match after optimal swapping contribute to the Hamming distance.

The key insight is that through the allowed swaps, certain indices become interconnected - if you can swap index a with b, and b with c, then elements at positions a, b, and c can be rearranged among themselves in any order. This forms groups of indices where elements can be freely rearranged within each group.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem can be modeled as a graph where each index is a node, and each allowed swap [a_i, b_i] creates an edge between nodes a_i and b_i. The swaps create connections between indices.

Is it a tree?

• No: The graph formed by allowed swaps is not necessarily a tree. It can have cycles (e.g., if we can swap indices 0↔1, 1↔2, and 2↔0, this forms a cycle) and may have multiple disconnected components.

Is the problem related to directed acyclic graphs?

• No: The swap relationships are bidirectional (if we can swap a with b, we can also swap b with a), so this is an undirected graph, not a DAG.

Is the problem related to shortest paths?

• No: We're not trying to find the shortest path between nodes. Instead, we need to identify which indices belong to the same connected component.

Does the problem involve connectivity?

• Yes: The core insight is that indices connected through a chain of allowed swaps form connected components. Within each component, elements can be rearranged freely among those positions.

Disjoint Set Union

• Yes: DSU (Union-Find) is the perfect data structure for this problem. It efficiently groups indices into connected components based on the allowed swaps.

Conclusion: The flowchart leads us to use Disjoint Set Union (DSU) to identify connected components. While DSU isn't strictly DFS, it solves the same connectivity problem that DFS would solve (finding connected components), but more efficiently for this use case. We could alternatively use DFS to explore each connected component, but DSU provides a cleaner solution for grouping indices that can exchange elements through swaps.

Intuition

The key insight is to recognize that the allowed swaps create groups of positions where elements can move freely among themselves. If we can swap position i with j, and position j with k, then through a series of swaps, we can move any element from positions i, j, or k to any of these three positions.

Think of it this way: imagine you have three cups at positions 0, 1, and 2. If you can swap cups at positions 0↔1 and 1↔2, then you can arrange the three cups in any order across these three positions. This forms a "connected component" where the elements are interchangeable.

Once we identify these connected components, the problem becomes much simpler. For each component:

1. Collect all the elements from source at positions in this component
2. Collect all the elements from target at positions in this component
3. Match as many elements as possible between these two collections

For example, if a component has positions [0, 2, 3]:

• From source: we might have elements [1, 5, 3] at these positions
• From target: we might have elements [3, 5, 2] at these positions

Since we can rearrange source elements freely within the component, we can match 3 with 3 and 5 with 5. The element 1 from source can't match with 2 from target, contributing 1 to the Hamming distance.

The mathematical approach is to count the frequency of each element in both arrays within each component. If source has three 5's in a component but target only needs two 5's, we can match two of them. The unmatched elements contribute to the minimum Hamming distance.

This transforms the problem from "finding optimal swaps" to "finding connected components and matching elements within each component" - a much more tractable problem that we can solve efficiently using Union-Find to identify components and hash tables to count element frequencies.

Learn more about Depth-First Search and Union Find patterns.

Solution Approach

The solution uses Union-Find (Disjoint Set Union) to group indices into connected components, followed by frequency counting within each component.

Step 1: Initialize Union-Find Structure

n = len(source)
p = list(range(n))

We create a parent array p where initially each index is its own parent (each index forms its own component).

Step 2: Build Connected Components

for a, b in allowedSwaps:
    p[find(a)] = find(b)

For each allowed swap [a, b], we union the two indices by connecting their root parents. The find function with path compression ensures efficient lookups:

def find(x: int) -> int:
    if p[x] != x:
        p[x] = find(p[x])  # Path compression
    return p[x]

Step 3: Count Source Elements by Component

cnt = defaultdict(Counter)
for i, x in enumerate(source):
    j = find(i)
    cnt[j][x] += 1

We use a two-dimensional hash table cnt where:

• First dimension: component ID (root parent)
• Second dimension: element value frequency counter

For each position i in source, we find its component ID j and increment the count of element source[i] in that component.

Step 4: Match with Target Elements

ans = 0
for i, x in enumerate(target):
    j = find(i)
    cnt[j][x] -= 1
    ans += cnt[j][x] < 0

For each position i in target:

• Find its component ID j
• Decrement the count of element target[i] in that component
• If the count goes negative, it means we don't have enough of this element in source to match, so we increment the answer

The clever part is that we're essentially doing a "greedy matching" - for each element needed in target, we try to use an available element from source within the same component. If cnt[j][x] becomes negative, it means we've exhausted all available copies of element x in component j, and this position contributes to the Hamming distance.

Time Complexity: O(n * α(n) + m) where n is array length, m is the number of allowed swaps, and α is the inverse Ackermann function (practically constant).

Space Complexity: O(n) for the Union-Find structure and the frequency counters.

Example Walkthrough

Let's walk through a concrete example to understand the solution approach.

Given:

• source = [1, 2, 3, 4]
• target = [2, 1, 4, 5]
• allowedSwaps = [[0, 1], [2, 3]]

Step 1: Initialize Union-Find

p = [0, 1, 2, 3]  # Each index is its own parent initially

Step 2: Build Connected Components

Processing [0, 1]:

• find(0) = 0, find(1) = 1
• Set p[1] = 0 (connect index 1 to index 0)
• Now p = [0, 0, 2, 3]

Processing [2, 3]:

• find(2) = 2, find(3) = 3
• Set p[3] = 2 (connect index 3 to index 2)
• Now p = [0, 0, 2, 2]

We have two components:

• Component 0: indices {0, 1}
• Component 2: indices {2, 3}

Step 3: Count Source Elements by Component

Processing source array [1, 2, 3, 4]:

• Index 0: source[0] = 1, find(0) = 0 → cnt[0][1] = 1
• Index 1: source[1] = 2, find(1) = 0 → cnt[0][2] = 1
• Index 2: source[2] = 3, find(2) = 2 → cnt[2][3] = 1
• Index 3: source[3] = 4, find(3) = 2 → cnt[2][4] = 1

Current state:

cnt[0] = {1: 1, 2: 1}  # Component 0 has one 1 and one 2
cnt[2] = {3: 1, 4: 1}  # Component 2 has one 3 and one 4

Step 4: Match with Target Elements

Processing target array [2, 1, 4, 5]:

• Index 0: target[0] = 2, find(0) = 0

  • cnt[0][2] = 1 - 1 = 0 (we have a 2 to match!)
  • 0 >= 0, so no increment to answer

• Index 1: target[1] = 1, find(1) = 0

  • cnt[0][1] = 1 - 1 = 0 (we have a 1 to match!)
  • 0 >= 0, so no increment to answer

• Index 2: target[2] = 4, find(2) = 2

  • cnt[2][4] = 1 - 1 = 0 (we have a 4 to match!)
  • 0 >= 0, so no increment to answer

• Index 3: target[3] = 5, find(3) = 2

  • cnt[2][5] = 0 - 1 = -1 (we don't have a 5 in this component!)
  • -1 < 0, so increment answer: ans = 1

Result: Minimum Hamming distance = 1

Why this works:

• In component 0 (indices 0,1), we have elements {1,2} in source and need {2,1} in target. Perfect match possible through swapping!
• In component 2 (indices 2,3), we have elements {3,4} in source but need {4,5} in target. We can match the 4, but we have a 3 where we need a 5, creating one mismatch.

The algorithm efficiently identifies that we can optimally rearrange to match everything except position 3, giving us the minimum Hamming distance of 1.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × α(n)) where n is the length of the arrays and α(n) is the inverse Ackermann function.

• The Union-Find operations (find and union) take O(α(n)) amortized time per operation due to path compression
• Processing allowedSwaps: For each swap pair [a, b], we perform two find operations and one union operation, resulting in O(m × α(n)) where m is the number of allowed swaps
• First loop through source array: O(n × α(n)) as we call find for each element and update the counter
• Second loop through target array: O(n × α(n)) as we call find for each element and update the counter
• Overall: O((m + n) × α(n)), which simplifies to O(n × α(n)) when m ≤ n

Space Complexity: O(n)

• Parent array p: O(n) space
• Counter dictionary cnt: In the worst case, stores up to n elements distributed across different components, resulting in O(n) space
• Other variables use O(1) space
• Total space complexity: O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Union-Find Implementation Without Path Compression

Problem: A common mistake is implementing the find function without path compression or implementing it incorrectly:

# Incorrect - No path compression
def find(x):
    while p[x] != x:
        x = p[x]
    return x

# Incorrect - Wrong path compression
def find(x):
    if p[x] != x:
        return find(p[x])  # Doesn't update p[x]
    return p[x]

Without proper path compression, the Union-Find operations can degrade to O(n) time complexity in the worst case, making the overall solution inefficient for large inputs.

Solution: Always implement path compression by updating the parent pointer during the recursive call:

def find(x):
    if p[x] != x:
        p[x] = find(p[x])  # Update parent to root directly
    return p[x]

Pitfall 2: Misunderstanding the Matching Logic

Problem: Some might try to match elements greedily position by position without considering the entire component:

# Incorrect approach
ans = 0
for i in range(n):
    root = find(i)
    if source[i] != target[i]:
        # Try to find target[i] in the same component
        # This doesn't guarantee optimal matching!
        ans += 1

This approach fails because it doesn't account for the fact that we need to optimally match ALL elements within a component simultaneously.

Solution: Use the frequency counting approach where we track available elements in each component and consume them as needed:

# Correct approach - tracks availability across the entire component
for i, x in enumerate(target):
    j = find(i)
    cnt[j][x] -= 1
    ans += cnt[j][x] < 0  # Only count if we've exhausted this value

Pitfall 3: Not Handling Empty allowedSwaps Array

Problem: If allowedSwaps is empty, each index is its own component. Some implementations might not handle this edge case properly, especially if they assume swaps always exist.

Solution: The Union-Find initialization naturally handles this case:

parent = list(range(n))  # Each index starts as its own component
# If allowedSwaps is empty, the loop doesn't execute
for a, b in allowedSwaps:
    parent[find(a)] = find(b)

Pitfall 4: Using Wrong Data Structure for Frequency Counting

Problem: Using a simple dictionary instead of defaultdict(Counter) can lead to KeyError exceptions:

# Incorrect - prone to KeyError
cnt = {}
for i, x in enumerate(source):
    j = find(i)
    if j not in cnt:
        cnt[j] = {}
    if x not in cnt[j]:
        cnt[j][x] = 0
    cnt[j][x] += 1

Solution: Use defaultdict(Counter) for cleaner and safer code:

cnt = defaultdict(Counter)
for i, x in enumerate(source):
    j = find(i)
    cnt[j][x] += 1  # Automatically handles missing keys

Pitfall 5: Confusing Component ID with Array Index

Problem: Some might incorrectly use the array index directly instead of finding its component root:

# Incorrect - uses index directly instead of component root
for i, x in enumerate(source):
    cnt[i][x] += 1  # Should be cnt[find(i)][x] += 1

This completely breaks the component grouping logic.

Solution: Always use find(i) to get the component ID:

for i, x in enumerate(source):
    j = find(i)  # Get component root first
    cnt[j][x] += 1