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 _theminimum Hamming distance of _source andtarget _after performingany amount of swap operations on array _source .

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4

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

1
2

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^5
  • 1 <= source[i], target[i] <= 10^5
  • 0 <= allowedSwaps.length <= 10^5
  • allowedSwaps[i].length == 2
  • 0 <= ai, bi <= n - 1
  • ai != bi

Solution

Method 1 – Union-Find and Frequency Matching

Intuition

Allowed swaps form connected components in the array. Within each component, any permutation is possible, so we can match as many elements as possible between source and target in each component. The minimum Hamming distance is the number of unmatched elements after optimal matching in each component.

Approach

  1. Use Union-Find to group indices that can be swapped.
  2. For each component, collect the values from source and target at those indices.
  3. Count the frequency of each value in both lists.
  4. For each value, match as many as possible between source and target (using min of the counts).
  5. The minimum Hamming distance is the total number of indices minus the total matches.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
        int n = source.size();
        vector<int> parent(n);
        iota(parent.begin(), parent.end(), 0);
        function<int(int)> find = [&](int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); };
        for (auto& s : allowedSwaps) {
            parent[find(s[0])] = find(s[1]);
        }
        unordered_map<int, vector<int>> groups;
        for (int i = 0; i < n; ++i) groups[find(i)].push_back(i);
        int ans = 0;
        for (auto& [_, idxs] : groups) {
            unordered_map<int, int> freq;
            for (int i : idxs) freq[source[i]]++;
            for (int i : idxs) {
                if (freq[target[i]]) freq[target[i]]--;
                else ans++;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

func minimumHammingDistance(source, target []int, allowedSwaps [][]int) int {
    n := len(source)
    parent := make([]int, n)
    for i := range parent { parent[i] = i }
    var find func(int) int
    find = func(x int) int {
        if parent[x] != x { parent[x] = find(parent[x]) }
        return parent[x]
    }
    for _, s := range allowedSwaps {
        parent[find(s[0])] = find(s[1])
    }
    groups := map[int][]int{}
    for i := 0; i < n; i++ {
        root := find(i)
        groups[root] = append(groups[root], i)
    }
    ans := 0
    for _, idxs := range groups {
        freq := map[int]int{}
        for _, i := range idxs { freq[source[i]]++ }
        for _, i := range idxs {
            if freq[target[i]] > 0 {
                freq[target[i]]--
            } else {
                ans++
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
        int n = source.length;
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        for (int[] s : allowedSwaps) parent[find(parent, s[0])] = find(parent, s[1]);
        Map<Integer, List<Integer>> groups = new HashMap<>();
        for (int i = 0; i < n; i++) groups.computeIfAbsent(find(parent, i), k -> new ArrayList<>()).add(i);
        int ans = 0;
        for (List<Integer> idxs : groups.values()) {
            Map<Integer, Integer> freq = new HashMap<>();
            for (int i : idxs) freq.put(source[i], freq.getOrDefault(source[i], 0) + 1);
            for (int i : idxs) {
                if (freq.getOrDefault(target[i], 0) > 0) freq.put(target[i], freq.get(target[i]) - 1);
                else ans++;
            }
        }
        return ans;
    }
    private int find(int[] parent, int x) {
        if (parent[x] != x) parent[x] = find(parent, parent[x]);
        return parent[x];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    fun minimumHammingDistance(source: IntArray, target: IntArray, allowedSwaps: Array<IntArray>): Int {
        val n = source.size
        val parent = IntArray(n) { it }
        fun find(x: Int): Int {
            if (parent[x] != x) parent[x] = find(parent[x])
            return parent[x]
        }
        for (s in allowedSwaps) parent[find(s[0])] = find(s[1])
        val groups = mutableMapOf<Int, MutableList<Int>>()
        for (i in 0 until n) groups.getOrPut(find(i)) { mutableListOf() }.add(i)
        var ans = 0
        for (idxs in groups.values) {
            val freq = mutableMapOf<Int, Int>()
            for (i in idxs) freq[source[i]] = freq.getOrDefault(source[i], 0) + 1
            for (i in idxs) {
                if (freq.getOrDefault(target[i], 0) > 0) freq[target[i]] = freq[target[i]]!! - 1
                else ans++
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def minimum_hamming_distance(source: list[int], target: list[int], allowed_swaps: list[list[int]]) -> int:
    n = len(source)
    parent = list(range(n))
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    for a, b in allowed_swaps:
        parent[find(a)] = find(b)
    groups = {}
    for i in range(n):
        root = find(i)
        groups.setdefault(root, []).append(i)
    ans = 0
    for idxs in groups.values():
        freq = {}
        for i in idxs:
            freq[source[i]] = freq.get(source[i], 0) + 1
        for i in idxs:
            if freq.get(target[i], 0):
                freq[target[i]] -= 1
            else:
                ans += 1
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

impl Solution {
    pub fn minimum_hamming_distance(source: Vec<i32>, target: Vec<i32>, allowed_swaps: Vec<Vec<i32>>) -> i32 {
        let n = source.len();
        let mut parent: Vec<usize> = (0..n).collect();
        fn find(parent: &mut Vec<usize>, x: usize) -> usize {
            if parent[x] != x {
                parent[x] = find(parent, parent[x]);
            }
            parent[x]
        }
        for s in allowed_swaps.iter() {
            let a = find(&mut parent, s[0] as usize);
            let b = find(&mut parent, s[1] as usize);
            parent[a] = b;
        }
        use std::collections::HashMap;
        let mut groups: HashMap<usize, Vec<usize>> = HashMap::new();
        for i in 0..n {
            let root = find(&mut parent, i);
            groups.entry(root).or_default().push(i);
        }
        let mut ans = 0;
        for idxs in groups.values() {
            let mut freq = std::collections::HashMap::new();
            for &i in idxs {
                *freq.entry(source[i]).or_insert(0) += 1;
            }
            for &i in idxs {
                let cnt = freq.entry(target[i]).or_insert(0);
                if *cnt > 0 {
                    *cnt -= 1;
                } else {
                    ans += 1;
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    minimumHammingDistance(source: number[], target: number[], allowedSwaps: number[][]): number {
        const n = source.length;
        const parent = Array.from({ length: n }, (_, i) => i);
        function find(x: number): number {
            if (parent[x] !== x) parent[x] = find(parent[x]);
            return parent[x];
        }
        for (const [a, b] of allowedSwaps) parent[find(a)] = find(b);
        const groups: Record<number, number[]> = {};
        for (let i = 0; i < n; ++i) {
            const root = find(i);
            if (!groups[root]) groups[root] = [];
            groups[root].push(i);
        }
        let ans = 0;
        for (const idxs of Object.values(groups)) {
            const freq: Record<number, number> = {};
            for (const i of idxs) freq[source[i]] = (freq[source[i]] ?? 0) + 1;
            for (const i of idxs) {
                if (freq[target[i]]) freq[target[i]]--;
                else ans++;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n + m), where n is the array length and m is the number of allowed swaps.
  • 🧺 Space complexity: O(n), for union-find and frequency maps.