Skip to main content
Talentd

Count Connected Components in LCM Graph - Solution & Explanation

HardArrayHash TableMathUnion Find6 min read
Practice this problem

Problem Statement

You are given an array of integers nums of size n and a positive integer threshold.

There is a graph consisting of n nodes with the ith node having a value of nums[i]. Two nodes i and j in the graph are connected via an undirected edge if lcm(nums[i], nums[j]) <= threshold.

Return the number of connected components in this graph.

A connected component is a subgraph of a graph in which there exists a path between any two vertices, and no vertex of the subgraph shares an edge with a vertex outside of the subgraph.

The term lcm(a, b) denotes the least common multiple of a and b.

 

Example 1:

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

Output: 4

Explanation: 

 

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

Example 2:

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

Output: 2

Explanation: 

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

Approach Overview

Problem Overview: You are given an array of integers and a threshold. Treat each value as a node. Two nodes are connected if the lcm(a, b) of their values is less than or equal to the threshold. The task is to determine how many connected components exist in this implicit graph.

Approach 1: Union Find with Multiples (≈ O(T log T) time, O(T) space)

The key observation is that if lcm(a, b) ≤ threshold, both numbers must divide some common multiple that is also ≤ threshold. Instead of checking every pair (which would be too slow), iterate through values up to the threshold and connect numbers through their multiples. Use a Union Find structure to merge indices whose values share a valid LCM relationship. For each number x, iterate through multiples k * x that do not exceed the threshold and union the nodes containing those values. Numbers greater than the threshold cannot form valid LCM edges with others and remain isolated components. Path compression and union-by-rank keep operations nearly constant time.

Approach 2: Graph Construction + DFS (O(n² log(max)) time, O(n²) space)

A direct approach constructs the graph explicitly. For every pair of numbers, compute lcm(a, b) = a * b / gcd(a, b). If the result is ≤ threshold, add an undirected edge. After building the adjacency list, run DFS or BFS to count connected components. This uses standard graph traversal techniques. The main drawback is the quadratic pair check and repeated gcd calculations, making it impractical for large inputs.

The efficient solution relies heavily on insights from number theory. Instead of evaluating LCM for every pair, it groups numbers through shared multiples that stay within the threshold.

Recommended for interviews: The Union Find approach is what interviewers typically expect. It demonstrates that you can translate a number theory constraint into a connectivity problem and optimize pairwise checks using disjoint sets. Explaining the brute-force pair comparison first shows understanding of the graph definition, while transitioning to Union Find with multiples shows the algorithmic insight needed to scale the solution.

Approach 1: Union Find

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Approach 2: DFS

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Union Find—
DFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Graph Construction + DFSO(n² log M)O(n²)Useful for understanding the definition of the LCM graph or when n is very small
Union Find with Multiples≈ O(T log T)O(T)Optimal approach for large inputs; avoids pairwise LCM checks using number theory

Video Solution

3378. Count Connected Components in LCM Graph | Factors/Divisors | DSU | Graph + Math | Part-1 • Aryan Mittal • 1,784 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Count Connected Components in LCM Graph easy or hard?
The problem is classified as Hard because it requires combining graph connectivity, number theory, and Union Find optimization. The brute-force idea is straightforward, but recognizing how to connect numbers through shared multiples within the threshold is the challenging insight.
Count Connected Components in LCM Graph Python/Java solution
Most implementations use Union Find with path compression and union-by-rank. The algorithm iterates through multiples up to the threshold and unions indices that share valid LCM relationships. The same logic translates easily across Python, Java, C++, and Go.
How to solve Count Connected Components in LCM Graph in O(T log T)?
Use a Union Find structure and iterate through numbers up to the threshold. For each value x, union nodes corresponding to its multiples (2x, 3x, 4x, ...) that remain ≤ threshold. This groups numbers whose LCM stays within the limit without explicitly checking every pair.
What is the best approach for Count Connected Components in LCM Graph?
The most efficient approach uses Union Find combined with number theory. Instead of checking every pair of numbers, you connect values through shared multiples that do not exceed the threshold. This reduces the complexity to roughly O(T log T) and efficiently groups nodes into components.
Is Count Connected Components in LCM Graph asked at Google/Amazon/Meta?
Problems combining Union Find and number theory frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving LCM, GCD, or connectivity through divisibility are common because they test mathematical reasoning and graph modeling skills.
What data structure is used in Count Connected Components in LCM Graph?
The primary data structure is Union Find (Disjoint Set Union). It efficiently merges nodes that share a valid LCM relationship and allows quick checks of whether two nodes belong to the same component. Graph traversal with DFS or BFS can also be used in the brute-force approach.
What is the time complexity of Count Connected Components in LCM Graph?
The optimized Union Find solution runs in about O(T log T), where T is the threshold used for iterating through multiples. Each union and find operation is nearly constant due to path compression. A naive pairwise solution requires O(n² log M) time because it computes LCM for every pair.

Ready to solve this problem?

Practice Count Connected Components in LCM Graph with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays