We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Connected Components in LCM Graph

Difficulty: Hard

Problem Description

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.

Key Insights

  • The connected components are determined by the least common multiple (LCM) of the values in the nums array.
  • If the LCM of two numbers is less than or equal to the threshold, they belong to the same connected component.
  • The problem can be solved using graph traversal techniques like Depth-First Search (DFS) or Union-Find to find connected components efficiently.
  • Given the constraints, an efficient algorithm is necessary to handle the upper limits in terms of time and space complexity.

Space and Time Complexity

Time Complexity: O(n^2) in the worst case, but can be improved with Union-Find optimizations.
Space Complexity: O(n) for storing the graph representation and connected components.

Solution

To solve the problem, we will use the Union-Find data structure to keep track of connected components. We will iterate through the nums array and check the LCM of every pair of nodes. If their LCM is less than or equal to the threshold, we will union these nodes. Finally, we count the number of unique parent nodes to get the number of connected components.

Code Solutions

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]
    
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            self.parent[rootY] = rootX  # Union operation

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * (b // gcd(a, b))

def countComponents(nums, threshold):
    n = len(nums)
    uf = UnionFind(n)
    
    for i in range(n):
        for j in range(i + 1, n):
            if lcm(nums[i], nums[j]) <= threshold:
                uf.union(i, j)
    
    # Count unique roots
    unique_roots = set()
    for i in range(n):
        unique_roots.add(uf.find(i))
    
    return len(unique_roots)
← Back to All Questions