Problem editorial

Largest Component Size by Common Factor

HardGraph Traversal Patterns (DFS & BFS)ArrayHash TableMath

Editorial

Core insight

Largest Component Size by Common Factor · Graph Traversal Patterns (DFS & BFS)

Core Insight for Largest Component Size by Common Factor

The core insight that allows us to bypass the $O(N^2)$ comparison is prime factorization.

If number $A$ and number $B$ share a common factor $g > 1$ , they belong to the same component. This implies transitivity: if $A$ shares a factor with $B$ , and $B$ shares a factor with $C$ , then $A$ , $B$ , and $C$ are in the same component.

Instead of connecting numbers directly to each other, we can connect each number to its factors.

If we have the number 6, it has factors 2 and 3. We can conceptually draw edges $6 \leftrightarrow 2$ and $6 \leftrightarrow 3$ .
If we have the number 15, it has factors 3 and 5. We draw edges $15 \leftrightarrow 3$ and $15 \leftrightarrow 5$ .
Because 6 and 15 both connect to the factor 3, they become part of the same connected component ( $6 \leftrightarrow 3 \leftrightarrow 15$ ).

Visual Description: Imagine the DSU structure as a forest of trees. Initially, every integer from 1 up to the maximum value in nums is its own root. When we process a number from the input array, say 14, we calculate its prime factors (2 and 7). We perform a union operation merging the set containing 14, the set containing 2, and the set containing 7. As we process more numbers, these sets merge further. Finally, the "size" of a component is determined by how many numbers from the original nums array map to the same root parent in the DSU structure.

By unioning numbers with their factors, we implicitly build the connected components without ever iterating over pairs of numbers.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 952: Largest Component Size by Common Factor Solution & Explanation

Problem Overview

TL;DR: The optimal solution decomposes each number into its prime factors and uses a Union-Find (Disjoint Set Union) data structure to group numbers that share common prime factors, subsequently counting the size of the largest group.

In the LeetCode 952 problem, "Largest Component Size by Common Factor," you are provided with an array of unique positive integers. These integers represent nodes in a graph. An undirected edge exists between two nodes if they share a common factor greater than 1 (i.e., their greatest common divisor is greater than 1). The objective is to determine the size of the largest connected component in this implicitly defined graph.

Brute Force Approach for Largest Component Size by Common Factor

The naive approach attempts to build the graph explicitly by checking every possible pair of numbers to see if an edge exists between them.

Initialize an adjacency list or matrix for a graph with $N$ nodes.
Iterate through every pair of indices $(i, j)$ from the input array nums.
Calculate the Greatest Common Divisor (GCD) of nums[i] and nums[j].
If $\text{GCD}(nums[i], nums[j]) > 1$ , add an edge between node $i$ and node $j$ .
After building the graph, perform a standard DFS or BFS on every unvisited node to find the size of its connected component.
Return the maximum size found.

Pseudo-code:

text

max_size = 0
visited = set()
graph = build_empty_graph(nums.length)

for i from 0 to nums.length:
    for j from i + 1 to nums.length:
        if gcd(nums[i], nums[j]) > 1:
            add_edge(graph, i, j)

for i from 0 to nums.length:
    if i not in visited:
        component_size = dfs(graph, i, visited)
        max_size = max(max_size, component_size)

return max_size

Time Complexity Analysis: The time complexity is dominated by the pair-wise comparison. There are $O(N^2)$ pairs. Calculating GCD takes logarithmic time relative to the value of the numbers ( $V$ ). Total Complexity: $O(N^2 \log V)$ .

Why it fails: Given the constraints, $N$ can be up to $20,000$ . $N^2$ results in $400,000,000$ pairs. Combined with the GCD overhead, this far exceeds the typical operation limit (approx $10^8$ ) allowed by LeetCode, resulting in a Time Limit Exceeded (TLE) error.

Algorithm Strategy: Graph - Union-Find (DSU)

