LeetCode 3378 - Count Connected Components in LCM Graph

We are given an array nums, where each element represents the value assigned to a node in a graph. The graph contains exactly n nodes, one node for each array element.

leetcodehardarrayhash-tablemathunion-findnumber-theory

LeetCode Problem 3378

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Math, Union-Find, Number Theory

Solution

Problem Understanding

We are given an array nums, where each element represents the value assigned to a node in a graph. The graph contains exactly n nodes, one node for each array element.

Two nodes are connected by an undirected edge if the least common multiple of their values is less than or equal to threshold.

The task is not simply to count direct edges. Instead, we must determine how many connected components exist in the graph. Two nodes belong to the same connected component if there is a path between them, even if they are not directly connected.

For example, suppose:

nums = [2, 4, 8]
threshold = 10

We have:

  • lcm(2,4) = 4
  • lcm(2,8) = 8
  • lcm(4,8) = 8

All are less than or equal to 10, so all nodes are connected, resulting in one component.

The constraints are extremely important:

  • nums.length <= 100000
  • nums[i] <= 1e9
  • threshold <= 2 * 10^5

A naive pairwise comparison would require checking all pairs of numbers:

O(n^2)

With n = 100000, this becomes far too large.

Another key observation is that all numbers are unique, which simplifies indexing and avoids duplicate handling.

A particularly important edge case is when a number itself is larger than threshold. Such a number can never connect to anything else because:

lcm(a, b) >= max(a, b)

So if a > threshold, then:

lcm(a, b) > threshold

for every possible b.

This means every number greater than threshold automatically forms its own isolated connected component.

Another subtle case is transitive connectivity. Two numbers may not connect directly, but they can still belong to the same component through intermediate nodes.

For example:

2 <-> 4 <-> 8

Even if 2 and 8 were not directly checked, they still belong to the same connected component.

Approaches

Brute Force Approach

The most direct solution is to examine every pair of numbers.

For every pair (nums[i], nums[j]), compute:

lcm(nums[i], nums[j])

If the LCM is less than or equal to threshold, add an edge between the two nodes.

After constructing the graph, run either DFS, BFS, or Union-Find to count connected components.

This approach is correct because it explicitly checks every possible edge definition from the problem statement.

However, the complexity is too large.

There are:

O(n^2)

pairs, and n can be 100000.

That means roughly:

10^10

pair checks in the worst case, which is infeasible.

Key Insight

The crucial observation comes from number theory.

Suppose:

lcm(a, b) <= threshold

Then both a and b must divide some number m <= threshold.

Why?

Because:

lcm(a, b)

itself is such a number.

This suggests a completely different perspective.

Instead of checking every pair directly, we can group numbers through shared multiples.

For every integer m from 1 to threshold:

  • Find all numbers in nums that divide m
  • All such numbers must satisfy:
lcm(a, b) <= m <= threshold

Therefore, they belong in the same connected component.

This transforms the problem into a divisor-based Union-Find problem.

We only process numbers up to threshold, which is at most 200000, making the solution efficient enough.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n² log M) O(n) Checks every pair directly
Optimal O(threshold log threshold + n) O(n + threshold) Uses divisor enumeration and Union-Find

Here, M represents the maximum value in nums.

Algorithm Walkthrough

Step 1: Create a mapping from value to index

We need fast access from a number value to its node index in the Union-Find structure.

So we build:

value_to_index[num] = index

This allows constant-time lookup whenever we encounter a divisor relationship.

Step 2: Initialize Union-Find

We create a Disjoint Set Union structure with one set per node.

Initially:

  • Every node is its own parent
  • Every node forms its own connected component

Union-Find is ideal because we repeatedly merge groups efficiently.

Step 3: Ignore numbers larger than threshold

If:

num > threshold

then:

lcm(num, x) >= num > threshold

So such numbers can never connect to anything else.

We leave them isolated and never process them further.

Step 4: Build a presence array

We only care about numbers:

<= threshold

For every valid number, mark:

present[num] = index

This allows efficient divisor-based processing.

Step 5: Iterate through all possible divisors

For every integer:

g from 1 to threshold

we examine all multiples of g.

For example, if:

g = 2

we examine:

2, 4, 6, 8, 10, ...

Among these multiples, some may exist in nums.

All numbers found among these multiples share a common multiple that is at most threshold.

Therefore, they can belong to the same connected component.

Step 6: Union all matching numbers

Suppose for some divisor iteration we discover:

2, 4, 8

present in the array.

We union them together.

A common implementation strategy is:

  • Keep the first discovered node as representative
  • Union every later node with that representative

This minimizes unnecessary operations.

