Largest Component Size By Common Factor - Leetcode Solution

The problem "Largest Component Size By Common Factor" on Leetcode is a graph problem.

The problem statement is as follows: Given a non-empty array of unique positive integers A, consider the following graph:

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

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

Solution:

The problem can be solved using the Union-Find algorithm.

We start by iterating through the array A to build a hashmap where we store the factors of each number. For this, we can use the sieve of Eratosthenes algorithm to generate the prime numbers up to the maximum number in A. Then, for each number in A, we can factorize it using these prime numbers to get its factors.

After that, we initialize the Union-Find data structure with the size of A. Then we iterate through the array A again, and for each number in A, we find all the numbers that share a factor with it and unionize them in the Union-Find data structure.

Finally, we return the size of the largest connected component in the Union-Find data structure.

Here is the Python code for the solution:

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        
    def find(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]
    
    def union(self, i, j):
        pi, pj = self.find(i), self.find(j)
        if pi != pj:
            if self.size[pi] < self.size[pj]:
                pi, pj = pj, pi
            self.parent[pj] = pi
            self.size[pi] += self.size[pj]
            
class Solution:
    def largestComponentSize(self, A: List[int]) -> int:
        n = len(A)
        uf = UnionFind(n)
        
        max_num = max(A)
        primes = []        
        is_prime = [True] * (max_num + 1)        
        for i in range(2, max_num + 1):
            if is_prime[i]:
                primes.append(i)
                for j in range(i * i, max_num + 1, i):
                    is_prime[j] = False
        
        factor_map = {}
        for i in range(n):
            num_factors = set()
            num = A[i]
            for prime in primes:
                if prime > num:
                    break
                if num % prime == 0:
                    num_factors.add(prime)
                    while num % prime == 0:
                        num //= prime
            if num > 1:
                num_factors.add(num)
            factor_map[A[i]] = num_factors
        
        for i in range(n):
            for j in range(i + 1, n):
                if factor_map[A[i]] & factor_map[A[j]]:
                    uf.union(i, j)
        
        return max(uf.size)

Time Complexity:

• The time complexity of the sieve of Eratosthenes algorithm is O(n log log n).
• The time complexity of factorizing a number using prime numbers is O(sqrt(n)).
• The time complexity of the Union-Find algorithm is O(n alpha(n)), where alpha(n) is the inverse Ackermann function, which essentially means it's very close to constant time.
• Therefore, the overall time complexity of the solution is O(n sqrt(n) + n alpha(n)).

Space Complexity:

• The space complexity of the hashmap is O(n sqrt(n)).
• The space complexity of the Union-Find data structure is O(n).
• Therefore, the overall space complexity of the solution is O(n sqrt(n)).

1