#952

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Largest Component Size by Common Factor

Find the largest connected component in an array where edges exist between numbers sharing a common factor greater than one.

array hash table math union find number theory

Problem Statement

You are given an array of unique positive integers nums. Construct an undirected graph where each integer is a node, and there is an edge between two numbers if they share a common factor greater than one. The task is to find the size of the largest connected component in this graph.

For example, given nums = [4,6,15,35], nodes 4 and 6 are connected through factor 2, 6 and 15 share factor 3, and 15 and 35 share factor 5. The largest connected component includes all four numbers, so the output is 4. You must return this largest component size for any valid input array.

Examples

Example 1

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

Output: 4

Example details omitted.

Example 2

Input: nums = [20,50,9,63]

Output: 2

Example details omitted.

Example 3

Input: nums = [2,3,6,7,4,12,21,39]

Output: 8

Example details omitted.

Constraints

1 <= nums.length <= 2 * 104
1 <= nums[i] <= 105
All the values of nums are unique.

Solution Approach

Prime Factorization with Union-Find

For each number in the array, find its prime factors and map them to the number using a hash map. Use union-find to merge sets of numbers sharing the same factor. This ensures numbers with a common factor are grouped efficiently, avoiding direct pairwise comparisons which are too slow for large arrays.

Path Compression Optimization

While performing union operations, apply path compression to flatten the union-find tree structure. This reduces the time complexity for subsequent find operations, making repeated merges and queries faster, especially in dense factor sharing scenarios.

Count Component Sizes

After all union operations, iterate over each number and determine its root in the union-find structure. Maintain a count of numbers per root, and return the maximum count. This directly yields the size of the largest connected component while leveraging the factor-based grouping.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on factorization and union-find operations, roughly O(N sqrt(M)) where N is array length and M is max value. Space complexity is O(N + M) for parent and factor maps. Optimizations like path compression help maintain near-linear performance.

What Interviewers Usually Probe

Candidate attempts naive pairwise GCD checks, which is inefficient for large inputs.
Candidate successfully maps numbers to prime factors, indicating understanding of factor-based graph structure.
Candidate applies union-find with path compression or other optimizations to manage large component merging efficiently.

Common Pitfalls or Variants

Common pitfalls

Trying to compare every pair with GCD, causing TLE on large arrays.
Forgetting to merge all numbers sharing a factor, leading to undercounting component sizes.
Neglecting path compression, resulting in slower union-find operations and exceeding time limits.

Follow-up variants

Compute largest component size considering only prime numbers in the array.
Find the number of connected components rather than the largest size using the same factor-based graph.
Determine largest component size when edges exist for numbers sharing any divisor within a given threshold, not necessarily prime factors.

FAQ

What is the key insight for solving Largest Component Size by Common Factor?

The main insight is mapping each number to its prime factors and using union-find to merge numbers sharing any factor.

Can I use pairwise GCD checks for this problem?

Direct pairwise GCD checks are too slow for large arrays and will likely exceed time limits, making factor mapping essential.

Why is path compression important in this problem?

Path compression reduces the depth of union-find trees, speeding up subsequent find operations and overall component size calculations.

How do I count the size of each connected component efficiently?

After union operations, find each number's root and maintain a frequency map per root, then return the maximum count as the largest component size.

Does this approach work if numbers are not unique?

The solution assumes unique integers for correct mapping of factors; duplicates would require additional handling to merge all occurrences correctly.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

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())

Continue Practicing

#914 x of a kind in a deck of cards #1627 graph connectivity with threshold #957 prison cells after n days