3378. Count Connected Components in LCM Graph

HardUnion FindArrayHash TableMathNumber Theory

Leetcode Link

Problem Description

You have an array nums containing n integers and a positive integer threshold.

Create a graph with n nodes where:

Node i has value nums[i]
Two nodes i and j are connected by an undirected edge if lcm(nums[i], nums[j]) <= threshold

The least common multiple (LCM) of two numbers is the smallest positive integer that is divisible by both numbers.

Your task is to count the number of connected components in this graph.

A connected component is a group of nodes where:

You can reach any node from any other node in the group by following edges
No node in the group has an edge to any node outside the group

Example breakdown:

If nums = [2, 3, 6] and threshold = 10:
- lcm(2, 3) = 6 <= 10 → nodes with values 2 and 3 are connected
- lcm(2, 6) = 6 <= 10 → nodes with values 2 and 6 are connected
- lcm(3, 6) = 6 <= 10 → nodes with values 3 and 6 are connected
- All three nodes form one connected component, so return 1

The solution uses Union-Find (Disjoint Set Union) to efficiently group nodes. For each number in nums, it unions that number with all its multiples up to the threshold. This works because if two numbers share a common multiple within the threshold, they can be connected through that multiple. Numbers greater than the threshold cannot connect to anything and form isolated components.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key insight is recognizing that we don't need to check every pair of numbers to determine if they're connected. Instead, we can leverage the relationship between numbers and their multiples.

Consider two numbers a and b. Their LCM can be calculated as lcm(a, b) = (a * b) / gcd(a, b). For the LCM to be within the threshold, these numbers must share some mathematical relationship.

Here's the crucial observation: if two numbers a and b have lcm(a, b) <= threshold, then their LCM is a common multiple of both numbers that's within the threshold. This means both a and b divide their LCM evenly.

Instead of checking all pairs directly, we can think differently:

For each number num in our array, all multiples of num up to the threshold (i.e., num, 2*num, 3*num, ...) are potential connection points
If two different numbers from our array share a common multiple within the threshold, they can be connected through that multiple

For example, if we have numbers 2 and 3 with threshold 10:

Multiples of 2 within threshold: 2, 4, 6, 8, 10
Multiples of 3 within threshold: 3, 6, 9
They share the multiple 6, which means lcm(2, 3) = 6 <= 10

This transforms our problem into a union-find problem where:

We union each number with all its multiples up to the threshold
Numbers that share common multiples will end up in the same connected component
Numbers greater than the threshold can't have any valid LCM with other numbers (since their LCM would exceed the threshold), so they form isolated components

This approach is efficient because instead of checking O(n²) pairs, we only iterate through multiples of each number up to the threshold.

Learn more about Union Find and Math patterns.

Solution Implementation

1class DSU: 2 """Disjoint Set Union (Union-Find) data structure for efficient set operations.""" 3 4 def __init__(self, n: int) -> None: 5 """ 6 Initialize DSU with n elements (0 to n-1). 7 8 Args: 9 n: Number of elements in the DSU 10 """ 11 # Each element is initially its own parent (self-loop indicates root) 12 self.parent = {i: i for i in range(n)} 13 # Rank is used for union by rank optimization (tree height) 14 self.rank = {i: 0 for i in range(n)} 15 16 def make_set(self, v: int) -> None: 17 """ 18 Create a new set containing only element v. 19 20 Args: 21 v: Element to create a new set for 22 """ 23 self.parent[v] = v 24 self.rank[v] = 1 25 26 def find(self, x: int) -> int: 27 """ 28 Find the root/representative of the set containing element x. 29 Uses path compression optimization. 30 31 Args: 32 x: Element to find the root for 33 34 Returns: 35 Root element of the set containing x 36 """ 37 # Path compression: make all nodes on path point directly to root 38 if self.parent[x] != x: 39 self.parent[x] = self.find(self.parent[x]) 40 return self.parent[x] 41 42 def union_set(self, u: int, v: int) -> None: 43 """ 44 Unite the sets containing elements u and v. 45 Uses union by rank optimization. 46 47 Args: 48 u: First element 49 v: Second element 50 """ 51 # Find roots of both elements 52 root_u = self.find(u) 53 root_v = self.find(v) 54 55 # Only unite if they're in different sets 56 if root_u != root_v: 57 # Union by rank: attach smaller tree under larger tree 58 if self.rank[root_u] < self.rank[root_v]: 59 root_u, root_v = root_v, root_u 60 61 # Make root_u the parent of root_v 62 self.parent[root_v] = root_u 63 64 # Update rank if both trees had same height 65 if self.rank[root_u] == self.rank[root_v]: 66 self.rank[root_u] += 1 67 68 69class Solution: 70 """Solution class for counting connected components based on divisibility.""" 71 72 def countComponents(self, nums: list[int], threshold: int) -> int: 73 """ 74 Count the number of connected components where numbers are connected 75 if they share a common divisor greater than 1 and less than or equal to threshold. 76 77 Args: 78 nums: List of integers to group into components 79 threshold: Maximum value to consider for divisibility connections 80 81 Returns: 82 Number of connected components 83 """ 84 # Initialize DSU for values up to threshold 85 dsu = DSU(threshold + 1) 86 87 # Connect numbers based on their multiples 88 for num in nums: 89 # Only process numbers within threshold 90 if num <= threshold: 91 # Connect num with all its multiples up to threshold 92 # Start from 2*num since num itself is already handled 93 for multiple in range(num * 2, threshold + 1, num): 94 dsu.union_set(num, multiple) 95 96 # Find unique component representatives 97 unique_components = set() 98 99 for num in nums: 100 if num > threshold: 101 # Numbers greater than threshold form their own components 102 unique_components.add(num) 103 else: 104 # Find the root representative of the component 105 unique_components.add(dsu.find(num)) 106 107 # Return the total number of unique components 108 return len(unique_components) 109

