# Largest Component Size by Common Factor
**Difficulty:** HARD
[External](https://leetcode.com/problems/largest-component-size-by-common-factor)
Canonical: https://scaleengineer.com/dsa/problems/largest-component-size-by-common-factor
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Algorithms:** [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Hash Table
---
## Problem
You are given an integer array of unique positive integers `nums`. Consider the following graph:

* There are `nums.length` nodes, labeled `nums[0]` to `nums[nums.length - 1]`,
* There is an undirected edge between `nums[i]` and `nums[j]` if `nums[i]` and `nums[j]` share a common factor greater than `1`.

Return _the size of the largest connected component in the graph_.

**Example 1:**

![](https://assets.glich.co/dsa/largest-component-size-by-common-factor/image0.png) 

**Input:** nums = [4,6,15,35]
**Output:** 4

**Example 2:**

![](https://assets.glich.co/dsa/largest-component-size-by-common-factor/image1.png) 

**Input:** nums = [20,50,9,63]
**Output:** 2

**Example 3:**

![](https://assets.glich.co/dsa/largest-component-size-by-common-factor/image2.png) 

**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**.

# Approaches
## Brute-Force Graph Construction and Traversal
This approach directly translates the problem statement into a graph data structure. It builds an explicit graph where nodes are the numbers from the input array. An edge is added between two nodes if their corresponding numbers share a common factor greater than 1. After building the graph, a standard graph traversal algorithm like Depth-First Search (DFS) or Breadth-First Search (BFS) is used to find the sizes of all connected components.
**Time:** O(N^2 * log(M)), where N is the length of `nums` and M is the maximum value in `nums`. Building the graph requires checking `O(N^2)` pairs, and each check involves a GCD calculation which takes `O(log(M))` time. The subsequent graph traversal is dominated by the graph construction time. · **Space:** O(N^2), where N is the number of elements in `nums`. This is for storing the adjacency list, which can have up to `O(N^2)` edges in a dense graph.
**Pros:** Simple to understand and directly follows the problem definition.
**Cons:** Inefficient for the given constraints. `N^2` operations are too slow.; The space complexity can be very high, up to `O(N^2)`, if the graph is dense.; This approach will likely result in a "Time Limit Exceeded" or "Memory Limit Exceeded" error on competitive programming platforms.
### Explanation
```java
class Solution {
    public int largestComponentSize(int[] nums) {
        int n = nums.length;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (gcd(nums[i], nums[j]) > 1) {
                    adj.get(i).add(j);
                    adj.get(j).add(i);
                }
            }
        }

        boolean[] visited = new boolean[n];
        int maxSize = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                int currentSize = dfs(i, adj, visited);
                maxSize = Math.max(maxSize, currentSize);
            }
        }
        return maxSize;
    }

    private int dfs(int u, List<List<Integer>> adj, boolean[] visited) {
        visited[u] = true;
        int count = 1;
        for (int v : adj.get(u)) {
            if (!visited[v]) {
                count += dfs(v, adj, visited);
            }
        }
        return count;
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}
```
### Algorithm
- Initialize an adjacency list to represent the graph. The nodes correspond to the indices of the `nums` array.
- Iterate through every unique pair of numbers `(nums[i], nums[j])` from the input array.
- For each pair, calculate their Greatest Common Divisor (GCD) using the Euclidean algorithm.
- If `gcd(nums[i], nums[j]) > 1`, add an edge between node `i` and node `j` in the adjacency list.
- Initialize a `visited` array to keep track of visited nodes and a variable `maxSize` to store the size of the largest component found so far.
- Iterate from `i = 0` to `nums.length - 1`. If node `i` has not been visited:
    - Start a DFS or BFS traversal from node `i`.
    - Count the number of nodes in the component discovered by the traversal.
    - Update `maxSize` with the maximum of its current value and the size of the new component.
- Return `maxSize`.

## Union-Find on Numbers with On-the-fly Factorization
This approach improves upon the brute-force method by avoiding the explicit construction of the graph. It uses a Disjoint Set Union (DSU) or Union-Find data structure to group numbers into connected components. The key insight is that two numbers are in the same component if they share a common prime factor. We can iterate through each number, find its prime factors, and union it with any other number that shares one of those primes.
**Time:** O(N * sqrt(M)), where N is `nums.length` and M is the max value in `nums`. The bottleneck is the prime factorization for each of the N numbers, which takes `O(sqrt(M))` time. Union-Find operations are nearly constant time. · **Space:** O(N + P), where N is `nums.length` and P is the number of unique prime factors across all numbers. P is bounded by `π(M)`, the number of primes up to the maximum value M. This is efficient.
**Pros:** Much more time and space efficient than the brute-force approach.; Avoids building a large `O(N^2)` graph by using an efficient DSU data structure.
**Cons:** The prime factorization step, which takes `O(sqrt(M))` for each number, can still be a bottleneck if `N` and `M` are large.; While much better than brute-force, it may be borderline on passing the time limits for the strictest constraints.
### Explanation
```java
class Solution {
    public int largestComponentSize(int[] nums) {
        int n = nums.length;
        DSU dsu = new DSU(n);
        Map<Integer, Integer> primeToIndex = new HashMap<>();

        for (int i = 0; i < n; i++) {
            int num = nums[i];
            for (int p = 2; p * p <= num; p++) {
                if (num % p == 0) {
                    if (!primeToIndex.containsKey(p)) {
                        primeToIndex.put(p, i);
                    }
                    dsu.union(i, primeToIndex.get(p));
                    while (num % p == 0) {
                        num /= p;
                    }
                }
            }
            if (num > 1) { // Remaining factor is prime
                if (!primeToIndex.containsKey(num)) {
                    primeToIndex.put(num, i);
                }
                dsu.union(i, primeToIndex.get(num));
            }
        }

        Map<Integer, Integer> componentCounts = new HashMap<>();
        int maxSize = 0;
        for (int i = 0; i < n; i++) {
            int root = dsu.find(i);
            int count = componentCounts.getOrDefault(root, 0) + 1;
            componentCounts.put(root, count);
            maxSize = Math.max(maxSize, count);
        }
        return maxSize;
    }
}

class DSU {
    int[] parent;
    public DSU(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    public int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }
    public void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) parent[rootJ] = rootI;
    }
}
```
### Algorithm
- Initialize a Union-Find data structure for `N` elements, where `N` is the length of `nums`. Each number `nums[i]` initially belongs to its own set.
- Create a hash map `primeToIndex` to store the first index `i` encountered for each prime factor `p`.
- Iterate through each number `x = nums[i]` from `i = 0` to `N-1`.
- For the current number `x`, find all its distinct prime factors. A simple way is to use trial division up to `sqrt(x)`.
- For each prime factor `p` of `x`:
    - Check if `p` exists as a key in `primeToIndex`.
    - If it does, it means we've seen this prime before in another number `nums[j]`, where `j = primeToIndex.get(p)`. We then union the sets of `i` and `j`.
    - If `p` does not exist in the map, we are seeing this prime for the first time. Store the current index `i` in the map: `primeToIndex.put(p, i)`.
- After processing all numbers, the DSU structure contains the connected components.
- Iterate through all numbers again, count the size of each component (set) using a hash map, and find the maximum size.

## Optimized Union-Find with Sieve
This is the most efficient approach. It builds upon the Union-Find idea but optimizes the prime factorization step. Instead of factoring each number individually, we first pre-compute the smallest prime factor (SPF) for all numbers up to the maximum value in `nums` using a sieve. This allows for very fast factorization. The DSU structure then connects numbers with their prime factors, efficiently forming the components.
**Time:** O(M log log M + N * log(M) * α(M)), where N is `nums.length`, M is the max value, and α is the inverse Ackermann function. `O(M log log M)` is for the sieve, and `O(N * log M)` is for iterating through numbers and their factors. This is highly efficient. · **Space:** O(M), where M is the maximum value in `nums`. This space is used for the `spf` array and the DSU `parent` array.
**Pros:** Optimal time complexity for the given constraints.; The sieve pre-computation significantly speeds up the critical step of finding prime factors, making the overall solution very fast.
**Cons:** More complex to implement due to the sieve pre-computation step.; Uses more memory, `O(M)`, which could be large if the maximum number is much larger than `N`.
### Explanation
```java
class Solution {
    public int largestComponentSize(int[] nums) {
        int maxVal = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }

        DSU dsu = new DSU(maxVal + 1);
        int[] spf = sieve(maxVal);

        for (int num : nums) {
            int temp = num;
            while (temp > 1) {
                int p = spf[temp];
                dsu.union(num, p);
                while (temp % p == 0) {
                    temp /= p;
                }
            }
        }

        Map<Integer, Integer> componentCounts = new HashMap<>();
        int maxSize = 0;
        for (int num : nums) {
            int root = dsu.find(num);
            int count = componentCounts.getOrDefault(root, 0) + 1;
            componentCounts.put(root, count);
            maxSize = Math.max(maxSize, count);
        }

        return maxSize;
    }

    private int[] sieve(int n) {
        int[] spf = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            spf[i] = i;
        }
        for (int i = 2; i * i <= n; i++) {
            if (spf[i] == i) { // i is prime
                for (int j = i * i; j <= n; j += i) {
                    if (spf[j] == j) { // if spf[j] is not set yet
                        spf[j] = i;
                    }
                }
            }
        }
        return spf;
    }
}

class DSU {
    int[] parent;

    public DSU(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    public int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        return parent[i] = find(parent[i]);
    }

    public void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            parent[rootJ] = rootI;
        }
    }
}
```
### Algorithm
- Find the maximum number `M` in the `nums` array.
- **Pre-computation:** Create an array `spf` (Smallest Prime Factor) of size `M+1`. Populate it using a sieve algorithm in `O(M log log M)` time. `spf[i]` will store the smallest prime that divides `i`.
- **Union-Find Model:** Initialize a DSU structure for `M+1` elements. This DSU will manage sets for all numbers from `0` to `M`, allowing us to directly union a number `x` with its prime factors `p`.
- Iterate through each number `x` in the `nums` array.
- For each `x`, find its distinct prime factors using the pre-computed `spf` array. This is done by repeatedly dividing `x` by `spf[x]` until `x` becomes 1. This process takes `O(log x)` time.
- For each prime factor `p` found, perform a union operation between the original number `x` and the prime `p`: `dsu.union(x, p)`.
- **Counting:** After processing all numbers, create a map to count the number of `nums` elements belonging to each component's root.
- Iterate through `nums` one last time. For each `x`, find its root `r = dsu.find(x)` and increment the count for `r`.
- The answer is the maximum count found in the map.

# Solutions
### Java

```java
class UnionFind { int [] p ; UnionFind ( int n ) { p = new int [ n ]; for ( int i = 0 ; i < n ; ++ i ) { p [ i ] = i ; } } void union ( int a , int b ) { int pa = find ( a ), pb = find ( b ); if ( pa != pb ) { p [ pa ] = pb ; } } int find ( int x ) { if ( p [ x ] != x ) { p [ x ] = find ( p [ x ]); } return p [ x ]; } } class Solution { public int largestComponentSize ( int [] nums ) { int m = 0 ; for ( int v : nums ) { m = Math . max ( m , v ); } UnionFind uf = new UnionFind ( m + 1 ); for ( int v : nums ) { int i = 2 ; while ( i <= v / i ) { if ( v % i == 0 ) { uf . union ( v , i ); uf . union ( v , v / i ); } ++ i ; } } int [] cnt = new int [ m + 1 ]; int ans = 0 ; for ( int v : nums ) { int t = uf . find ( v ); ++ cnt [ t ]; ans = Math . max ( ans , cnt [ t ]); } return ans ; } }
```

### CPP

```cpp
class UnionFind { public: vector < int > p ; int n ; UnionFind ( int _n ) : n ( _n ) , p ( _n ) { iota ( p . begin (), p . end (), 0 ); } void unite ( int a , int b ) { int pa = find ( a ), pb = find ( b ); if ( pa != pb ) p [ pa ] = pb ; } int find ( int x ) { if ( p [ x ] != x ) p [ x ] = find ( p [ x ]); return p [ x ]; } }; class Solution { public: int largestComponentSize ( vector < int >& nums ) { int m = * max_element ( nums . begin (), nums . end ()); UnionFind * uf = new UnionFind ( m + 1 ); for ( int v : nums ) { int i = 2 ; while ( i <= v / i ) { if ( v % i == 0 ) { uf -> unite ( v , i ); uf -> unite ( v , v / i ); } ++ i ; } } vector < int > cnt ( m + 1 ); int ans = 0 ; for ( int v : nums ) { int t = uf -> find ( v ); ++ cnt [ t ]; ans = max ( ans , cnt [ t ]); } return ans ; } };
```

### Python

```python
class UnionFind : def __init__ ( self , n ): self . p = list ( range ( n )) def union ( self , a , b ): pa , pb = self . find ( a ), self . find ( b ) if pa != pb : self . p [ pa ] = pb def find ( self , x ): if self . p [ x ] != x : self . p [ x ] = self . find ( self . p [ x ]) return self . p [ x ] class Solution : def largestComponentSize ( self , nums : List [ int ]) -> int : uf = UnionFind ( max ( nums ) + 1 ) for v in nums : i = 2 while i <= v // i : if v % i == 0 : uf . union ( v , i ) uf . union ( v , v // i ) i += 1 return max ( Counter ( uf . find ( v ) for v in nums ). values ())
```