You are given an array nums of positive integers. Your task:

Return the size of the largest connected component, where two numbers are connected if they share a common factor greater than 1.

Example:

Input:  [4,6,15,35]
Output: 4
Explanation:
4 and 6 share factor 2
6 and 15 share factor 3
15 and 35 share factor 5
So all are connected

Another example:

Input: [20,50,9,63]
Output: 2
Explanation:
20 and 50 share factor 10
9 and 63 share factor 9
So two separate components of size 2

---

Problem Understanding

Two numbers belong to the same connected component if:

• They share a common factor > 1, OR
• They are indirectly connected through other numbers

This means it’s not enough to check pairwise adjacency. Instead:

If A shares factor with B, and B shares factor with C,
then A, B, C belong to same component

Important observations:

• Numbers can be as large as 100,000
• nums length can be up to 20,000
• Pairwise factor checking would be too slow (O(n² log n))

We need a more efficient approach.

---

Logic Explained in Simple English

The best way to think about this problem:

Step 1: Treat each number as a node

We want to group numbers that share factors.

Step 2: Use factors to connect numbers

For each number:

• Find all of its prime factors
• Any two numbers that share a factor must belong to the same group

Step 3: Use Union-Find (Disjoint Set Union)

Why DSU?

• It efficiently merges sets
• It quickly finds component sizes
• It supports transitive connectivity

Step 4: Track how many numbers end up in each connected component

The component with the largest count is the answer.

Why this works:

• We avoid O(n²) pair checking
• We use factor mapping instead
• Union-Find ensures efficiency and correctness

---

Step-by-Step Approach

1. Find the maximum number in nums
2. Initialize DSU up to max number
3. For each number in nums:
   • Factorize it
   • For each factor, union number with factor
4. After unions, compute frequency of each root parent
5. Return the maximum frequency

Factorization approach:

For number x:

• Try divisors from 2 to sqrt(x)
• If divisor divides x, record both divisor and x/divisor

---

Java Implementation

class Solution {

    public int largestComponentSize(int[] nums) {
        int max = 0;
        for (int num : nums) max = Math.max(max, num);
        
        UnionFind uf = new UnionFind(max + 1);

        for (int num : nums) {
            for (int factor = 2; factor * factor <= num; factor++) {
                if (num % factor == 0) {
                    uf.union(num, factor);
                    uf.union(num, num / factor);
                }
            }
        }

        Map<Integer, Integer> countMap = new HashMap<>();
        int result = 0;

        for (int num : nums) {
            int root = uf.find(num);
            int count = countMap.getOrDefault(root, 0) + 1;
            countMap.put(root, count);
            result = Math.max(result, count);
        }

        return result;
    }

    private static class UnionFind {
        int[] parent;
        int[] rank;

        UnionFind(int size) {
            parent = new int[size];
            rank = new int[size];
            for (int i = 0; i < size; i++) parent[i] = i;
        }

        int find(int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        }

        void union(int a, int b) {
            int rootA = find(a);
            int rootB = find(b);
            if (rootA == rootB) return;

            if (rank[rootA] < rank[rootB]) {
                parent[rootA] = rootB;
            } else if (rank[rootB] < rank[rootA]) {
                parent[rootB] = rootA;
            } else {
                parent[rootB] = rootA;
                rank[rootA]++;
            }
        }
    }
}

---

Dry Run Example

Input:

nums = [20,50,9,63]

Step 1: Factor numbers

20 → factors: 2, 4, 5, 10
50 → factors: 2, 5, 10, 25
9 → factors: 3
63 → factors: 3, 7, 9, 21

Step 2: Union based on shared factors

20 unions with factors → links to 50
9 unions with factors → links to 63

Step 3: Component grouping

Component 1: [20, 50] → size 2
Component 2: [9, 63] → size 2

Final result:

2

---

Time and Space Complexity

Time Complexity

O(n * sqrt(maxNum))

Because factorization dominates runtime.

Space Complexity

O(maxNum)

Due to DSU array sizes.

---

Common Mistakes and How to Avoid Them

Mistake 1: Checking all number pairs

This leads to O(n²) and will time out.

Mistake 2: Treating full factor lists as edges

Prime factorization is enough.

Mistake 3: Forgetting transitive connectivity

Must use DSU to merge indirect groups.

Mistake 4: Thinking numbers must be adjacent in array

Ordering does not matter.

Mistake 5: Missing frequencies from roots

Must count component sizes after unions.