Given nums[], consider a graph where two numbers are connected if they share a common factor > 1. Return the size of the largest connected component.
Input: [4,6,15,35] → Output: 4Input: [20,50,9,63] → Output: 2
Union each number with all its prime factors. Numbers sharing a factor will be in the same component.
- For each number: factorize it; union the number with each prime factor.
- Use a map to group numbers by their prime factors.
- Count the largest component using Union-Find.
import java.util.*;
class Solution {
int[] parent, size;
public int largestComponentSize(int[] nums) {
int max = Arrays.stream(nums).max().getAsInt();
parent = new int[max+1]; size = new int[max+1];
for (int i = 0; i <= max; i++) { parent[i]=i; size[i]=1; }
for (int num : nums) {
for (int f = 2; f * f <= num; f++) {
if (num % f == 0) { union(num, f); union(num, num/f); }
}
}
Map<Integer,Integer> compSize = new HashMap<>();
int res = 1;
for (int num : nums) {
int p = find(num);
compSize.merge(p, 1, Integer::sum);
res = Math.max(res, compSize.get(p));
}
return res;
}
private int find(int x) { return parent[x]==x?x:(parent[x]=find(parent[x])); }
private void union(int a, int b) {
int pa=find(a), pb=find(b);
if (pa!=pb) { parent[pa]=pb; }
}
}
- Time Complexity: O(N * sqrt(max))
- Space Complexity: O(max)