Identify the Range: Determine the maximum value ( $M$ ) in the nums array. This defines the size of our DSU array, as we need to handle all potential factors up to this maximum.
Initialize DSU: Create a Union-Find data structure capable of handling elements from $0$ to $M$ .
Factorize and Union: Iterate through each number num in the input array nums.
- Find all prime factors of num. We can do this by iterating from $d=2$ up to $\sqrt{num}$ .
- If $d$ divides num, then both $d$ and $num/d$ are factors.
- Perform union(num, d) and union(num, num/d). This effectively groups the number num with all other numbers that share the factor $d$ or $num/d$ .
Count Components:
- Initialize a frequency map (hash map).
- Iterate through the original nums array one last time.
- For each num, find its representative root using find(num).
- Increment the count for this root in the frequency map.
Result: The maximum value in the frequency map is the size of the largest connected component.

Execution Flow

Let's trace nums = [4, 6, 15, 35]. Max value is 35. Initialize DSU for $0..35$ .

Process 4:
- Factors: 2.
- union(4, 2). Set: $\{2, 4\}$ .
Process 6:
- Factors: 2, 3.
- union(6, 2). Set merges with $\{2, 4\}$ . New Set: $\{2, 4, 6\}$ .
- union(6, 3). Set merges with $\{3\}$ . New Set: $\{2, 3, 4, 6\}$ .
Process 15:
- Factors: 3, 5.
- union(15, 3). Set merges with $\{2, 3, 4, 6\}$ . New Set: $\{2, 3, 4, 6, 15\}$ .
- union(15, 5). Set merges with $\{5\}$ . New Set: $\{2, 3, 4, 5, 6, 15\}$ .
Process 35:
- Factors: 5, 7.
- union(35, 5). Set merges with previous large set.
- union(35, 7).
- All numbers are now indirectly connected.
Count:
- find(4) $\to$ Root A. Count[Root A] = 1.
- find(6) $\to$ Root A. Count[Root A] = 2.
- find(15) $\to$ Root A. Count[Root A] = 3.
- find(35) $\to$ Root A. Count[Root A] = 4.
Result: Max count is 4.

Proof of Correctness

The correctness relies on the mathematical definition of the problem edges. An edge exists between $A$ and $B$ if $\text{GCD}(A, B) > 1$ . This implies there exists a prime $p$ such that $p | A$ and $p | B$ .

Our algorithm performs union(A, p) and union(B, p). Due to the transitive property of the Union-Find data structure, if $A$ is connected to $p$ and $B$ is connected to $p$ , then $A$ is connected to $B$ . Thus, any two numbers that share a common factor will end up in the same set. Since connectivity is transitive (if $A \sim B$ and $B \sim C$ , then $A \sim C$ ), the DSU correctly aggregates all elements belonging to the same connected component.

Pattern Reuse Notes

The Graph - Union-Find pattern is highly reusable for connectivity problems involving dynamic grouping or cycle detection.

LeetCode 200: Number of Islands: While typically DFS/BFS, this can be solved with DSU by unioning adjacent land cells.
LeetCode 261: Graph Valid Tree: Uses DSU to detect cycles; a valid tree must have $N-1$ edges and no cycles.
LeetCode 305: Number of Islands II: A classic dynamic connectivity problem where DSU is essential to merge islands as land is added.
LeetCode 323: Number of Connected Components in an Undirected Graph: The direct definition of finding component counts using DSU.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 952

cpp

1#include <vector>
2#include <numeric>
3#include <algorithm>
4#include <cmath>
5#include <unordered_map>
6
7using namespace std;
8
9class DSU {
10public:
11    vector<int> parent;
12    
13    DSU(int n) {
14        parent.resize(n + 1);
15        iota(parent.begin(), parent.end(), 0);
16    }
17    
18    int find(int x) {
19        if (parent[x] != x) {
20            parent[x] = find(parent[x]); // Path compression
21        }
22        return parent[x];
23    }
24    
25    void unite(int x, int y) {
26        int rootX = find(x);
27        int rootY = find(y);
28        if (rootX != rootY) {
29            parent[rootX] = rootY; // Simple union
30        }
31    }
32};
33
34class Solution {
35public:
36    int largestComponentSize(vector<int>& nums) {
37        int maxVal = *max_element(nums.begin(), nums.end());
38        DSU dsu(maxVal);
39        
40        // Union numbers with their factors
41        for (int num : nums) {
42            for (int factor = 2; factor * factor <= num; ++factor) {
43                if (num % factor == 0) {
44                    dsu.unite(num, factor);
45                    dsu.unite(num, num / factor);
46                }
47            }
48        }
49        
50        // Count frequency of each component's root
51        unordered_map<int, int> componentSize;
52        int maxSize = 0;
53        
54        for (int num : nums) {
55            int root = dsu.find(num);
56            componentSize[root]++;
57            maxSize = max(maxSize, componentSize[root]);
58        }
59        
60        return maxSize;
61    }
62};

