Largest Component Size by Common Factor

Problem Statement

Given an array nums consisting of unique positive integers, you are to imagine a graph where each integer in the array represents a node. Edges are formed between nodes nums[i] and nums[j] if and only if they share at least one common factor greater than 1. Your task is to determine the size of the largest connected component in this graph. A connected component in this context is a subset of nodes such that there is a path connecting any two nodes within this subset, and no such path exists between a node inside the subset and a node outside it.

Examples

Example 1

Input:

nums = [4,6,15,35]

Output:

4

Example 2

Input:

nums = [20,50,9,63]

Output:

2

Example 3

Input:

nums = [2,3,6,7,4,12,21,39]

Output:

8

Constraints

• 1 <= nums.length <= 2 * 104
• 1 <= nums[i] <= 105
• All the values of nums are unique.

Approach and Intuition

Idea and Initial Thoughts

When forming the problem into a graph:

• Each integer from the array nums is a node.
• An edge is created between two nodes if their corresponding numbers share any common factor greater than 1.

This problem involves identifying connected components which are groups of nodes that are directly or indirectly connected.

Steps to Solve the Problem

1. Mapping Numbers to Their Factors:

   • Generate all prime factors of each number and map each number to its set of prime factors.
   • This way, any two numbers sharing a prime factor will be connected.

2. Graph Construction:

   • Build an adjacency list where each node points to other nodes (numbers) that share at least one common factor with it.

3. Finding Connected Components:

   • Use graph traversal techniques such as Depth-First Search (DFS) or Breadth-First Search (BFS) to explore all nodes reachable from any given node.
   • Keep a count of the size of nodes visited during the traversal to determine the size of the connected component starting from that node.

4. Compute the Largest Component:

   • Traverse from each unvisited node, compute the size of the connected component, and update the maximum size found.

Intuition Behind Solution

The crux of the problem is to effectively find links (common factors) between the numbers. Since dividing numbers to find commonality is computationally expensive for larger arrays, transforming the problem into a graph and using tried-and-true techniques for component identification simplifies the complexity.

Example Analyses from Given Examples

• Example 1: Input: [4, 6, 15, 35]
  • All numbers are interconnected through various common factors e.g., 2 between 4 and 6, 3 between 6 and 15, 5 between 15 and 35, hence all are part of a single component of size 4.
• Example 2: Input: [20, 50, 9, 63]
  • Here, 20 and 50 share the factor 10. 9 and 63 share the factor 3. Thus there are two components, the largest being of size 2.
• Example 3: Input: [2, 3, 6, 7, 4, 12, 21, 39]
  • Each number has a connection to another through multiple factors directly or indirectly, forming a single component of size 8.

This method provides a systematic approach to tackling the problem, leveraging the properties of graph theory and number theory to determine the structure and characteristics of the dataset represented by nums.

Solutions

class Solution {

    public int maxComponentSize(int[] nums) {
        int highestValue = Arrays.stream(nums).max().getAsInt();
        UnionFind uf = new UnionFind(highestValue);

        HashMap<Integer, Integer> factorRootMap = new HashMap<>();

        for (int num : nums) {
            List<Integer> primes = new ArrayList<>(new HashSet<>(decomposePrimes(num)));

            factorRootMap.put(num, primes.get(0));
            for (int i = 0; i < primes.size() - 1; i++) {
                uf.merge(primes.get(i), primes.get(i + 1));
            }
        }

        int largestSize = 0;
        HashMap<Integer, Integer> sizeMap = new HashMap<>();
        for (int num : nums) {
            int root = uf.findRoot(factorRootMap.get(num));
            int cnt = sizeMap.getOrDefault(root, 0) + 1;
            sizeMap.put(root, cnt);
            largestSize = Math.max(largestSize, cnt);
        }

        return largestSize;
    }

    protected List<Integer> decomposePrimes(int number) {
        List<Integer> factors = new ArrayList<>();
        int current = 2;
        while (number >= current * current) {
            if (number % current == 0) {
                factors.add(current);
                number /= current;
            } else {
                current++;
            }
        }
        factors.add(number);
        return factors;
    }

}

class UnionFind {
    private int[] root;
    private int[] componentSize;

    public UnionFind(int max) {
        root = new int[max + 1];
        componentSize = new int[max + 1];
        for (int i = 0; i <= max; i++) {
            root[i] = i;
            componentSize[i] = 1;
        }
    }

    public int findRoot(int element) {
        if (root[element] != element) {
            root[element] = findRoot(root[element]);
        }
        return root[element];
    }

    public int merge(int x, int y) {
        int rootX = findRoot(x);
        int rootY = findRoot(y);

        if (rootX == rootY) {
            return rootX;
        }

        if (componentSize[rootX] < componentSize[rootY]) {
            root[rootX] = rootY;
            componentSize[rootY] += componentSize[rootX];
        } else {
            root[rootY] = rootX;
            componentSize[rootX] += componentSize[rootY];
        }
        return rootY;
    }
}