Minimize Hamming Distance After Swap Operations

Medium
1528.

Minimize Hamming Distance After Swap Operations

Minimize Hamming Distance After Swap Operations is a medium coding problem on arrays, depth-first search and union find, asked in Amazon and Google interviews.

You are given two integer arrays source and target of the same length n, and a list allowedSwaps where allowedSwaps[i] = [ai, bi] lets you swap the elements at indices ai and bi of source. Each allowed swap may be used any number of times, in any order.

The Hamming distance of two equal-length arrays is the number of indices i where they differ.

Return the smallest Hamming distance between source and target you can reach after performing any sequence of allowed swaps on source.

Example 1

Input
source = [5,1,2,4], target = [1,5,4,3], allowedSwaps = [[0,1],[2,3]]
Output
1
Explanation
Swap indices 0, 1 and then 2, 3 to get `[1,5,4,2]`; only index 3 still differs.

Example 2

Input
source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = []
Output
2

Example 3

Input
source = [3,1,2,2,5], target = [2,3,5,2,1], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]]
Output
0
Explanation
All indices are linked, so `source` can be rearranged freely into `target`.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} source
 * @param {number[]} target
 * @param {number[][]} allowedSwaps
 * @return {number}
 */
var minimumHammingDistance = function(source, target, allowedSwaps) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimize Hamming Distance After Swap Operations — Solution

Minimize Hamming Distance After Swap Operations solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimize Hamming Distance After Swap Operations is a medium coding problem on arrays, depth-first search and union find, asked in Amazon and Google interviews.

Problem statement

You are given two integer arrays source and target of the same length n, and a list allowedSwaps where allowedSwaps[i] = [ai, bi] lets you swap the elements at indices ai and bi of source. Each allowed swap may be used any number of times, in any order.

The Hamming distance of two equal-length arrays is the number of indices i where they differ.

Return the smallest Hamming distance between source and target you can reach after performing any sequence of allowed swaps on source.

Example 1

Input: source = [5,1,2,4], target = [1,5,4,3], allowedSwaps = [[0,1],[2,3]]
Output: 1
Explanation: Swap indices 0, 1 and then 2, 3 to get `[1,5,4,2]`; only index 3 still differs.

Example 2

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

Example 3

Input: source = [3,1,2,2,5], target = [2,3,5,2,1], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]]
Output: 0
Explanation: All indices are linked, so `source` can be rearranged freely into `target`.

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

Hints for Minimize Hamming Distance After Swap Operations

  1. Hint 1

    If index a can swap with b, and b with c, then the values at a, b and c can be arranged in any order.

  2. Hint 2

    So the swaps split the indices into groups (connected components); inside a group the values of source can be permuted freely.

  3. Hint 3

    Per group, count how many values of source can be matched with equal values of target at the group's indices; everything unmatched adds to the distance.

How to solve Minimize Hamming Distance After Swap Operations

Allowed swaps connect indices; within a connected group any permutation is reachable, so each group contributes size − (multiset overlap of its source and target values).

Approach

  1. Union the two indices of every allowed swap in a union-find.
  2. For each index i, add the pair (root(i), source[i]) to a counter.
  3. For each index i, look up (root(i), target[i]): if the counter is positive, decrement it (a match); otherwise the index will stay different, so add 1 to the answer.

Why it works

Transpositions along the edges of a connected graph generate every permutation of its vertices, so inside a component the source values can be placed anywhere. The best placement then matches as many target values as the two multisets have in common, which the greedy counter computes exactly; components are independent of each other.

Complexity

  • Time — O((n + s) · α(n))
  • Space — O(n)

Pitfalls

  • Swaps are transitive — handling each listed pair in isolation undercounts what can be rearranged.
  • Key the counter by component and value; a value matching in a different component does not count.
  • allowedSwaps may be empty: then the answer is the plain Hamming distance.

Reference solution

Python

from typing import List
from collections import Counter

def minimumHammingDistance(source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:
    n = len(source)
    root = list(range(n))

    def find(x):
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    for a, b in allowedSwaps:
        ra, rb = find(a), find(b)
        if ra != rb:
            root[ra] = rb
    count = Counter()
    for i in range(n):
        count[(find(i), source[i])] += 1
    dist = 0
    for i in range(n):
        key = (find(i), target[i])
        if count[key] > 0:
            count[key] -= 1
        else:
            dist += 1
    return dist

Java

public static int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
    int n = source.length;
    int[] root = new int[n];
    for (int i = 0; i < n; i++) root[i] = i;
    for (int[] s : allowedSwaps) {
        int ra = mhFind(root, s[0]), rb = mhFind(root, s[1]);
        if (ra != rb) root[ra] = rb;
    }
    Map<Long, Integer> count = new HashMap<>();
    for (int i = 0; i < n; i++) count.merge((long) mhFind(root, i) * 100001L + source[i], 1, Integer::sum);
    int dist = 0;
    for (int i = 0; i < n; i++) {
        long key = (long) mhFind(root, i) * 100001L + target[i];
        Integer c = count.get(key);
        if (c != null && c > 0) count.put(key, c - 1);
        else dist++;
    }
    return dist;
}

static int mhFind(int[] root, int x) {
    while (root[x] != x) { root[x] = root[root[x]]; x = root[x]; }
    return x;
}

C++

static int mhFind(vector<int>& root, int x) {
    while (root[x] != x) { root[x] = root[root[x]]; x = root[x]; }
    return x;
}

int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
    int n = source.size();
    vector<int> root(n);
    for (int i = 0; i < n; i++) root[i] = i;
    for (auto& s : allowedSwaps) {
        int ra = mhFind(root, s[0]), rb = mhFind(root, s[1]);
        if (ra != rb) root[ra] = rb;
    }
    unordered_map<long long, int> count;
    for (int i = 0; i < n; i++) count[(long long)mhFind(root, i) * 100001LL + source[i]]++;
    int dist = 0;
    for (int i = 0; i < n; i++) {
        long long key = (long long)mhFind(root, i) * 100001LL + target[i];
        auto it = count.find(key);
        if (it != count.end() && it->second > 0) it->second--;
        else dist++;
    }
    return dist;
}

JavaScript

var minimumHammingDistance = function(source, target, allowedSwaps) {
    var n = source.length;
    var root = [];
    for (var i = 0; i < n; i++) root.push(i);
    var find = function(x) {
        while (root[x] !== x) { root[x] = root[root[x]]; x = root[x]; }
        return x;
    };
    for (var s = 0; s < allowedSwaps.length; s++) {
        var ra = find(allowedSwaps[s][0]), rb = find(allowedSwaps[s][1]);
        if (ra !== rb) root[ra] = rb;
    }
    var count = new Map();
    for (var j = 0; j < n; j++) {
        var key = find(j) * 100001 + source[j];
        count.set(key, (count.get(key) || 0) + 1);
    }
    var dist = 0;
    for (var k = 0; k < n; k++) {
        var key2 = find(k) * 100001 + target[k];
        var c = count.get(key2) || 0;
        if (c > 0) count.set(key2, c - 1);
        else dist++;
    }
    return dist;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Depth-First Search (DFS)