Count Connected Components in LCM Graph solution and explanation
2 more videos on this problem
3378. Count Connected Components in LCM Graph | Factors/Divisors | DSU | Graph + Math | Part-1Aryan Mittal · 35:09 · 1K views
3378. Count Connected Components in LCM Graph | Factors/Divisors | DSU | Graph + Math | Part-2Aryan Mittal · 11:55 · 947 views
3378. Count Connected Components in LCM Graph (Leetcode Hard)Programming Live with Larry · 34:59 · 267 views
The problem
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 <= 1051 <= nums[i] <= 109- All elements of
numsare 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
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)class DSU {
private Map<Integer, Integer> parent;
private Map<Integer, Integer> rank;
public DSU(int n) {
parent = new HashMap<>();
rank = new HashMap<>();
for (int i = 0; i <= n; i++) {
parent.put(i, i);
rank.put(i, 0);
}
}
public void makeSet(int v) {
parent.put(v, v);
rank.put(v, 1);
}
public int find(int x) {
if (parent.get(x) != x) {
parent.put(x, find(parent.get(x)));
}
return parent.get(x);
}
public void unionSet(int u, int v) {
u = find(u);
v = find(v);
if (u != v) {
if (rank.get(u) < rank.get(v)) {
int temp = u;
u = v;
v = temp;
}
parent.put(v, u);
if (rank.get(u).equals(rank.get(v))) {
rank.put(u, rank.get(u) + 1);
}
}
}
}
class Solution {
public int countComponents(int[] nums, int threshold) {
DSU dsu = new DSU(threshold);
for (int num : nums) {
for (int j = num; j <= threshold; j += num) {
dsu.unionSet(num, j);
}
}
Set<Integer> uniqueParents = new HashSet<>();
for (int num : nums) {
if (num > threshold) {
uniqueParents.add(num);
} else {
uniqueParents.add(dsu.find(num));
}
}
return uniqueParents.size();
}
}typedef struct DSU {
unordered_map<int, int> par, rank;
DSU(int n) {
for (int i = 0; i < n; ++i) {
par[i] = i;
rank[i] = 0;
}
}
void makeSet(int v) {
par[v] = v;
rank[v] = 1;
}
int find(int x) {
if (par[x] == x) {
return x;
}
return par[x] = find(par[x]);
}
void unionSet(int u, int v) {
u = find(u);
v = find(v);
if (u != v) {
if (rank[u] < rank[v]) swap(u, v);
par[v] = u;
if (rank[u] == rank[v]) rank[u]++;
}
}
} DSU;
class Solution {
public:
int countComponents(vector<int> &nums, int threshold) {
DSU dsu(threshold);
for (auto &num : nums) {
for (int j = num; j <= threshold; j += num) {
dsu.unionSet(num, j);
}
}
unordered_set<int> par;
for (auto &num : nums) {
if (num > threshold) {
par.insert(num);
} else {
par.insert(dsu.find(num));
}
}
return par.size();
}
};type DSU struct {
parent map[int]int
rank map[int]int
}
func NewDSU(n int) *DSU {
dsu := &DSU{
parent: make(map[int]int),
rank: make(map[int]int),
}
for i := 0; i <= n; i++ {
dsu.parent[i] = i
dsu.rank[i] = 0
}
return dsu
}
func (dsu *DSU) Find(x int) int {
if dsu.parent[x] != x {
dsu.parent[x] = dsu.Find(dsu.parent[x])
}
return dsu.parent[x]
}
func (dsu *DSU) Union(u, v int) {
uRoot := dsu.Find(u)
vRoot := dsu.Find(v)
if uRoot != vRoot {
if dsu.rank[uRoot] < dsu.rank[vRoot] {
uRoot, vRoot = vRoot, uRoot
}
dsu.parent[vRoot] = uRoot
if dsu.rank[uRoot] == dsu.rank[vRoot] {
dsu.rank[uRoot]++
}
}
}
func countComponents(nums []int, threshold int) int {
dsu := NewDSU(threshold)
for _, num := range nums {
for j := num; j <= threshold; j += num {
dsu.Union(num, j)
}
}
uniqueParents := make(map[int]struct{})
for _, num := range nums {
if num > threshold {
uniqueParents[num] = struct{}{}
} else {
uniqueParents[dsu.Find(num)] = struct{}{}
}
}
return len(uniqueParents)
}Approach 2: DFS
class Solution:
def dfs(self, node, adj, vis):
if vis[node]:
return
vis[node] = True
for neighbor in adj[node]:
self.dfs(neighbor, adj, vis)
def countComponents(self, nums, threshold):
adj = [[] for _ in range(threshold + 1)]
vis = [False] * (threshold + 1)
ans = 0
for num in nums:
if num > threshold:
ans += 1
continue
for j in range(2 * num, threshold + 1, num):
adj[num].append(j)
adj[j].append(num)
for num in nums:
if num <= threshold and not vis[num]:
self.dfs(num, adj, vis)
ans += 1
return ansclass Solution {
private void dfs(int node, List<List<Integer>> adj, boolean[] visited) {
if (visited[node]) return;
visited[node] = true;
for (int neighbor : adj.get(node)) {
dfs(neighbor, adj, visited);
}
}
public int countComponents(int[] nums, int threshold) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i <= threshold; i++) {
adj.add(new ArrayList<>());
}
boolean[] visited = new boolean[threshold + 1];
int ans = 0;
for (int num : nums) {
if (num > threshold) {
ans++;
continue;
}
for (int j = 2 * num; j <= threshold; j += num) {
adj.get(num).add(j);
adj.get(j).add(num);
}
}
for (int num : nums) {
if (num <= threshold && !visited[num]) {
dfs(num, adj, visited);
ans++;
}
}
return ans;
}
}class Solution {
private:
void dfs(int node, vector<vector<int>> &adj, vector<bool> &vis) {
if (vis[node]) return;
vis[node] = true;
for (auto &u : adj[node]) {
dfs(u, adj, vis);
}
}
public:
int countComponents(vector<int> &nums, int threshold) {
vector<vector<int>> adj(threshold + 1);
vector<bool> vis(threshold + 1, false);
int ans = 0;
for (auto &num : nums) {
if (num > threshold) {
++ans;
continue;
}
for (int j = 2 * num; j <= threshold; j += num) {
adj[num].push_back(j);
adj[j].push_back(num);
}
}
for (auto &num : nums) {
if (num <= threshold && !vis[num]) {
dfs(num, adj, vis);
++ans;
}
}
return ans;
}
};func dfs(node int, adj [][]int, visited []bool) {
if visited[node] {
return
}
visited[node] = true
for _, neighbor := range adj[node] {
dfs(neighbor, adj, visited)
}
}
func countComponents(nums []int, threshold int) int {
adj := make([][]int, threshold+1)
for i := range adj {
adj[i] = []int{}
}
visited := make([]bool, threshold+1)
components := 0
for _, num := range nums {
if num > threshold {
components++
continue
}
for j := 2 * num; j <= threshold; j += num {
adj[num] = append(adj[num], j)
adj[j] = append(adj[j], num)
}
}
for _, num := range nums {
if num <= threshold && !visited[num] {
dfs(num, adj, visited)
components++
}
}
return components
}Complexity comparison
| Approach | Complexity |
|---|---|
| Union Find | – |
| DFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Graph Construction + DFS | O(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 |
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.