Java Solution for LeetCode 952

java

1import java.util.HashMap;
2import java.util.Map;
3
4class Solution {
5    class DSU {
6        int[] parent;
7
8        public DSU(int n) {
9            parent = new int[n + 1];
10            for (int i = 0; i <= n; i++) {
11                parent[i] = i;
12            }
13        }
14
15        public int find(int x) {
16            if (parent[x] != x) {
17                parent[x] = find(parent[x]); // Path compression
18            }
19            return parent[x];
20        }
21
22        public void union(int x, int y) {
23            int rootX = find(x);
24            int rootY = find(y);
25            if (rootX != rootY) {
26                parent[rootX] = rootY;
27            }
28        }
29    }
30
31    public int largestComponentSize(int[] nums) {
32        int maxVal = 0;
33        for (int num : nums) maxVal = Math.max(maxVal, num);
34        
35        DSU dsu = new DSU(maxVal);
36        
37        // Iterate over each number and union with its factors
38        for (int num : nums) {
39            for (int factor = 2; factor * factor <= num; factor++) {
40                if (num % factor == 0) {
41                    dsu.union(num, factor);
42                    dsu.union(num, num / factor);
43                }
44            }
45        }
46        
47        // Count the size of components based on roots of numbers in nums
48        Map<Integer, Integer> countMap = new HashMap<>();
49        int maxComponent = 0;
50        
51        for (int num : nums) {
52            int root = dsu.find(num);
53            int count = countMap.getOrDefault(root, 0) + 1;
54            countMap.put(root, count);
55            maxComponent = Math.max(maxComponent, count);
56        }
57        
58        return maxComponent;
59    }
60}

Python Solution for LeetCode 952

python