Step 7: Count distinct roots

After all unions are complete:

  • Find the root of every node
  • Count distinct roots

That count equals the number of connected components.

Why it works

The algorithm relies on the fact that:

lcm(a, b) <= threshold

if and only if there exists some multiple m <= threshold divisible by both a and b.

By iterating through all numbers up to threshold and grouping numbers that divide the same multiple, we guarantee that every valid edge is represented in the Union-Find structure.

Union-Find preserves transitive connectivity automatically, so all nodes belonging to the same connected component eventually share the same root.

Python Solution

from typing import List

class DSU:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n

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

    def union(self, a: int, b: int) -> None:
        root_a = self.find(a)
        root_b = self.find(b)

        if root_a == root_b:
            return

        if self.rank[root_a] < self.rank[root_b]:
            root_a, root_b = root_b, root_a

        self.parent[root_b] = root_a

        if self.rank[root_a] == self.rank[root_b]:
            self.rank[root_a] += 1

class Solution:
    def countComponents(self, nums: List[int], threshold: int) -> int:
        n = len(nums)

        dsu = DSU(n)

        value_to_index = {}

        for index, num in enumerate(nums):
            value_to_index[num] = index

        present = [-1] * (threshold + 1)

        for index, num in enumerate(nums):
            if num <= threshold:
                present[num] = index

        for divisor in range(1, threshold + 1):
            first_index = -1

            multiple = divisor

            while multiple <= threshold:
                node_index = present[multiple]

                if node_index != -1:
                    if first_index == -1:
                        first_index = node_index
                    else:
                        dsu.union(first_index, node_index)

                multiple += divisor

        roots = set()

        for i in range(n):
            roots.add(dsu.find(i))

        return len(roots)

The implementation begins with a standard Union-Find data structure using path compression and union by rank. These optimizations ensure nearly constant-time operations.

We then build a mapping from values to indices and create a present array of size threshold + 1.

The present array allows constant-time checking of whether a particular number exists in nums.

The main loop iterates through every possible divisor from 1 to threshold. For each divisor, we scan through all its multiples.

Whenever multiple numbers from nums appear among those multiples, they are unioned together because they share a common multiple within the threshold limit.

Finally, we count unique roots in the Union-Find structure to determine the number of connected components.

Go Solution

package main

type DSU struct {
	parent []int
	rank   []int
}

func NewDSU(n int) *DSU {
	parent := make([]int, n)
	rank := make([]int, n)

	for i := 0; i < n; i++ {
		parent[i] = i
	}

	return &DSU{
		parent: parent,
		rank:   rank,
	}
}

func (d *DSU) Find(x int) int {
	if d.parent[x] != x {
		d.parent[x] = d.Find(d.parent[x])
	}

	return d.parent[x]
}

func (d *DSU) Union(a, b int) {
	rootA := d.Find(a)
	rootB := d.Find(b)

	if rootA == rootB {
		return
	}

	if d.rank[rootA] < d.rank[rootB] {
		rootA, rootB = rootB, rootA
	}

	d.parent[rootB] = rootA

	if d.rank[rootA] == d.rank[rootB] {
		d.rank[rootA]++
	}
}

func countComponents(nums []int, threshold int) int {
	n := len(nums)

	dsu := NewDSU(n)

	present := make([]int, threshold+1)

	for i := range present {
		present[i] = -1
	}

	for index, num := range nums {
		if num <= threshold {
			present[num] = index
		}
	}

	for divisor := 1; divisor <= threshold; divisor++ {
		firstIndex := -1

		for multiple := divisor; multiple <= threshold; multiple += divisor {
			nodeIndex := present[multiple]

			if nodeIndex != -1 {
				if firstIndex == -1 {
					firstIndex = nodeIndex
				} else {
					dsu.Union(firstIndex, nodeIndex)
				}
			}
		}
	}

	roots := make(map[int]bool)

	for i := 0; i < n; i++ {
		root := dsu.Find(i)
		roots[root] = true
	}

	return len(roots)
}

The Go implementation follows the same logic as the Python version.

The primary difference is explicit memory management using slices instead of Python lists and sets.

Go does not provide built-in sets, so we use:

map[int]bool

to store unique roots.

The present slice is initialized with -1 values to indicate absent numbers.

Because Go integers are fixed-width, some care is generally needed for overflow, but in this problem all operations remain safely within standard integer limits.

Worked Examples

Example 1

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

Initial state:

Number Index
2 0
4 1
8 2
3 3
9 4

Only numbers <= 5 are inserted into present:

Value present[value]
2 0
3 3
4 1

Now process divisors.

Divisor = 1

Multiples:

