LeetCode 952 - Largest Component Size by Common Factor
The problem asks us to find the largest connected component in a graph derived from an array of unique positive integers nums.
Difficulty: 🔴 Hard
Topics: Array, Hash Table, Math, Union-Find, Number Theory
Solution
Problem Understanding
The problem asks us to find the largest connected component in a graph derived from an array of unique positive integers nums. Each integer in the array represents a node, and there is an undirected edge between two nodes if the corresponding numbers share a common factor greater than 1. Essentially, numbers are connected if they have a non-trivial greatest common divisor. The goal is to determine the size of the largest cluster of numbers where every number is indirectly connected through shared factors.
The input nums contains up to 20,000 integers, each up to 100,000, and all are unique. This guarantees we do not have to deal with duplicate nodes. The main challenge is efficiently finding connections based on factors, since checking all pairs would be computationally prohibitive. Edge cases include prime numbers, numbers with only one factor in common, and numbers that share multiple factors with different numbers.
Approaches
Brute Force
A naive approach would be to consider every pair of numbers and check if they share a common factor greater than 1. If they do, we could add an edge between the corresponding nodes in a graph. After constructing the graph, we could run a depth-first search or breadth-first search to find connected components and return the size of the largest one.
While correct, this approach is too slow because checking all pairs requires $O(n^2)$ gcd computations, and each gcd operation could be up to $O(\log(\text{maxNum}))$. For n = 20,000, this becomes impractical.
Optimal Approach
The key observation is that instead of checking all pairs, we can associate each number with its prime factors. Numbers sharing the same prime factor belong to the same connected component. Using a Union-Find (Disjoint Set Union) data structure, we can union numbers by their prime factors efficiently.
- Factorize each number into primes.
- Use a union-find to merge numbers that share a factor.
- Count the size of each connected component by tracking the root of each number.
This reduces the problem to factorization and union-find operations, which are far more efficient than pairwise gcd checks.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n^2 log m) | O(n^2) | Check all pairs using gcd |
| Optimal | O(n * sqrt(m)) | O(n + m) | Factorization + Union-Find, m = max(nums) |
Algorithm Walkthrough
- Initialize Union-Find: Create a union-find data structure that can track unions by indices of numbers. This allows us to merge numbers that share common factors efficiently.
- Prime Factorization: For each number, compute its prime factors up to its square root. This ensures that each factor is considered only once.
- Union by Factor: Maintain a mapping from each factor to a number index. If a factor is already associated with a number, union the current number with that previous number.
- Count Component Sizes: After all unions are performed, traverse all numbers, find their roots, and count how many numbers belong to each root.
- Return Maximum Size: The largest component size is the maximum count among all roots.
Why it works: Each union operation ensures that numbers sharing any factor are in the same component. Because all numbers sharing a factor are merged transitively, the connected components in the union-find structure correspond exactly to the connected components defined by shared factors in the graph.
Python Solution
from typing import List
from collections import defaultdict
import math
class Solution:
def largestComponentSize(self, nums: List[int]) -> int:
parent = {}
size = {}
def find(x):
if parent.setdefault(x, x) != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px != py:
parent[py] = px
size[px] = size.get(px, 1) + size.get(py, 1)
factor_to_num = {}
for num in nums:
for i in range(2, int(math.isqrt(num)) + 1):
if num % i == 0:
if i in factor_to_num:
union(num, factor_to_num[i])
else:
factor_to_num[i] = num
j = num // i
if j in factor_to_num:
union(num, factor_to_num[j])
else:
factor_to_num[j] = num
count = defaultdict(int)
max_size = 0
for num in nums:
root = find(num)
count[root] += 1
max_size = max(max_size, count[root])
return max_size
Explanation: We use a union-find structure with path compression. Each factor maps to one number; if another number shares that factor, we union them. Counting the root occurrences at the end gives the component sizes.
Go Solution
package main
import (
"math"
)
func largestComponentSize(nums []int) int {
parent := make(map[int]int)
size := make(map[int]int)
var find func(int) int
find = func(x int) int {
if _, ok := parent[x]; !ok {
parent[x] = x
}
if parent[x] != x {
parent[x] = find(parent[x])
}
return parent[x]
}
union := func(x, y int) {
px, py := find(x), find(y)
if px != py {
parent[py] = px
size[px] = size[px] + size[py]
}
}
factorToNum := make(map[int]int)
for _, num := range nums {
for i := 2; i <= int(math.Sqrt(float64(num))); i++ {
if num%i == 0 {
if prev, ok := factorToNum[i]; ok {
union(num, prev)
} else {
factorToNum[i] = num
}
j := num / i
if prev, ok := factorToNum[j]; ok {
union(num, prev)
} else {
factorToNum[j] = num
}
}
}
}
count := make(map[int]int)
maxSize := 0
for _, num := range nums {
root := find(num)
count[root]++
if count[root] > maxSize {
maxSize = count[root]
}
}
return maxSize
}
Go-specific notes: Go maps handle missing keys gracefully, but we initialize parent mapping explicitly. Integer square roots require float64 conversion for math.Sqrt. Slice vs array is not a factor here as nums is passed as a slice.
Worked Examples
Example: [4,6,15,35]
Step-by-step factor mapping and union operations:
| Number | Factors | Union Operations |
|---|---|---|
| 4 | 2 | 4 is first with 2 → map 2→4 |
| 6 | 2,3 | 2→4, union 6 and 4 → 6-4; map 3→6 |
| 15 | 3,5 | 3→6, union 15 and 6 → 15-6-4; map 5→15 |
| 35 | 5,7 | 5→15, union 35 and 15 → 35-15-6-4; map 7→35 |
Counting roots gives one component of size 4.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n * sqrt(m)) | Each number factorized up to sqrt(num) and union-find operations are nearly O(1) amortized |
| Space | O(n + m) | Union-find stores parent for each number, factor map stores mapping for factors up to max(num) |
The complexity is dominated by factorization.
Test Cases
# Provided examples
assert Solution().largestComponentSize([4,6,15,35]) == 4 # all connected
assert Solution().largestComponentSize([20,50,9,63]) == 2 # 20-50 and 9-63
assert Solution().largestComponentSize([2,3,6,7,4,12,21,39]) == 8 # all connected
# Edge cases
assert Solution().largestComponentSize([2]) == 1 # single element
assert Solution().largestComponentSize([2,3,5,7,11]) == 1 # all primes
assert Solution().largestComponentSize([6,10,15,30]) == 4 # multiple shared factors
assert Solution().largestComponentSize([100000]) == 1 # largest possible value
| Test | Why |
|---|---|
[4,6,15,35] |
Validates union by multiple shared factors |
[20,50,9,63] |
Checks separate components |
[2,3,6,7,4,12,21,39] |
Large connected component |
[2] |
Minimal input |
[2,3,5,7,11] |
All primes, no connections |
[6,10,15,30] |
Multiple shared factors causing unions |
[100000] |
Edge value for |