LeetCode Solutions Blog

Largest Component Size by Common Factor

Number: 989

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an array of unique positive integers, treat each number as a node in a graph. Two nodes share an undirected edge if the corresponding numbers share a common factor greater than 1. The task is to determine the size of the largest connected component in this graph.

Key Insights

Recognize that common factors (other than 1) can connect numbers.
Instead of building an explicit graph, use factorization to connect numbers sharing any factor.
Use the Union-Find (Disjoint Set Union) data structure to dynamically merge nodes that share common factors.
For each number, factorize it and union together all numbers that have the same factor.
The largest connected component size is equivalent to the largest set in the Union-Find data structure.

Space and Time Complexity

Time Complexity: O(n * sqrt(m) * α(n)) where n is the number of elements, m is the maximum value in nums (due to factorization up to sqrt(m)), and α(n) is the inverse Ackerman function from union-find operations which is almost constant. Space Complexity: O(n + m) for storing the union-find data structure and factor mapping.

Solution

The solution uses the Union-Find algorithm with path compression to connect nodes that share common factors greater than 1. For each number in the array, we perform the following:

Factorize the number by checking divisibility up to its square root.
For each factor found (and its complementary factor), use a mapping to union the current number with previously seen numbers that share the same factor.
Finally, count the size of each component by iterating through the union-find parent references to find the largest connected component.

This approach avoids the overhead of constructing an explicit graph by directly linking numbers based on shared factors.

Code Solutions

# Python Solution
class UnionFind:
    def __init__(self, size):
        # Initially, each element is its own parent.
        self.parent = list(range(size))
        self.rank = [0] * size
        self.count = [1] * size  # count[i] holds the size of the set whose root is i.

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

    def union(self, x, y):
        # Find roots of the components.
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return
        # Union by rank optimization.
        if self.rank[rootX] < self.rank[rootY]:
            self.parent[rootX] = rootY
            self.count[rootY] += self.count[rootX]
        elif self.rank[rootX] > self.rank[rootY]:
            self.parent[rootY] = rootX
            self.count[rootX] += self.count[rootY]
        else:
            self.parent[rootY] = rootX
            self.rank[rootX] += 1
            self.count[rootX] += self.count[rootY]

class Solution:
    def largestComponentSize(self, nums):
        n = len(nums)
        uf = UnionFind(n)
        # Map to track factor -> index (first occurrence)
        factor_to_index = {}
        
        for i, num in enumerate(nums):
            # Factorize the number.
            factor = 2
            # Iterate through possible factors
            while factor * factor <= num:
                if num % factor == 0:
                    # Check factor and its counterpart
                    for f in [factor, num // factor]:
                        if f > 1:
                            if f in factor_to_index:
                                uf.union(i, factor_to_index[f])
                            else:
                                factor_to_index[f] = i
                factor += 1
            # For a prime number greater than sqrt(num) that hasn't been handled.
            if num > 1:
                if num in factor_to_index:
                    uf.union(i, factor_to_index[num])
                else:
                    factor_to_index[num] = i
        
        return max(uf.count)

# Example usage:
# sol = Solution()
# print(sol.largestComponentSize([4,6,15,35]))