Easy Approach and Easy to Understand(90% Beat) 😊😊
Approach & IntuitionThe problem requires us to find the largest connected component in an array where two numbers are connected if they share a common factor >
# Approach & Intuition
The problem requires us to find the largest connected component in an array where two numbers are connected if they share a common factor > 1.
A brute-force approach would check all pairwise GCDs, leading to O(N² log M) complexity. Instead, this solution leverages Union-Find with prime factorization, optimizing it to O(N log M + M).

# Optimized Approach
1️⃣ Understanding the Connection Rule
* Two numbers belong to the same component if they share at least one prime factor.
* Instead of checking all pairs, we map numbers to their prime factors.
* If two numbers share a factor, they are unioned in the Disjoint Set 
Union (DSU).

2️⃣ Using Union-Find for Efficient Grouping
1. Union-Find (Disjoint Set Union, DSU) helps efficiently merge components.
2. Path compression and union by size ensure near-constant time operations.

Union-Find Structure
```java []
private class unionFind {
    int maxSize;
    int[] parent;
    int[] size;
    
    public unionFind(int n) {
        maxSize = 1;
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public int findParent(int num) {
        if (parent[num] != num) {
            parent[num] = findParent(parent[num]); // Path compression
        }
        return parent[num];
    }

    public void union(int num1, int num2) {
        int prt1 = findParent(num1);
        int prt2 = findParent(num2);
        if (prt1 != prt2) {
            if (size[prt1] > size[prt2]) {
                parent[prt2] = prt1;
                size[prt1] += size[prt2];
                maxSize = Math.max(maxSize, size[prt1]);
            } else {
                parent[prt1] = prt2;
                size[prt2] += size[prt1];
                maxSize = Math.max(size[prt2], maxSize);
            }
        }
    }
}
```
* Each number starts as its own parent.
* findParent() applies path compression for efficiency.
* union() merges smaller components into larger ones.

3️⃣ Efficiently Finding Prime Factors
* Instead of checking GCD of all pairs, we factorize each number.
* A HashMap (factorStore) stores which number first introduced a prime factor.
* If another number shares the same factor, we union them.

Prime Factorization Function
```java []
public List<Integer> primeFactorFinder(int num) {
    int n = num;
    List<Integer> factor = new ArrayList<>();
    for (int i = 2; i * i <= n; i++) { // Trial division method
        if (n % i == 0) {
            factor.add(i);
            while (n % i == 0) {
                n /= i;
            }
        }
    }
    if (n > 1) { // If n is prime
        factor.add(n);
    }
    return factor;
}
```
* Extracts prime factors efficiently in O(log M).
* If a factor repeats, it's only stored once (removes duplicate contributions).

4️⃣ Connecting Numbers via Prime Factors
* Each number is connected based on its prime factors.
* We use a HashMap (factorStore) to track the first occurrence of a prime factor.
* If another number shares the same factor, we union them.
Building the Union-Find Structure
``` java []
public int largestComponentSize(int[] nums) {
    int len = nums.length;
    unionFind unionFind = new unionFind(len);
    HashMap<Integer, Integer> factorStore = new HashMap<>();

    for (int i = 0; i < len; i++) {
        for (Integer factor : primeFactorFinder(nums[i])) {
            if (!factorStore.containsKey(factor)) {
                factorStore.put(factor, i);  // Store first occurrence of factor
            } else {
                unionFind.union(factorStore.get(factor), i); // Union with previous index
            }
        }
    }
    return unionFind.maxSize;
}
```
# Complexity Analysis
Step ---------------------------- Complexity
Prime Factorization	---------------------------- O(N log M)
Union-Find Operations ---------------------------- O(α(N)) ≈ O(1)
Overall Complexity ----------------------------	O(N log M + M)
✅ Optimized from O(N² log M) to O(N log M + M)! 🚀
✅ Handles large constraints efficiently.

# Key Takeaways
✔ Union-Find + Prime Factorization efficiently groups connected numbers.
✔ Avoids unnecessary GCD checks by mapping numbers to their prime factors.
✔ Uses factorStore HashMap to track first occurrence of each factor.
✔ Path compression & union by size make DSU operations nearly O(1).

This is the most optimal approach while keeping the same intuitive connection rule. 🚀

# Code
```java []
class Solution {
    private class unionFind{
        int maxSize;
        int[] parent;
        int[] size;
        public unionFind(int n){
            maxSize = 1;
            parent = new int[n];
            size = new int[n];
            for(int i = 0;i < n;i++){
                parent[i] = i;
                size[i] = 1;
            }
        }
        public int findParent(int num){
            if(num == parent[num]){
                return num;
            }
            int val = findParent(parent[num]);
            return parent[num] = val;
        }
        public void union(int num1, int num2){
            int prt1 = findParent(num1);
            int prt2 = findParent(num2);
            if(prt1 != prt2){
                if(size[prt2] > size[prt1]){
                    parent[prt2] = prt1;
                    size[prt1] += size[prt2];
                    maxSize = Math.max(maxSize, size[prt1]);
                }
                else{
                    parent[prt1] = prt2;
                    size[prt2] += size[prt1];
                    maxSize = Math.max(size[prt2], maxSize);
                }
            }
        }
    }
    public int largestComponentSize(int[] nums) {
        int len = nums.length;
        unionFind unionFind = new unionFind(len);
        HashMap<Integer, Integer> factorStore = new HashMap<>();
        for(int i = 0;i < len;i++){
            for(Integer ele: primeFactorFinder(nums[i])){
                if(!factorStore.containsKey(ele)){
                    factorStore.put(ele, i);
                }
                else{
                    unionFind.union(factorStore.get(ele), i);
                }
            }
        }
        return unionFind.maxSize;
    }
    public List<Integer> primeFactorFinder(int num){
        int n = num;
        List<Integer> factor = new ArrayList<>();
        for(int i = 2;i*i <= n;i++){
            if(n%i == 0){
                factor.add(i);
                while(n%i == 0){
                    n/=i;
                }
            }
        }
        if(n > 1){
            factor.add(n);
        }
        return factor;
    }
}
```
['Array', 'Hash Table', 'Union Find', 'Number Theory', 'Java']