1/** 2 * Disjoint Set Union (Union-Find) data structure implementation 3 * Used for efficiently managing disjoint sets and performing union operations 4 */ 5class DSU { 6 // Maps each element to its parent in the disjoint set tree 7 private Map<Integer, Integer> parent; 8 // Maps each element to its rank (used for union by rank optimization) 9 private Map<Integer, Integer> rank; 10 11 /** 12 * Initialize DSU with elements from 0 to n 13 * @param n The maximum element value 14 */ 15 public DSU(int n) { 16 parent = new HashMap<>(); 17 rank = new HashMap<>(); 18 19 // Initially, each element is its own parent (self-loop) 20 // All elements start with rank 0 21 for (int i = 0; i <= n; i++) { 22 parent.put(i, i); 23 rank.put(i, 0); 24 } 25 } 26 27 /** 28 * Create a new set containing only element v 29 * @param v The element to create a set for 30 */ 31 public void makeSet(int v) { 32 parent.put(v, v); 33 rank.put(v, 1); 34 } 35 36 /** 37 * Find the root/representative of the set containing element x 38 * Uses path compression optimization for better performance 39 * @param x The element to find the root for 40 * @return The root element of the set containing x 41 */ 42 public int find(int x) { 43 // Path compression: Make all nodes on the path point directly to root 44 if (parent.get(x) != x) { 45 parent.put(x, find(parent.get(x))); 46 } 47 return parent.get(x); 48 } 49 50 /** 51 * Union two sets containing elements u and v 52 * Uses union by rank to maintain balanced trees 53 * @param u First element 54 * @param v Second element 55 */ 56 public void unionSet(int u, int v) { 57 // Find roots of both elements 58 int rootU = find(u); 59 int rootV = find(v); 60 61 // If already in same set, no union needed 62 if (rootU != rootV) { 63 // Union by rank: attach smaller rank tree under root of higher rank tree 64 if (rank.get(rootU) < rank.get(rootV)) { 65 // Swap to ensure rootU has higher or equal rank 66 int temp = rootU; 67 rootU = rootV; 68 rootV = temp; 69 } 70 71 // Make rootU the parent of rootV 72 parent.put(rootV, rootU); 73 74 // Update rank if both trees had same rank 75 if (rank.get(rootU).equals(rank.get(rootV))) { 76 rank.put(rootU, rank.get(rootU) + 1); 77 } 78 } 79 } 80} 81 82/** 83 * Solution class to count connected components based on common divisors 84 */ 85class Solution { 86 /** 87 * Count the number of connected components formed by numbers sharing common divisors 88 * Numbers are connected if they share a common divisor <= threshold 89 * @param nums Array of numbers to process 90 * @param threshold Maximum value to consider for common divisors 91 * @return Number of connected components 92 */ 93 public int countComponents(int[] nums, int threshold) { 94 // Initialize DSU with size up to threshold 95 DSU dsu = new DSU(threshold); 96 97 // Connect numbers through their multiples 98 for (int num : nums) { 99 // For each number, connect it with all its multiples up to threshold 100 // This effectively groups numbers that share common divisors 101 for (int multiple = num; multiple <= threshold; multiple += num) { 102 dsu.unionSet(num, multiple); 103 } 104 } 105 106 // Count unique components 107 Set<Integer> uniqueParents = new HashSet<>(); 108 109 for (int num : nums) { 110 if (num > threshold) { 111 // Numbers greater than threshold form their own component 112 uniqueParents.add(num); 113 } else { 114 // Find the root of the component containing this number 115 uniqueParents.add(dsu.find(num)); 116 } 117 } 118 119 // Return the total number of unique components 120 return uniqueParents.size(); 121 } 122} 123

1// Disjoint Set Union (Union-Find) data structure with path compression and union by rank 2struct DSU { 3 unordered_map<int, int> parent; // Maps element to its parent 4 unordered_map<int, int> rank; // Rank for union by rank optimization 5 6 // Constructor: Initialize DSU with n elements (0 to n-1) 7 DSU(int n) { 8 for (int i = 0; i < n; ++i) { 9 parent[i] = i; // Each element is initially its own parent 10 rank[i] = 0; // Initial rank is 0 11 } 12 } 13 14 // Create a new set with element v as its representative 15 void makeSet(int v) { 16 parent[v] = v; 17 rank[v] = 1; 18 } 19 20 // Find the representative of the set containing x with path compression 21 int find(int x) { 22 if (parent[x] == x) { 23 return x; // x is the representative 24 } 25 // Path compression: make all nodes point directly to the root 26 return parent[x] = find(parent[x]); 27 } 28 29 // Unite the sets containing u and v using union by rank 30 void unionSet(int u, int v) { 31 u = find(u); // Find representative of u's set 32 v = find(v); // Find representative of v's set 33 34 if (u != v) { // Only unite if they're in different sets 35 // Union by rank: attach smaller tree under root of larger tree 36 if (rank[u] < rank[v]) { 37 swap(u, v); 38 } 39 parent[v] = u; // Make u the parent of v 40 41 // Update rank if both trees had same rank 42 if (rank[u] == rank[v]) { 43 rank[u]++; 44 } 45 } 46 } 47}; 48 49class Solution { 50public: 51 // Count the number of connected components after grouping numbers by GCD > 1 52 int countComponents(vector<int>& nums, int threshold) { 53 // Initialize DSU with elements from 0 to threshold 54 DSU dsu(threshold + 1); 55 56 // Group numbers that share common factors 57 // For each number, unite it with all its multiples up to threshold 58 for (auto& num : nums) { 59 // Connect num with all its multiples (num, 2*num, 3*num, ...) 60 for (int multiple = num; multiple <= threshold; multiple += num) { 61 dsu.unionSet(num, multiple); 62 } 63 } 64 65 // Count unique components by finding representative of each number 66 unordered_set<int> uniqueComponents; 67 for (auto& num : nums) { 68 if (num > threshold) { 69 // Numbers greater than threshold form their own component 70 uniqueComponents.insert(num); 71 } else { 72 // Find the representative of the component containing num 73 uniqueComponents.insert(dsu.find(num)); 74 } 75 } 76 77 // Return the total number of unique components 78 return uniqueComponents.size(); 79 } 80}; 81

1// Disjoint Set Union (Union-Find) data structure with path compression and union by rank 2const parent: Map<number, number> = new Map(); // Maps element to its parent 3const rank: Map<number, number> = new Map(); // Rank for union by rank optimization 4 5// Initialize DSU with n elements (0 to n-1) 6function initializeDSU(n: number): void { 7 for (let i = 0; i < n; i++) { 8 parent.set(i, i); // Each element is initially its own parent 9 rank.set(i, 0); // Initial rank is 0 10 } 11} 12 13// Create a new set with element v as its representative 14function makeSet(v: number): void { 15 parent.set(v, v); 16 rank.set(v, 1); 17} 18 19// Find the representative of the set containing x with path compression 20function find(x: number): number { 21 if (parent.get(x) === x) { 22 return x; // x is the representative 23 } 24 // Path compression: make all nodes point directly to the root 25 const root = find(parent.get(x)!); 26 parent.set(x, root); 27 return root; 28} 29 30// Unite the sets containing u and v using union by rank 31function unionSet(u: number, v: number): void { 32 u = find(u); // Find representative of u's set 33 v = find(v); // Find representative of v's set 34 35 if (u !== v) { // Only unite if they're in different sets 36 // Union by rank: attach smaller tree under root of larger tree 37 if (rank.get(u)! < rank.get(v)!) { 38 [u, v] = [v, u]; // Swap u and v 39 } 40 parent.set(v, u); // Make u the parent of v 41 42 // Update rank if both trees had same rank 43 if (rank.get(u) === rank.get(v)) { 44 rank.set(u, rank.get(u)! + 1); 45 } 46 } 47} 48 49// Count the number of connected components after grouping numbers by GCD > 1 50function countComponents(nums: number[], threshold: number): number { 51 // Clear and initialize DSU with elements from 0 to threshold 52 parent.clear(); 53 rank.clear(); 54 initializeDSU(threshold + 1); 55 56 // Group numbers that share common factors 57 // For each number, unite it with all its multiples up to threshold 58 for (const num of nums) { 59 // Connect num with all its multiples (num, 2*num, 3*num, ...) 60 for (let multiple = num; multiple <= threshold; multiple += num) { 61 unionSet(num, multiple); 62 } 63 } 64 65 // Count unique components by finding representative of each number 66 const uniqueComponents: Set<number> = new Set(); 67 for (const num of nums) { 68 if (num > threshold) { 69 // Numbers greater than threshold form their own component 70 uniqueComponents.add(num); 71 } else { 72 // Find the representative of the component containing num 73 uniqueComponents.add(find(num)); 74 } 75 } 76 77 // Return the total number of unique components 78 return uniqueComponents.size; 79} 80

Solution Approach

The solution uses Union-Find (Disjoint Set Union) data structure to efficiently group connected components.

Implementation Details:

DSU (Disjoint Set Union) Class Setup:
- Initialize parent and rank dictionaries for values from 0 to threshold
- Each value initially points to itself as parent
- Rank is used for union by rank optimization

Path Compression in Find Operation:

def find(self, x):  if self.parent[x] != x:  self.parent[x] = self.find(self.parent[x]) # Path compression  return self.parent[x]

Recursively finds the root parent
Compresses the path by making each node point directly to the root

Union by Rank:

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

Always attach the smaller tree under the root of the larger tree
This keeps the tree balanced and operations efficient

Main Algorithm:

for num in nums:  for j in range(num, threshold + 1, num):  dsu.union_set(num, j)

For each number in nums, iterate through its multiples: num, 2*num, 3*num, ... up to threshold
Union the number with each of its multiples
This creates connections between numbers that share common multiples

Counting Connected Components:

unique_parents = set() for num in nums:  if num > threshold:  unique_parents.add(num)  else:  unique_parents.add(dsu.find(num))

For numbers greater than threshold: They form isolated components (can't connect to anything)
For numbers within threshold: Find their root parent using DSU
Use a set to count unique root parents, which gives us the number of connected components

Time Complexity: O(n × (threshold/min_num) × α(threshold)) where α is the inverse Ackermann function (practically constant)

Space Complexity: O(threshold) for the DSU structure

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example with nums = [6, 12, 10] and threshold = 20.

Step 1: Initialize DSU Create a DSU structure with parent pointers for values 0 to 20. Each value initially points to itself.

Step 2: Process each number and its multiples

For num = 6:

Multiples within threshold: 6, 12, 18
Union(6, 6) - no change
Union(6, 12) - connects 6 and 12
Union(6, 18) - connects 6 and 18
After this: 6, 12, and 18 are in the same group (let's say root is 6)

For num = 12:

Multiples within threshold: 12
Union(12, 12) - no change (12 is already connected to 6's group)
After this: 12 remains in the group with root 6

For num = 10:

Multiples within threshold: 10, 20
Union(10, 10) - no change
Union(10, 20) - connects 10 and 20
After this: 10 and 20 form their own group (let's say root is 10)

Step 3: Count connected components

Find parent of 6: returns 6 (root of first group)
Find parent of 12: returns 6 (same group as 6)
Find parent of 10: returns 10 (root of second group)
Unique parents: {6, 10}
Result: 2 connected components

Verification:

lcm(6, 12) = 12 ≤ 20 ✓ (connected through multiple 12)
lcm(6, 10) = 30 > 20 ✗ (not connected)
lcm(12, 10) = 60 > 20 ✗ (not connected)

This confirms we have 2 connected components: {6, 12} and {10}.

Time and Space Complexity

Time Complexity: O(n * threshold * log(threshold)) where n is the length of the nums array.

The outer loop iterates through each number in nums: O(n)
For each number num, the inner loop iterates from num to threshold with step size num, which gives approximately threshold/num iterations
The total number of union operations across all numbers is bounded by O(threshold * log(threshold)) because the sum of threshold/1 + threshold/2 + ... + threshold/threshold equals threshold * H(threshold) where H(threshold) is the harmonic series, which is approximately O(log(threshold))
Each union operation involves two find operations, and with path compression, the amortized time complexity of find is nearly O(1), but worst case is O(log(threshold))
Therefore, the overall time complexity is O(n * threshold * log(threshold)) in the worst case

Space Complexity: O(threshold)

The DSU data structure maintains two dictionaries (parent and rank), each storing threshold + 1 elements: O(threshold)
The unique_parents set can store at most n elements (one for each number in nums): O(n)
Since typically n ≤ threshold in practical scenarios, the dominant space complexity is O(threshold)
The recursion stack for the find operation with path compression has a maximum depth of O(log(threshold)) in the worst case
Overall space complexity: O(threshold)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Connection Logic - Connecting Numbers Directly Instead of Through Multiples

The Pitfall: A common misunderstanding is trying to connect numbers directly by checking if their LCM is within the threshold:

# INCORRECT approach - directly checking LCM between pairs for i in range(len(nums)):  for j in range(i + 1, len(nums)):  if lcm(nums[i], nums[j]) <= threshold:  dsu.union_set(nums[i], nums[j])

Why This Fails:

The DSU structure is initialized for values 0 to threshold, not for the indices of nums
This would cause KeyError when nums[i] or nums[j] exceeds the DSU's initialized range
Even if you initialize DSU with all values in nums, you miss transitive connections through common multiples

The Correct Solution: Connect numbers through their common multiples within the threshold range:

# CORRECT approach - connecting through multiples for num in nums:  if num <= threshold:  for multiple in range(num * 2, threshold + 1, num):  dsu.union_set(num, multiple)

2. Starting Multiples from the Wrong Value

The Pitfall: Starting the multiple iteration from num itself instead of 2*num:

# INCORRECT - creates unnecessary self-loops for multiple in range(num, threshold + 1, num): # Starts at num  dsu.union_set(num, multiple)

Why This Matters:

union_set(num, num) is redundant since every element is already its own parent
While not causing incorrect results, it adds unnecessary operations

The Correct Solution: Start from 2*num since the first actual multiple is twice the number:

# CORRECT - starts from first actual multiple for multiple in range(num * 2, threshold + 1, num):  dsu.union_set(num, multiple)

3. Not Handling Numbers Greater Than Threshold

The Pitfall: Forgetting that numbers greater than threshold cannot have any valid LCM connections:

# INCORRECT - tries to find parent for numbers > threshold unique_components = set() for num in nums:  unique_components.add(dsu.find(num)) # Fails if num > threshold

Why This Fails:

Numbers greater than threshold aren't in the DSU structure
They can't connect to any other number (their LCM with anything would exceed threshold)
Calling dsu.find(num) when num > threshold causes KeyError

The Correct Solution: Treat numbers greater than threshold as isolated components:

# CORRECT - handles large numbers separately unique_components = set() for num in nums:  if num > threshold:  unique_components.add(num) # Each forms its own component  else:  unique_components.add(dsu.find(num))

4. Misunderstanding the Connection Criteria

The Pitfall: Thinking that numbers connect only if they directly divide each other or share a GCD:

# INCORRECT understanding - checking GCD instead of LCM for i in range(len(nums)):  for j in range(i + 1, len(nums)):  if gcd(nums[i], nums[j]) > 1: # Wrong criteria  # connect them

The Key Insight: Two numbers are connected if lcm(a, b) <= threshold. The solution cleverly uses the fact that if two numbers share a common multiple within the threshold, they can be connected through that multiple. For example:

Numbers 2 and 3 both divide 6
If 6 ≤ threshold, then 2 and 3 are in the same component
This is why we connect each number to all its multiples up to the threshold

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1

dp[i] = dp[i] + dp[i - 1]

dp[i] = (dp[i] + dp[j] + 1) for j in 0 to i

dp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don't know