Count Connected Components in LCM Graph - Solution & Explanation

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.