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

Largest Component Size by Common Factor

Difficulty: Hard

Problem Description

You are given an integer array of unique positive integers nums. Consider the following graph:

  • There are nums.length nodes, labeled nums[0] to nums[nums.length - 1],
  • There is an undirected edge between nums[i] and nums[j] if nums[i] and nums[j] share a common factor greater than 1.

Return the size of the largest connected component in the graph.

Key Insights

  • The problem can be visualized as a graph where each number is a node and edges are formed based on the common factors.
  • The largest connected component can be found using a union-find data structure to group nodes that are connected through common factors.
  • Each number can be represented by its prime factors, which can be used to connect nodes in the graph.
  • The problem requires efficient factorization and union operations to find the sizes of connected components.

Space and Time Complexity

Time Complexity: O(n log n) - where n is the number of elements in nums, primarily due to the factorization process. Space Complexity: O(n) - for storing the union-find structure and additional storage for factors.

Solution

To solve the problem, we can use the Union-Find (Disjoint Set Union) algorithm with path compression and union by rank. We will iterate through each number in nums, factor it to find its prime factors, and union the indices of the numbers that share the same prime factors. Finally, we will count the sizes of each component to find the largest one.

Code Solutions

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [1] * 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:
            if self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1

def largestComponentSize(nums):
    n = len(nums)
    uf = UnionFind(n)
    factor_map = {}
    
    for i, num in enumerate(nums):
        for factor in range(2, int(num**0.5) + 1):
            if num % factor == 0:
                if factor not in factor_map:
                    factor_map[factor] = i
                else:
                    uf.union(i, factor_map[factor])
                while num % factor == 0:
                    num //= factor
        if num > 1:
            if num not in factor_map:
                factor_map[num] = i
            else:
                uf.union(i, factor_map[num])
    
    component_size = {}
    max_size = 0
    for i in range(n):
        root = uf.find(i)
        if root not in component_size:
            component_size[root] = 0
        component_size[root] += 1
        max_size = max(max_size, component_size[root])
    
    return max_size
← Back to All Questions