952. Largest Component Size by Common Factor

952

HardUnion-Find / Disjoint Set UnionUnion-Find with prime factorizationUnion by prime factors

Largest Component Size by Common Factor

Given an array nums of unique positive integers, build a graph with one node per value; connect two values with an edge if they share a common factor greater than 1. Return the size of the largest connected component of this graph.

Open official problem prompt ↗

In plain English

Find the size of the largest group of numbers that are transitively linked by shared prime factors.

Picture it like this

Think of primes as clubs. Every number joins the club of each prime that divides it. People in overlapping clubs form one big social circle; we want the biggest circle.

Example

Input: nums = [4,6,15,35]
Output: 4
Why: 4-6 share 2, 6-15 share 3, 15-35 share 5, so all four values are transitively connected into one component of size 4.

Constraints

1 <= nums.length <= 2 * 10^41 <= nums[i] <= 10^5All values in nums are unique

Pattern lesson

See the pattern, then code

Union by prime factors

↗

Union-Find / Disjoint Set Union

Dynamic connectivity, merging groups, redundant edges, or Kruskal's algorithm.. Two numbers sharing a common factor > 1 means they share a prime factor. Instead of comparing every pair (O(n^2)), union each number with each of its prime factors; numbers sharing any prime land in the same set. Then the largest bucket of numbers by root is the answer.

New words, made simpleKnow these before the algorithm

Prime factor: A prime that divides a number; sharing one means sharing a common factor > 1.
Prime as a node: We union a value with each of its primes so values sharing a prime merge without pairwise comparison.
Trial division: Factorizing by testing divisors up to sqrt(x).

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Pairwise gcd

Quadratic pairs blow up at n = 2*10^4.

For every pair (i, j) union them if gcd(nums[i], nums[j]) > 1.

Time O(n^2 log M)Space O(n)

Best choiceUnion with prime factors

Linear in n times factorization cost, comfortably fast.

Union each number with its prime factors; shared primes auto-merge the numbers.

Time O(n * sqrt(M))Space O(n + P)

The rule we keep true

Invariant

Two numbers share a DSU root if and only if there is a chain of shared prime factors connecting them.

Why this is correct

Reasoning

If two numbers share a common factor > 1, they share a prime p, and both are unioned with p, so they end up in the same set. Conversely, numbers only merge through primes they actually contain. Thus DSU sets correspond exactly to the graph's connected components, and the largest number-count per root is the largest component.

The algorithm in three movesSay these aloud before coding

1For each number, factorize it into primes

4 -> prime 2: union(4,2)

2Union the number's id with each of its prime-factor ids

6 -> 2,3: union(6,2),union(6,3)

3After processing all numbers, find the root of each number

15 -> 3,5; 35 -> 5,7 chain together

4Count numbers per root and return the maximum bucket size

all 4 share one root -> size 4

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

152

353

1 · Readfactor 2

2 · AskUnion with primes

3 · Update stateunion(4,2)

4 · Result{4,2}

Key takeaway

Shared primes 2, 3, 5 chain every value into one component.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 5-10find with lazy nodes
Both numbers and primes live in the same forest; setdefault registers primes on first touch.
2
Lines 15-24Factorize and union
Trial-divide num, unioning it with each prime factor; the residual x > 1 is a large prime factor.
3
Lines 26-27Largest bucket
Count how many original numbers map to each root; the maximum is the largest component.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A value of 1 has no prime factor > 1, so it forms its own component of size 1
A large prime value only connects to itself unless another multiple of it appears
Two equal-size components (return either size, they match)

Common beginner mistakes

Counting primes in the bucket totals instead of only original numbers (count find(num) for num in nums, not all keys)
Forgetting the residual x > 1 after the loop, which is the last prime factor
Using pairwise gcd and timing out at large n

Check your understanding

Why union numbers with their prime factors instead of comparing numbers pairwise?

PyPython 3 · solution.py

Optimal

1class Solution:2    def largestComponentSize(self, nums: list[int]) -> int:3        from collections import Counter4        parent: dict[int, int] = {}56        def find(x: int) -> int:7            parent.setdefault(x, x)8            while parent[x] != x:9                parent[x] = parent[parent[x]]10                x = parent[x]11            return x1213        def union(a: int, b: int) -> None:14            parent[find(a)] = find(b)1516        for num in nums:17            x = num18            d = 219            while d * d <= x:20                if x % d == 0:21                    union(num, d)22                    while x % d == 0:23                        x //= d24                d += 125            if x > 1:26                union(num, x)2728        counts = Counter(find(num) for num in nums)29        return max(counts.values())

Time complexityO(n * sqrt(M))Optimized

Space complexityO(n + P)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

GoogleAirbnbAmazon

Largest Component Size by Common Factor

Largest Component Size by Common Factor

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Union-Find / Disjoint Set Union