LargestComponentSizeByCommonFactor.java

// https://leetcode.com/problems/largest-component-size-by-common-factor
// N = nums, M = max(N)
// T: O(M + N sqrt(M) al(M) + N al(N)) al = inverse Ackermann function
// S: O(M + N)

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class LargestComponentSizeByCommonFactor {
    private static final class DisjointSet {
        private final int[] root, rank;

        public DisjointSet(int size) {
            root = new int[size];
            rank = new int[size];
            for (int i = 0 ; i < size ; i++) {
                root[i] = i;
                rank[i] = 1;
            }
        }

        public int find(int num) {
            if (num == root[num]) {
                return num;
            }
            return root[num] = find(root[num]);
        }

        public boolean areConnected(int x, int y) {
            return find(x) == find(y);
        }

        public void union(int x, int y) {
            final int rootX = find(x), rootY = find(y);
            if (rootX == rootY) {
                return;
            }
            if (rank[rootX] > rank[rootY]) {
                root[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                root[rootY] = rootX;
            } else {
                root[rootY] = rootX;
                rank[rootX]++;
            }
        }

        public int size() {
            return root.length;
        }
    }

    public int largestComponentSize(int[] nums) {
        final int maxValue = Arrays.stream(nums).max().getAsInt();
        final DisjointSet disjointSet = new DisjointSet(maxValue + 1);
        for (int number : nums) {
            for (int i = 2 ; i * i <= number ; i++) {
                if (number % i == 0) {
                    disjointSet.union(number, i);
                    disjointSet.union(number, number/ i);
                }
            }
        }
        return largestComponentSize(disjointSet, nums);
    }

    private static int largestComponentSize(DisjointSet disjointSet, int[] numbers) {
        final Map<Integer, Integer> rootFrequencies = new HashMap<>();
        int maxSize = 1;
        for (int number : numbers) {
            final int root = disjointSet.find(number);
            rootFrequencies.put(root, rootFrequencies.getOrDefault(root, 0) + 1);
            maxSize = Math.max(maxSize, rootFrequencies.get(root));
        }
        return maxSize;
    }
}