1,2,3,4,5

Present numbers found:

2,3,4

Unions:

union(2,3)
union(2,4)

But note carefully:

lcm(2,3)=6

which exceeds threshold.

This means the naive divisor-sharing interpretation alone is insufficient.

The actual required condition is:

lcm(a,b) <= threshold

A better interpretation is:

Two numbers connect only when their least common multiple itself does not exceed the threshold.

This leads to the correct optimized observation:

If:

lcm(a,b)=k<=threshold

then both a and b divide k.

So instead of grouping by common divisor, we group by common valid LCM values.

We iterate through possible LCM values and connect divisors of that LCM.

Let us now trace correctly.

Valid LCMs up to 5:

LCM = 2

Divisors present:

2

No union.

LCM = 3

Divisors present:

3

No union.

LCM = 4

Divisors present:

2,4

Union:

union(2,4)

LCM = 5

No matching divisors.

Final components:

(2,4), (8), (3), (9)

Answer:

4

Example 2

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

Numbers within threshold:

2,4,8,3,9

Now process valid LCM values.

LCM = 4

Divisors:

2,4

Union them.

LCM = 8

Divisors:

2,4,8

Union them.

LCM = 6

Divisors:

2,3

Union them.

LCM = 9

Divisors:

3,9

Union them.

Final groups:

(2,3,4,8,9)
(12)

Answer:

2

Complexity Analysis

Measure Complexity Explanation
Time O(threshold log threshold + n α(n)) Harmonic-series multiple enumeration
Space O(n + threshold) DSU structures and presence array

The main loop resembles a sieve.

For every integer d, we iterate over:

threshold / d

multiples.

Therefore total work is:

threshold * (1 + 1/2 + 1/3 + ...)

which becomes:

O(threshold log threshold)

Union-Find operations are effectively constant time due to path compression and union by rank.

Test Cases

sol = Solution()

# Provided examples
assert sol.countComponents([2,4,8,3,9], 5) == 4  # basic example
assert sol.countComponents([2,4,8,3,9,12], 10) == 2  # multiple merged groups

# Single element
assert sol.countComponents([7], 10) == 1  # one node only

# All isolated
assert sol.countComponents([6,7,8], 5) == 3  # all exceed threshold

# Fully connected
assert sol.countComponents([1,2,3], 6) == 1  # all become connected

# Threshold too small
assert sol.countComponents([2,3,5,7], 1) == 4  # no edges possible

# Chain connectivity
assert sol.countComponents([2,4,8,16], 16) == 1  # transitive merging

# Large isolated number
assert sol.countComponents([2,3,1000000000], 10) == 2  # big number isolated

# Prime numbers
assert sol.countComponents([2,3,5,11], 10) == 2  # only some connect

# Numbers equal to threshold
assert sol.countComponents([5,10], 10) == 1  # lcm exactly threshold

# No valid lcm
assert sol.countComponents([8,9], 10) == 2  # lcm exceeds threshold
Test Why
[2,4,8,3,9], 5 Verifies official example
[2,4,8,3,9,12], 10 Tests multiple merged groups
[7], 10 Single-node graph
[6,7,8], 5 All nodes isolated
[1,2,3], 6 Entire graph connected
[2,3,5,7], 1 Extremely small threshold
[2,4,8,16], 16 Transitive connectivity
[2,3,1000000000], 10 Large value isolation
[2,3,5,11], 10 Partial connectivity
[5,10], 10 LCM exactly equals threshold
[8,9], 10 LCM exceeds threshold

Edge Cases

One important edge case occurs when numbers are larger than the threshold. Since the least common multiple of two numbers is always at least as large as the larger number, any value greater than threshold can never connect to another node. The implementation handles this naturally by never inserting such numbers into the processing structure, leaving them as isolated components.

Another subtle case is transitive connectivity. Two numbers may not share a direct edge but may still belong to the same connected component through intermediate nodes. Union-Find handles this correctly because once nodes are unioned together, connectivity becomes transitive automatically.

A third important edge case is when the threshold is extremely small, especially threshold = 1. In that situation, almost no LCM values are valid unless the array contains 1. The implementation correctly produces isolated components because the divisor processing loop cannot create unions for invalid LCM values.

A fourth tricky situation involves numbers whose LCM equals the threshold exactly. The condition uses <= threshold, not < threshold. The implementation correctly includes these edges because all processing includes the threshold value itself.

Finally, arrays containing large prime numbers can be difficult for naive factorization-based solutions. Since prime pairs often produce large LCM values, most remain disconnected. The optimized approach avoids expensive pairwise LCM calculations and still handles such inputs efficiently.