Minimize Hamming Distance After Swap Operations

Minimize Hamming Distance After Swap Operations - Problem

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.

Input & Output

Example 1 — Basic Swapping

$ Input: source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]]

› Output: 1

💡 Note: We can swap indices 0 and 1 to get [2,1,3,4]. This matches target at positions 0,1,2 but differs at position 3 (4 vs 5), giving Hamming distance = 1.

Example 2 — No Beneficial Swaps

$ Input: source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = [[0,1],[2,3]]

› Output: 2

💡 Note: Even with swaps [0,1] or [2,3], we cannot make source match target better than the original 2 mismatches at positions 1 and 2.

Example 3 — No Swaps Allowed

$ Input: source = [5,1,2,4,3], target = [1,5,4,2,3], allowedSwaps = []

› Output: 4

💡 Note: No swaps allowed, so Hamming distance is simply the count of differing positions: 4 out of 5 positions differ.

Constraints

n == source.length == target.length
1 ≤ n ≤ 10⁵
1 ≤ source[i], target[i] ≤ 10⁵
0 ≤ allowedSwaps.length ≤ 10⁵
allowedSwaps[i].length == 2
0 ≤ ai, bi ≤ n - 1
ai ≠ bi

Visualization

Tap to expand

Understanding the Visualization

Input

Two arrays and allowed swap pairs

Process

Group indices by connectivity and optimize matches

Output

Minimum possible Hamming distance

Key Takeaway

🎯 Key Insight: Connected indices through swaps form components where optimal matching can be achieved independently

Asked in

G Google 45 M Microsoft 38 a Amazon 32 f Facebook 28

The key insight is that indices connected by allowed swaps form components where elements can be freely rearranged. Use Union-Find to identify these components, then greedily match elements within each group. Time: O(m × α(n) + n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Union-Find (Optimal Solution)	O(m × α(n) + n)	O(n)	Group connected indices and optimize matching within each group
Brute Force - Try All Swap Combinations	O(2^m × n)	O(n)	Generate all possible arrangements through allowed swaps

Union-Find (Optimal Solution) — Algorithm Steps

Build Union-Find structure from allowed swaps
Group indices into connected components
For each component, count matching elements
Calculate minimum mismatches across all components

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Components

Use Union-Find to group connected indices

Count Elements

For each component, count source and target values

Calculate Matches

Greedily match common elements within each group

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 100000

int parent[MAX_N];

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

void unite(int x, int y) {
    int px = find(x), py = find(y);
    if (px != py) {
        parent[px] = py;
    }
}

int solution(int* source, int* target, int n, int** allowedSwaps, int swapCount) {
    // Initialize Union-Find
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }
    
    // Build connected components
    for (int s = 0; s < swapCount; s++) {
        unite(allowedSwaps[s][0], allowedSwaps[s][1]);
    }
    
    // Simple approach: count initial mismatches and see if swaps help
    int hammingDistance = 0;
    for (int i = 0; i < n; i++) {
        if (source[i] != target[i]) {
            // Check if there's a connected index j where source[j] == target[i] and target[j] == source[i]
            int canFix = 0;
            for (int j = 0; j < n; j++) {
                if (i != j && find(i) == find(j) && source[j] == target[i] && target[j] == source[i]) {
                    canFix = 1;
                    break;
                }
            }
            if (!canFix) {
                hammingDistance++;
            }
        }
    }
    
    return hammingDistance;
}

int main() {
    int source[] = {1, 2, 3, 4};
    int target[] = {2, 1, 4, 5};
    int* swaps[] = {(int[]){0, 1}, (int[]){2, 3}};
    
    printf("%d\n", solution(source, target, 4, swaps, 2));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × α(n) + n)

m union operations with inverse Ackermann function plus n to process elements

✓ Linear Growth

Space Complexity

O(n)

Union-Find parent array and component maps

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Union-Find (Optimal Solution) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler