Count Connected Components in LCM Graph
HardPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
The most straightforward approach is to model the problem directly. We can construct the graph by considering every possible pair of nodes and checking if an edge exists between them based on the LCM condition. After building the graph (or determining all edges), we can count the connected components.
Algorithm
- Initialize a Disjoint Set Union (DSU) data structure with
nsets, one for each number innums. - Iterate through every pair of indices
(i, j)where0 <= i < j < n. - For each pair, calculate the greatest common divisor (GCD) of
nums[i]andnums[j]using the Euclidean algorithm. - Calculate the least common multiple (LCM) using the formula
lcm(a, b) = (a * b) / gcd(a, b). To avoid potential overflow witha * b, it's better to compute it as(a / gcd(a, b)) * b. - If
lcm(nums[i], nums[j]) <= threshold, perform a union operation on the sets containing nodesiandj. - After checking all pairs, the number of connected components is the number of disjoint sets remaining in the DSU.
Walkthrough
This method involves iterating through all unique pairs of numbers in the input array nums. For each pair (nums[i], nums[j]), we check if they should be connected. The condition for an edge is lcm(nums[i], nums[j]) <= threshold.
To manage the connected components, a Disjoint Set Union (DSU) or Union-Find data structure is ideal. We initialize n disjoint sets, one for each element in nums. Then, for each pair (i, j) that satisfies the LCM condition, we merge the sets to which i and j belong.
The final count of disjoint sets gives the number of connected components in the graph.
import java.math.BigInteger; class Solution { public int countConnectedComponents(int[] nums, int threshold) { int n = nums.length; DSU dsu = new DSU(n); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { long num_i = nums[i]; long num_j = nums[j]; long commonDivisor = gcd(num_i, num_j); // lcm(a,b) = (a / gcd(a,b)) * b to prevent overflow BigInteger lcm = BigInteger.valueOf(num_i / commonDivisor).multiply(BigInteger.valueOf(num_j)); if (lcm.compareTo(BigInteger.valueOf(threshold)) <= 0) { dsu.union(i, j); } } } return dsu.countSets(); } private long gcd(long a, long b) { while (b != 0) { long temp = b; b = a % b; a = temp; } return a; } class DSU { int[] parent; int count; public DSU(int n) { parent = new int[n]; count = n; for (int i = 0; i < n; i++) { parent[i] = i; } } public int find(int i) { if (parent[i] == i) { return i; } return parent[i] = find(parent[i]); } public void union(int i, int j) { int rootI = find(i); int rootJ = find(j); if (rootI != rootJ) { parent[rootI] = rootJ; count--; } } public int countSets() { return count; } }}Complexity
Time
O(n^2 * log(max(nums))) due to iterating through O(n^2) pairs and performing a GCD calculation for each, which takes logarithmic time.
Space
O(n) for the DSU data structure.
Trade-offs
Pros
Simple to understand and implement.
Correctly models the problem definition without complex transformations.
Cons
The time complexity of O(n^2) is too slow for the given constraints (n <= 10^5), leading to a Time Limit Exceeded (TLE) error.
The space complexity for an explicit graph representation (adjacency list) could be up to O(n^2) in a dense graph, which is too large for the given memory limits.
Solutions
Solution
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 (); } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.