GCD Sort of an Array LeetCode solution in Java

1
class Solution {
2
  private static final int[] primes;
3

4
  // precompute prime numbers
5
  static {
6
    primes = new int[5133];
7
    final int max = 100000 / 2;
8
    boolean[] notprime = new boolean[max];
9
    for (int index = 0, i = 2; i < max; i++) {
10
      if (notprime[i]) continue;
11
      primes[index++] = i;
12
      for (int j = (max - 1) / i; j >= 2; j--) notprime[i * j] = true;
13
    }
14
  }
15

16
  public boolean gcdSort(int[] nums) {
17
    final var sorted = nums.clone();
18
    Arrays.sort(sorted);
19
    final int len = nums.length, max = sorted[len - 1];
20
    final int[] map = new int[max + 1]; // grouping tree child->parent
21
    for (int i = 0; i < len; i++) map[nums[i]] = nums[i];
22

23
    for (final var p : primes) {
24
      if (p > max / 2) break;
25
      int group = p;
26
      map[p] = p;
27
      for (int num = p + p; num <= max; num += p) {
28
        var existing = map[num];
29
        if (existing == 0) continue; // value doens't exist in array
30
        if (existing == num) map[num] = group; // 1st hit, set group, otherwise, group merging
31
        else if ((existing = root(map, existing)) < group) {
32
          map[group] = existing;
33
          group = existing;
34
        } else map[existing] = group;
35
      }
36
    }
37

38
    for (int i = 0; i < len; i++) if (root(map, nums[i]) != root(map, (sorted[i]))) return false;
39
    return true;
40
  }
41

42
  private static int root(int[] map, int num) {
43
    int group;
44
    while (num != (group = map[num])) num = group;
45
    return group;
46
  }
47
}