#3378

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Count Connected Components in LCM Graph

Determine the number of connected components in an LCM-based graph using array scanning and hash-based connectivity checks.

array hash table math union find number theory

Problem Statement

You are given an array nums of unique integers and a positive integer threshold. Construct a graph where each node represents an element in nums, and an undirected edge exists between nodes i and j if the least common multiple of nums[i] and nums[j] is less than or equal to threshold.

Your task is to calculate and return the total number of connected components in this graph. Efficient handling requires combining array scanning with hash lookups and union-find structures to avoid redundant LCM calculations.

Examples

Example 1

Input: nums = [2,4,8,3,9], threshold = 5

Output: 4

The four connected components are (2, 4) , (3) , (8) , (9) .

Example 2

Input: nums = [2,4,8,3,9,12], threshold = 10

Output: 2

The two connected components are (2, 3, 4, 8, 9) , and (12) .

Constraints

1 <= nums.length <= 105
1 <= nums[i] <= 109
All elements of nums are unique.
1 <= threshold <= 2 * 105

Solution Approach

Map values to indices and initialize DSU

Create a mapping from each number in nums to its index. Initialize a Disjoint Set Union structure to track connected components. This ensures union operations are fast and reduces redundant searches.

Scan multiples within threshold

Iterate through nums, and for each number, check its multiples up to the threshold. Use hash lookups to find valid connections and union the corresponding indices. This reduces LCM computations and directly identifies connectivity patterns.

Count connected components

After processing all unions, count the distinct sets in the DSU. Each unique parent represents a connected component. This efficiently calculates the result while maintaining the array scanning plus hash lookup pattern.

Complexity Analysis

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

Time complexity depends on scanning multiples up to the threshold and performing union operations, roughly O(n * log n) with DSU optimizations. Space complexity is O(n) for the DSU and O(n) for the value-to-index mapping.

What Interviewers Usually Probe

They may ask why scanning multiples is preferred over pairwise LCM checks.
Look for questions about union-find optimization and path compression trade-offs.
They might probe understanding of threshold impacts on connected components.

Common Pitfalls or Variants

Common pitfalls

Performing O(n^2) LCM checks instead of scanning multiples.
Forgetting to map values to indices before union operations.
Neglecting to account for DSU path compression and union by rank.

Follow-up variants

Change the connectivity condition to GCD instead of LCM.
Use a different threshold calculation or dynamic threshold per pair.
Count components when nums contains repeated values with modified DSU handling.

FAQ

What is the best approach for Count Connected Components in LCM Graph?

Use array scanning with hash lookups and a DSU structure to merge nodes whose LCM is within the threshold efficiently.

Why is pairwise LCM calculation inefficient?

Pairwise LCM checking is O(n^2) and slow for large arrays; scanning multiples with hash lookups avoids redundant computations.

How does DSU help in counting components?

DSU tracks connected sets efficiently; after all unions, each unique parent represents a connected component.

Can this approach handle large thresholds?

Yes, by limiting multiples scanning and using hash maps, the approach scales even when threshold is large.

Do we need to sort nums first?

No, mapping values to indices allows unions without sorting while preserving array scanning plus hash lookup efficiency.

terminal

Solution

Solution 1: Union Find

#### 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

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

class DSU:
    def __init__(self, n):
        self.parent = {i: i for i in range(n)}
        self.rank = {i: 0 for i in range(n)}

    def make_set(self, v):
        self.parent[v] = v
        self.rank[v] = 1

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union_set(self, u, v):
        u = self.find(u)
        v = self.find(v)
        if u != v:
            if self.rank[u] < self.rank[v]:
                u, v = v, u
            self.parent[v] = u
            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1


class Solution:
    def countComponents(self, nums, threshold):
        dsu = DSU(threshold + 1)

        for num in nums:
            for j in range(num, threshold + 1, num):
                dsu.union_set(num, j)

        unique_parents = set()
        for num in nums:
            if num > threshold:
                unique_parents.add(num)
            else:
                unique_parents.add(dsu.find(num))

        return len(unique_parents)

Solution 2: DFS

#### 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

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

class DSU:
    def __init__(self, n):
        self.parent = {i: i for i in range(n)}
        self.rank = {i: 0 for i in range(n)}

    def make_set(self, v):
        self.parent[v] = v
        self.rank[v] = 1

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union_set(self, u, v):
        u = self.find(u)
        v = self.find(v)
        if u != v:
            if self.rank[u] < self.rank[v]:
                u, v = v, u
            self.parent[v] = u
            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1


class Solution:
    def countComponents(self, nums, threshold):
        dsu = DSU(threshold + 1)

        for num in nums:
            for j in range(num, threshold + 1, num):
                dsu.union_set(num, j)

        unique_parents = set()
        for num in nums:
            if num > threshold:
                unique_parents.add(num)
            else:
                unique_parents.add(dsu.find(num))

        return len(unique_parents)

Continue Practicing

#3312 sorted gcd pair queries #3591 check if any element has prime frequency #3044 most frequent prime