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.

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:

1. We union each number with all its multiples up to the threshold
2. Numbers that share common multiples will end up in the same connected component
3. 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 Approach

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

Implementation Details:

1. 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

2. 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

3. 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

4. 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

5. 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

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}.

Solution Implementation

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