Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

3680. Count Connected Components in LCM Graph

My accepted Python solution to LeetCode problem 3680, Count Connected Components in LCM Graph, running in 9120ms.

  • Difficulty: Hard
  • Python
  • Runtime 9120ms
  • Memory 47.4MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 9120ms, memory 47.4MB, accepted 2025-12-31.

python
class Solution:
    def countComponents(self, nums: List[int], threshold: int) -> int:
        # Union-Find
        n = len(nums)
        parent = list(range(n))
        rank = [0] * n
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def union(x, y):
            px, py = find(x), find(y)
            if px == py:
                return
            if rank[px] < rank[py]:
                px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]:
                rank[px] += 1
        
        # Filter nums that are <= threshold
        # For each multiple m <= threshold, group all nums that divide m
        
        # Map value to index for nums <= threshold
        val_to_idx = {}
        for i, v in enumerate(nums):
            if v <= threshold:
                val_to_idx[v] = i
        
        # For each m from 1 to threshold
        # Find all nums that divide m and union them
        for m in range(1, threshold + 1):
            divisors = []
            for d in range(1, int(m**0.5) + 1):
                if m % d == 0:
                    if d in val_to_idx:
                        divisors.append(val_to_idx[d])
                    if m // d != d and m // d in val_to_idx:
                        divisors.append(val_to_idx[m // d])
            # Union all divisors
            for i in range(1, len(divisors)):
                union(divisors[0], divisors[i])
        
        # Count components
        # Nums > threshold form their own component
        components = set()
        for i in range(n):
            if nums[i] > threshold:
                components.add(i)  # Each forms its own component
            else:
                components.add(find(i))
        
        return len(components)

Source