Minimize Hamming Distance After Swap Operations LeetCode solution in Java

1
class Solution {
2
  public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
3
    int[] line = new int[source.length];
4
    Arrays.fill(line, 100001);
5
    for (int[] swap : allowedSwaps) {
6
      int root0 = getRoot(line, swap[0]);
7
      int root1 = getRoot(line, swap[1]);
8
      int min = Integer.min(root0, root1);
9
      line[root0] = min;
10
      line[root1] = min;
11
      // for speed up
12
      line[swap[0]] = min;
13
      line[swap[1]] = min;
14
    }
15
    HashMap<Integer, HashMap<Integer, Integer>> pool = new HashMap<>();
16
    int different = 0;
17
    int noSwap = 0;
18
    for (int i = 0; i < line.length; i++) {
19
      if (line[i] == 100001) {
20
        if (source[i] != target[i]) {
21
          // not allow swap distance
22
          noSwap++;
23
        }
24
        continue;
25
      }
26
      Integer root = getRoot(line, i);
27
      if (!pool.containsKey(root)) {
28
        pool.put(root, new HashMap<>());
29
      }
30
      HashMap<Integer, Integer> freq = pool.get(root);
31
      freq.put(source[i], freq.getOrDefault(source[i], 0) + 1);
32
      freq.put(target[i], freq.getOrDefault(target[i], 0) - 1);
33
    }
34
    for (HashMap<Integer, Integer> freq : pool.values()) {
35
      for (Integer value : freq.values()) {
36
        different += Math.abs(value);
37
      }
38
    }
39
    // two different number mean one hamming distance
40
    return different / 2 + noSwap;
41
  }
42

43
  private int getRoot(int[] line, int index) {
44
    if (line[index] == 100001) {
45
      line[index] = index;
46
      return index;
47
    }
48
    if (line[index] == index) {
49
      return index;
50
    }
51
    return getRoot(line, line[index]);
52
  }
53
}