#952 Largest Component Size by Common Factor

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.

Example 1:

Input: nums = [4,6,15,35]
Output: 4

Example 2:

Input: nums = [20,50,9,63]
Output: 2

Example 3:

Input: nums = [2,3,6,7,4,12,21,39]
Output: 8

Constraints:

1 <= nums.length <= 2 * 10⁴
1 <= nums[i] <= 10⁵
All the values of nums are unique.

Approach	Time Complexity	Space Complexity
Union-Find with Factor Mapping	O(n log M) to O(n √M) depending on factorization method	O(n + M) for DSU and factor tracking

Solutions (12)

Union-Find with Prime Factorization

This approach leverages the union-find data structure to connect numbers that share common prime factors. Each number is represented as a node, and we create edges between numbers that have a common prime factor. The largest connected component is determined by finding the maximum size of the connected components formed.

The steps are:

Initialize a union-find structure for all numbers.
For each number, find its prime factors.
For each pair of numbers and a common prime factor, union their roots.
Count the size of the connected component for each root to find the largest.

Time Complexity: O(N * sqrt(M)), where N is the number of elements in nums and M is the maximum element value, due to factorization. Space Complexity: O(N + M) for the union-find structure and auxiliary space.

Python C++Java JavaScript C C#

1from collections import defaultdict
2import math
3
4class UnionFind:
5    def __init__(self, n):
6

Explanation

The solution uses a union-find data structure to represent connected components. Each number in the array has its factorization computed, and numbers sharing a factor are connected. By the end, the size of the largest component is computed by counting the results of the find operation on the union-find structure.

Graph-based BFS/DFS Approach

This graph-based approach builds an adjacency list to represent the graph, then uses BFS or DFS to explore connected components. Each connection is identified by the shared factors between the nodes. The largest connected component's size indicates the solution.

The steps are:

Factorize each number and use this to build an adjacency list.
Use BFS or DFS to traverse the graph and count the nodes in each component.
Keep track of the maximum size encountered during traversal.

Time Complexity: O(N * sqrt(M)), where N is the number of elements in nums and M is each element's largest value. Space Complexity: O(N + M) for storing adjacency lists and visited sets.

Python C++Java JavaScript C C#

#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <math.h>

std::vector<int> find_factors(int n) {
    std::vector<int> factors;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            factors.push_back(i);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) factors.push_back(n);
    return factors;
}

int largestComponentSize(std::vector<int>& nums) {
    std::unordered_map<int, std::vector<int>> factor_map;
    for (int num : nums) {
        std::vector<int> factors = find_factors(num);
        for (int factor : factors) {
            factor_map[factor].push_back(num);
        }
    }

    std::unordered_set<int> visited;
    std::function<int(int)> bfs = [&](int start) {
        std::queue<int> queue;
        queue.push(start);
        int size = 0;
        while (!queue.empty()) {
            int node = queue.front();
            queue.pop();
            if (!visited.count(node)) {
                visited.insert(node);
                size++;
                std::vector<int> factors = find_factors(node);
                for (int factor : factors) {
                    for (int neighbor : factor_map[factor]) {
                        if (!visited.count(neighbor)) queue.push(neighbor);
                    }
                }
            }
        }
        return size;
    };

    int max_size = 0;
    for (int num : nums) {
        if (!visited.count(num)) {
            int size = bfs(num);
            max_size = std::max(max_size, size);
        }
    }
    return max_size;
}

// Example usage:
// int main() {
//     std::vector<int> nums = {4, 6, 15, 35};
//     std::cout << largestComponentSize(nums) << std::endl; // Output: 4
//     return 0;
// }