1class Solution:
2    def largestComponentSize(self, nums: list[int]) -> int:
3        max_val = max(nums)
4        
5        # DSU Implementation using a list
6        parent = list(range(max_val + 1))
7        
8        def find(x):
9            if parent[x] != x:
10                parent[x] = find(parent[x]) # Path compression
11            return parent[x]
12        
13        def union(x, y):
14            rootX = find(x)
15            rootY = find(y)
16            if rootX != rootY:
17                parent[rootX] = rootY
18        
19        # Union numbers with their factors
20        for num in nums:
21            limit = int(num**0.5)
22            for factor in range(2, limit + 1):
23                if num % factor == 0:
24                    union(num, factor)
25                    union(num, num // factor)
26        
27        # Count component sizes
28        from collections import defaultdict
29        count_map = defaultdict(int)
30        max_size = 0
31        
32        for num in nums:
33            root = find(num)
34            count_map[root] += 1
35            max_size = max(max_size, count_map[root])
36            
37        return max_size

AI Coach Insight

For Largest Component Size by Common Factor, focus on explaining why the structure works, not just naming Graph Traversal Patterns (DFS & BFS).

Complexity Analysis

Let $N$ be the length of nums and $M$ be the maximum value in nums.

Time Complexity: $O(N \cdot \sqrt{M} \cdot \alpha(M))$
- We iterate through $N$ numbers.
- For each number, we iterate up to $\sqrt{M}$ to find factors.
- Inside the factorization loop, we perform DSU operations (union, find). The amortized time complexity of these operations is $\alpha(M)$ , where $\alpha$ is the Inverse Ackermann function (nearly constant, $\le 4$ ).
- Finally, we iterate $N$ times to count frequencies.
- Given $M \le 100,000$ , $\sqrt{M} \approx 316$ . $N \le 20,000$ . Total operations are roughly $20,000 \times 316$ , which is well within limits ( $\approx 6 \times 10^6$ ).
Space Complexity: $O(M)$
- The DSU arrays (parent and rank/size) require space proportional to the maximum value $M$ (up to 100,000).
- The frequency map in the final step stores at most $N$ entries.

Related Patterns

Pattern: Graph Traversal Patterns (DFS & BFS) Subpattern: Graph - Union-Find (Disjoint Set Union - DSU)

While the problem asks for connected components (often solved with DFS/BFS), the dense nature of the edges makes explicit graph construction inefficient. The Union-Find subpattern allows us to merge sets dynamically based on shared properties (factors) without checking every pair of nodes.

Common Mistakes & FAQ

Why does the naive solution result in TLE?
- The naive solution compares every pair of numbers ( $O(N^2)$ ). With $N=20,000$ , this results in roughly 400 million operations, which is too slow for the 1-second time limit. The efficient approach depends on $O(N \sqrt{M})$ logic.
Why iterate only up to $\sqrt{num}$ ?
- Iterating up to num to find factors increases time complexity to $O(N \cdot M)$ , which is much slower than $O(N \cdot \sqrt{M})$ . Any factor larger than $\sqrt{num}$ has a corresponding pair smaller than $\sqrt{num}$ (handled by num // factor), so checking up to the square root is sufficient.
Why not use the DSU size array directly?
- Standard DSU implementations maintain a size array to track the number of nodes in a set. However, our DSU nodes include both the numbers from nums and their factors. We only care about how many elements from nums are in a component, not how many factors are involved. Therefore, we must manually count frequencies of roots for the elements in nums at the end.
Forgetting to handle num // factor?
- When iterating factors $d$ up to $\sqrt{num}$ , if $d$ divides num, then num/d is also a factor. If you only union num with d, you miss connections to larger prime factors, potentially fracturing the component.

Practise Largest Component Size by Common Factor and the problems around it

Largest Component Size by Common Factor is a Graph Traversal Patterns (DFS & BFS) problem, in the Union-Find (Disjoint Set Union - DSU) subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Core insight

Largest Component Size by Common Factor · Graph Traversal Patterns (DFS & BFS)

Core Insight for Largest Component Size by Common Factor

The core insight that allows us to bypass the $O(N^2)$ comparison is prime factorization.

Instead of connecting numbers directly to each other, we can connect each number to its factors.

If we have the number 6, it has factors 2 and 3. We can conceptually draw edges $6 \leftrightarrow 2$ and $6 \leftrightarrow 3$ .
If we have the number 15, it has factors 3 and 5. We draw edges $15 \leftrightarrow 3$ and $15 \leftrightarrow 5$ .
Because 6 and 15 both connect to the factor 3, they become part of the same connected component ( $6 \leftrightarrow 3 \leftrightarrow 15$ ).

By unioning numbers with their factors, we implicitly build the connected components without ever iterating over pairs of numbers.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 952: Largest Component Size by Common Factor Solution & Explanation

Problem Overview

Brute Force Approach for Largest Component Size by Common Factor

The naive approach attempts to build the graph explicitly by checking every possible pair of numbers to see if an edge exists between them.

Initialize an adjacency list or matrix for a graph with $N$ nodes.
Iterate through every pair of indices $(i, j)$ from the input array nums.
Calculate the Greatest Common Divisor (GCD) of nums[i] and nums[j].
If $\text{GCD}(nums[i], nums[j]) > 1$ , add an edge between node $i$ and node $j$ .
After building the graph, perform a standard DFS or BFS on every unvisited node to find the size of its connected component.
Return the maximum size found.

Pseudo-code:

text

max_size = 0
visited = set()
graph = build_empty_graph(nums.length)

for i from 0 to nums.length:
    for j from i + 1 to nums.length:
        if gcd(nums[i], nums[j]) > 1:
            add_edge(graph, i, j)

for i from 0 to nums.length:
    if i not in visited:
        component_size = dfs(graph, i, visited)
        max_size = max(max_size, component_size)

return max_size

Algorithm Strategy: Graph - Union-Find (DSU)

Identify the Range: Determine the maximum value ( $M$ ) in the nums array. This defines the size of our DSU array, as we need to handle all potential factors up to this maximum.
Initialize DSU: Create a Union-Find data structure capable of handling elements from $0$ to $M$ .
Factorize and Union: Iterate through each number num in the input array nums.
- Find all prime factors of num. We can do this by iterating from $d=2$ up to $\sqrt{num}$ .
- If $d$ divides num, then both $d$ and $num/d$ are factors.
- Perform union(num, d) and union(num, num/d). This effectively groups the number num with all other numbers that share the factor $d$ or $num/d$ .
Count Components:
- Initialize a frequency map (hash map).
- Iterate through the original nums array one last time.
- For each num, find its representative root using find(num).
- Increment the count for this root in the frequency map.
Result: The maximum value in the frequency map is the size of the largest connected component.

Execution Flow

Let's trace nums = [4, 6, 15, 35]. Max value is 35. Initialize DSU for $0..35$ .

Process 4:
- Factors: 2.
- union(4, 2). Set: $\{2, 4\}$ .
Process 6:
- Factors: 2, 3.
- union(6, 2). Set merges with $\{2, 4\}$ . New Set: $\{2, 4, 6\}$ .
- union(6, 3). Set merges with $\{3\}$ . New Set: $\{2, 3, 4, 6\}$ .
Process 15:
- Factors: 3, 5.
- union(15, 3). Set merges with $\{2, 3, 4, 6\}$ . New Set: $\{2, 3, 4, 6, 15\}$ .
- union(15, 5). Set merges with $\{5\}$ . New Set: $\{2, 3, 4, 5, 6, 15\}$ .
Process 35:
- Factors: 5, 7.
- union(35, 5). Set merges with previous large set.
- union(35, 7).
- All numbers are now indirectly connected.
Count:
- find(4) $\to$ Root A. Count[Root A] = 1.
- find(6) $\to$ Root A. Count[Root A] = 2.
- find(15) $\to$ Root A. Count[Root A] = 3.
- find(35) $\to$ Root A. Count[Root A] = 4.
Result: Max count is 4.

Proof of Correctness

Pattern Reuse Notes

The Graph - Union-Find pattern is highly reusable for connectivity problems involving dynamic grouping or cycle detection.

LeetCode 200: Number of Islands: While typically DFS/BFS, this can be solved with DSU by unioning adjacent land cells.
LeetCode 261: Graph Valid Tree: Uses DSU to detect cycles; a valid tree must have $N-1$ edges and no cycles.
LeetCode 305: Number of Islands II: A classic dynamic connectivity problem where DSU is essential to merge islands as land is added.
LeetCode 323: Number of Connected Components in an Undirected Graph: The direct definition of finding component counts using DSU.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 952

cpp

1#include <vector>
2#include <numeric>
3#include <algorithm>
4#include <cmath>
5#include <unordered_map>
6
7using namespace std;
8
9class DSU {
10public:
11    vector<int> parent;
12    
13    DSU(int n) {
14        parent.resize(n + 1);
15        iota(parent.begin(), parent.end(), 0);
16    }
17    
18    int find(int x) {
19        if (parent[x] != x) {
20            parent[x] = find(parent[x]); // Path compression
21        }
22        return parent[x];
23    }
24    
25    void unite(int x, int y) {
26        int rootX = find(x);
27        int rootY = find(y);
28        if (rootX != rootY) {
29            parent[rootX] = rootY; // Simple union
30        }
31    }
32};
33
34class Solution {
35public:
36    int largestComponentSize(vector<int>& nums) {
37        int maxVal = *max_element(nums.begin(), nums.end());
38        DSU dsu(maxVal);
39        
40        // Union numbers with their factors
41        for (int num : nums) {
42            for (int factor = 2; factor * factor <= num; ++factor) {
43                if (num % factor == 0) {
44                    dsu.unite(num, factor);
45                    dsu.unite(num, num / factor);
46                }
47            }
48        }
49        
50        // Count frequency of each component's root
51        unordered_map<int, int> componentSize;
52        int maxSize = 0;
53        
54        for (int num : nums) {
55            int root = dsu.find(num);
56            componentSize[root]++;
57            maxSize = max(maxSize, componentSize[root]);
58        }
59        
60        return maxSize;
61    }
62};

Java Solution for LeetCode 952

java

1import java.util.HashMap;
2import java.util.Map;
3
4class Solution {
5    class DSU {
6        int[] parent;
7
8        public DSU(int n) {
9            parent = new int[n + 1];
10            for (int i = 0; i <= n; i++) {
11                parent[i] = i;
12            }
13        }
14
15        public int find(int x) {
16            if (parent[x] != x) {
17                parent[x] = find(parent[x]); // Path compression
18            }
19            return parent[x];
20        }
21
22        public void union(int x, int y) {
23            int rootX = find(x);
24            int rootY = find(y);
25            if (rootX != rootY) {
26                parent[rootX] = rootY;
27            }
28        }
29    }
30
31    public int largestComponentSize(int[] nums) {
32        int maxVal = 0;
33        for (int num : nums) maxVal = Math.max(maxVal, num);
34        
35        DSU dsu = new DSU(maxVal);
36        
37        // Iterate over each number and union with its factors
38        for (int num : nums) {
39            for (int factor = 2; factor * factor <= num; factor++) {
40                if (num % factor == 0) {
41                    dsu.union(num, factor);
42                    dsu.union(num, num / factor);
43                }
44            }
45        }
46        
47        // Count the size of components based on roots of numbers in nums
48        Map<Integer, Integer> countMap = new HashMap<>();
49        int maxComponent = 0;
50        
51        for (int num : nums) {
52            int root = dsu.find(num);
53            int count = countMap.getOrDefault(root, 0) + 1;
54            countMap.put(root, count);
55            maxComponent = Math.max(maxComponent, count);
56        }
57        
58        return maxComponent;
59    }
60}

Python Solution for LeetCode 952

python

1class Solution:
2    def largestComponentSize(self, nums: list[int]) -> int:
3        max_val = max(nums)
4        
5        # DSU Implementation using a list
6        parent = list(range(max_val + 1))
7        
8        def find(x):
9            if parent[x] != x:
10                parent[x] = find(parent[x]) # Path compression
11            return parent[x]
12        
13        def union(x, y):
14            rootX = find(x)
15            rootY = find(y)
16            if rootX != rootY:
17                parent[rootX] = rootY
18        
19        # Union numbers with their factors
20        for num in nums:
21            limit = int(num**0.5)
22            for factor in range(2, limit + 1):
23                if num % factor == 0:
24                    union(num, factor)
25                    union(num, num // factor)
26        
27        # Count component sizes
28        from collections import defaultdict
29        count_map = defaultdict(int)
30        max_size = 0
31        
32        for num in nums:
33            root = find(num)
34            count_map[root] += 1
35            max_size = max(max_size, count_map[root])
36            
37        return max_size

Largest Component Size by Common Factor

Core insight

Core Insight for Largest Component Size by Common Factor

Full breakdown

LeetCode 952: Largest Component Size by Common Factor Solution & Explanation

Problem Overview

Brute Force Approach for Largest Component Size by Common Factor

Algorithm Strategy: Graph - Union-Find (DSU)

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 952

Java Solution for LeetCode 952

Python Solution for LeetCode 952

Practise Largest Component Size by Common Factor and the problems around it

Related problems

Largest Component Size by Common Factor

Core insight

Core Insight for Largest Component Size by Common Factor

Full breakdown

LeetCode 952: Largest Component Size by Common Factor Solution & Explanation

Problem Overview

Brute Force Approach for Largest Component Size by Common Factor

Algorithm Strategy: Graph - Union-Find (DSU)

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 952

Java Solution for LeetCode 952

Python Solution for LeetCode 952

Practise Largest Component Size by Common Factor and the problems around it

Related problems