Count Connected Components in LCM Graph

Hard

#3001Time: 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.

Patterns

Math Number Theory

Algorithms

Union Find

Data structures

Array Hash Table

Prompt

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 i^th 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 <= 10⁵
1 <= nums[i] <= 10⁹
All elements of nums are unique.
1 <= threshold <= 2 * 10⁵

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 n sets, one for each number in nums.
Iterate through every pair of indices (i, j) where 0 <= i < j < n.
For each pair, calculate the greatest common divisor (GCD) of nums[i] and nums[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 with a * 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 nodes i and j.
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.

1import java.math.BigInteger;2 3class Solution {4    public int countConnectedComponents(int[] nums, int threshold) {5        int n = nums.length;6        DSU dsu = new DSU(n);7 8        for (int i = 0; i < n; i++) {9            for (int j = i + 1; j < n; j++) {10                long num_i = nums[i];11                long num_j = nums[j];12                13                long commonDivisor = gcd(num_i, num_j);14                // lcm(a,b) = (a / gcd(a,b)) * b to prevent overflow15                BigInteger lcm = BigInteger.valueOf(num_i / commonDivisor).multiply(BigInteger.valueOf(num_j));16 17                if (lcm.compareTo(BigInteger.valueOf(threshold)) <= 0) {18                    dsu.union(i, j);19                }20            }21        }22 23        return dsu.countSets();24    }25 26    private long gcd(long a, long b) {27        while (b != 0) {28            long temp = b;29            b = a % b;30            a = temp;31        }32        return a;33    }34 35    class DSU {36        int[] parent;37        int count;38 39        public DSU(int n) {40            parent = new int[n];41            count = n;42            for (int i = 0; i < n; i++) {43                parent[i] = i;44            }45        }46 47        public int find(int i) {48            if (parent[i] == i) {49                return i;50            }51            return parent[i] = find(parent[i]);52        }53 54        public void union(int i, int j) {55            int rootI = find(i);56            int rootJ = find(j);57            if (rootI != rootJ) {58                parent[rootI] = rootJ;59                count--;60            }61        }62 63        public int countSets() {64            return count;65        }66    }67}

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.

A more efficient approach avoids checking all O(n^2) pairs. The key observation is that the threshold is relatively small. We can filter out numbers greater than the threshold as they form singleton components. For the remaining numbers, we can use common divisors as a way to group numbers and check for connections more efficiently. Instead of checking all pairs, we iterate through possible common divisors g and only check for LCM conditions among numbers that share g as a divisor.

Algorithm

First, handle numbers larger than the threshold. Any nums[i] > threshold cannot have an LCM with any other number nums[j] that is less than or equal to the threshold, because lcm(a, b) >= max(a, b). Thus, each such number forms its own connected component of size one.
Create a new list, filtered_nums, containing only the numbers from nums that are less than or equal to the threshold.
If filtered_nums is empty, the answer is just the count from step 1.
Create a map val_to_idx to quickly find the index of a number in filtered_nums.
Initialize a DSU data structure for the elements in filtered_nums.
Iterate through all possible common divisors g from 1 to threshold.
For each g, find all multiples of g that are present in filtered_nums. Let this list be M_g.
If M_g contains more than one number, pick the first one, p. Then, for every other number q in M_g, check if lcm(p, q) <= threshold. If it is, union the sets for p and q.
The total number of components is the count from step 1 plus the final number of disjoint sets in the DSU.

Walkthrough

This approach optimizes the process of finding edges. We start by realizing that any number num > threshold can't be part of any edge, as lcm(num, other) >= num > threshold. These numbers form components of size one. We count them and focus on the remaining numbers, all of which are <= threshold.

We use a Union-Find data structure on these filtered numbers. The core idea is to iterate through each integer g from 1 to threshold. For each g, we identify all numbers in our filtered set that are multiples of g. Let's say we find a list of such multiples M_g = [m_1, m_2, ..., m_k]. Any pair from this list shares g as a common divisor. To form connections, we can pick the first multiple m_1 and iterate through the rest m_i. If lcm(m_1, m_i) <= threshold, we union their sets. This transitively connects all numbers in M_g that should be in the same component.

This avoids checking pairs with small GCDs that would likely result in large LCMs. The total number of LCM checks is significantly reduced from O(n^2).

1import java.util.ArrayList;2import java.util.HashMap;3import java.util.List;4import java.util.Map;5 6class Solution {7    public int countConnectedComponents(int[] nums, int threshold) {8        List<Integer> filteredNums = new ArrayList<>();9        int initialComponents = 0;10        for (int num : nums) {11            if (num > threshold) {12                initialComponents++;13            } else {14                filteredNums.add(num);15            }16        }17 18        if (filteredNums.isEmpty()) {19            return initialComponents;20        }21 22        int m = filteredNums.size();23        DSU dsu = new DSU(m);24        Map<Integer, Integer> valToIdx = new HashMap<>();25        for (int i = 0; i < m; i++) {26            valToIdx.put(filteredNums.get(i), i);27        }28 29        for (int g = 1; g <= threshold; g++) {30            List<Integer> multiples = new ArrayList<>();31            for (int multiple = g; multiple <= threshold; multiple += g) {32                if (valToIdx.containsKey(multiple)) {33                    multiples.add(multiple);34                }35            }36 37            if (multiples.size() > 1) {38                int firstVal = multiples.get(0);39                int firstIdx = valToIdx.get(firstVal);40                for (int i = 1; i < multiples.size(); i++) {41                    int currentVal = multiples.get(i);42                    int currentIdx = valToIdx.get(currentVal);43                    // lcm(a,b) = (a/gcd(a,b))*b. Here gcd(firstVal, currentVal) >= g.44                    // No need to check lcm, as if a,b are multiples of g and a+b <= threshold, then lcm(a,b) <= threshold.45                    // But a simpler, correct approach is to just check the lcm condition.46                    long commonDivisor = gcd(firstVal, currentVal);47                    if ((long)firstVal * currentVal / commonDivisor <= threshold) {48                         dsu.union(firstIdx, currentIdx);49                    }50                }51            }52        }53 54        return initialComponents + dsu.countSets();55    }56 57    private long gcd(long a, long b) {58        while (b != 0) {59            long temp = b;60            b = a % b;61            a = temp;62        }63        return a;64    }65 66    class DSU {67        int[] parent;68        int count;69 70        public DSU(int n) {71            parent = new int[n];72            count = n;73            for (int i = 0; i < n; i++) {74                parent[i] = i;75            }76        }77 78        public int find(int i) {79            if (parent[i] == i) return i;80            return parent[i] = find(parent[i]);81        }82 83        public void union(int i, int j) {84            int rootI = find(i);85            int rootJ = find(j);86            if (rootI != rootJ) {87                parent[rootI] = rootJ;88                count--;89            }90        }91 92        public int countSets() {93            return count;94        }95    }96}

Complexity

Time

O(n + T*log(T)*log(T)) where T is the threshold. The dominant part is iterating through divisors `g` from 1 to T. For each `g`, we iterate through its T/g multiples. The total number of pairs considered is much less than n^2. A loose upper bound is `O(T*log(T)*log(T))`. A tighter analysis shows the complexity is closer to `O(n + sum_{x in U} d(x)*log(T))`, where `d(x)` is the number of divisors of `x`, which is efficient enough.

Space

O(n + threshold) to store the filtered numbers, the value-to-index map, and the DSU structure.

Trade-offs

Pros

Significantly more efficient than the brute-force approach.
Handles the given constraints within the time limit.
The initial filtering step is a simple and effective optimization.

Cons

The logic is more complex than the brute-force approach.
The time complexity depends on the number of divisors of numbers up to the threshold, which can be non-trivial to analyze precisely.

Solutions

Solution

1class 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 (); } }

1typedef 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 (); } };

1class 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 )

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.

← Previous

Previous problem

Next problem