952. Largest Component Size by Common Factor Solution

The problem

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 overview

Problem Overview: You receive an integer array where each value represents a node. Two numbers belong to the same component if they share a common factor greater than 1. The goal is to group numbers using shared factors and return the size of the largest connected component.

Approach 1: Graph Traversal with Factor Mapping (BFS/DFS) (Time: O(n * sqrt(max(A))), Space: O(n + factors))

Treat each number as a node in a graph. If two numbers share a factor greater than 1, connect them with an edge. Instead of comparing every pair (which would be O(n²)), factorize each number and build a map from factor -> list of numbers. Numbers sharing the same factor become neighbors. Run BFS or DFS from every unvisited node to explore its connected component and track the largest size. The expensive step is factorization up to sqrt(num) for every value, which leads to roughly O(n * sqrt(max(A))) time. This approach directly models the graph but can consume more memory due to adjacency storage. It uses concepts from graph traversal and hash tables to manage factor mappings.

Approach 2: Union-Find with Prime Factorization (Time: O(n log M), Space: O(n))

This approach avoids explicitly building the graph. Instead, treat each number as a node in a Disjoint Set Union structure. Factorize every number into its prime factors. For each factor, union the current number with the first number that previously used that factor. A hash map stores factor -> index, allowing fast unions whenever the same factor appears again. The key insight is that shared factors imply connectivity, so union operations gradually merge related numbers into components. Path compression and union-by-rank keep operations nearly constant time, giving an overall complexity around O(n log M) where M is the maximum value. This solution combines Union Find with number theory factorization techniques and scales well for large arrays.

Recommended for interviews: Union-Find with prime factorization is the expected solution. It demonstrates knowledge of disjoint set structures and efficient connectivity modeling. Graph traversal shows the conceptual model, but the union-find approach avoids building large adjacency lists and performs better when the input size grows.

Approach 1: 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.

Python

from collections import defaultdict
import math

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

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

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.size[rootX] < self.size[rootY]:
                self.parent[rootX] = rootY
                self.size[rootY] += self.size[rootX]
            else:
                self.parent[rootY] = rootX
                self.size[rootX] += self.size[rootY]

    def getSize(self, x):
        return self.size[self.find(x)]

def largestComponentSize(nums):
    maxNum = max(nums)
    uf = UnionFind(maxNum + 1)

    for num in nums:
        for factor in range(2, int(math.sqrt(num)) + 1):
            if num % factor == 0:
                uf.union(num, factor)
                uf.union(num, num // factor)

    count = defaultdict(int)
    for num in nums:
        root = uf.find(num)
        count[root] += 1

    return max(count.values())

# Example usage:
nums = [4, 6, 15, 35]
print(largestComponentSize(nums))  # Output: 4

Java

import java.util.*;

class UnionFind {
    private int[] parent;
    private int[] size;

    public UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (size[rootX] < size[rootY]) {
                parent[rootX] = rootY;
                size[rootY] += size[rootX];
            } else {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];
            }
        }
    }

    public int getSize(int x) {
        return size[find(x)];
    }
}

public class Solution {
    public int largestComponentSize(int[] nums) {
        int maxNum = Arrays.stream(nums).max().getAsInt();
        UnionFind uf = new UnionFind(maxNum + 1);

        for (int num : nums) {
            for (int factor = 2; factor <= Math.sqrt(num); factor++) {
                if (num % factor == 0) {
                    uf.union(num, factor);
                    uf.union(num, num / factor);
                }
            }
        }

        Map<Integer, Integer> count = new HashMap<>();
        int result = 0;
        for (int num : nums) {
            int root = uf.find(num);
            count.put(root, count.getOrDefault(root, 0) + 1);
            result = Math.max(result, count.get(root));
        }
        return result;
    }

    // Example usage:
    public static void main(String[] args) {
        int[] nums = {4, 6, 15, 35};
        Solution solution = new Solution();
        System.out.println(solution.largestComponentSize(nums));  // Output: 4
    }
}

C++

#include <vector>
#include <unordered_map>
#include <cmath>
#include <algorithm>

class UnionFind {
public:
    UnionFind(int n) : parent(n), size(n, 1) {
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void unionNodes(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (size[rootX] < size[rootY]) {
                parent[rootX] = rootY;
                size[rootY] += size[rootX];
            } else {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];
            }
        }
    }

    int getSize(int x) {
        return size[find(x)];
    }

private:
    std::vector<int> parent;
    std::vector<int> size;
};

int largestComponentSize(std::vector<int>& nums) {
    int maxNum = *max_element(nums.begin(), nums.end());
    UnionFind uf(maxNum + 1);

    for (int num : nums) {
        for (int factor = 2; factor <= sqrt(num); ++factor) {
            if (num % factor == 0) {
                uf.unionNodes(num, factor);
                uf.unionNodes(num, num / factor);
            }
        }
    }

    std::unordered_map<int, int> count;
    int answer = 0;
    for (int num : nums) {
        int root = uf.find(num);
        count[root]++;
        answer = std::max(answer, count[root]);
    }

    return answer;
}

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

JavaScript

class UnionFind {
    constructor(n) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.size = Array(n).fill(1);
    }

    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }

    union(x, y) {
        let rootX = this.find(x);
        let rootY = this.find(y);
        if (rootX !== rootY) {
            if (this.size[rootX] < this.size[rootY]) {
                this.parent[rootX] = rootY;
                this.size[rootY] += this.size[rootX];
            } else {
                this.parent[rootY] = rootX;
                this.size[rootX] += this.size[rootY];
            }
        }
    }

    getSize(x) {
        return this.size[this.find(x)];
    }
}

function largestComponentSize(nums) {
    const maxNum = Math.max(...nums);
    const uf = new UnionFind(maxNum + 1);

    for (let num of nums) {
        for (let factor = 2; factor <= Math.sqrt(num); factor++) {
            if (num % factor === 0) {
                uf.union(num, factor);
                uf.union(num, num / factor);
            }
        }
    }

    const count = new Map();
    let result = 0;
    for (let num of nums) {
        let root = uf.find(num);
        count.set(root, (count.get(root) || 0) + 1);
        result = Math.max(result, count.get(root));
    }
    return result;
}

// Example usage:
let nums = [4, 6, 15, 35];
console.log(largestComponentSize(nums));  // Output: 4

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

typedef struct {
    int* parent;
    int* size;
} UnionFind;

UnionFind* createUnionFind(int n) {
    UnionFind* uf = (UnionFind*) malloc(sizeof(UnionFind));
    uf->parent = (int*) malloc(n * sizeof(int));
    uf->size = (int*) malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        uf->parent[i] = i;
        uf->size[i] = 1;
    }
    return uf;
}

int find(UnionFind* uf, int x) {
    if (uf->parent[x] != x) {
        uf->parent[x] = find(uf, uf->parent[x]);
    }
    return uf->parent[x];
}

void unionNodes(UnionFind* uf, int x, int y) {
    int rootX = find(uf, x);
    int rootY = find(uf, y);
    if (rootX != rootY) {
        if (uf->size[rootX] < uf->size[rootY]) {
            uf->parent[rootX] = rootY;
            uf->size[rootY] += uf->size[rootX];
        } else {
            uf->parent[rootY] = rootX;
            uf->size[rootX] += uf->size[rootY];
        }
    }
}

void freeUnionFind(UnionFind* uf) {
    free(uf->parent);
    free(uf->size);
    free(uf);
}

int largestComponentSize(int* nums, int numsSize) {
    int maxNum = 0;
    for (int i = 0; i < numsSize; ++i) {
        if (nums[i] > maxNum) maxNum = nums[i];
    }

    UnionFind* uf = createUnionFind(maxNum + 1);

    for (int i = 0; i < numsSize; i++) {
        int num = nums[i];
        for (int factor = 2; factor <= sqrt(num); ++factor) {
            if (num % factor == 0) {
                unionNodes(uf, num, factor);
                unionNodes(uf, num, num / factor);
            }
        }
    }

    int* count = (int*)calloc(maxNum + 1, sizeof(int));
    int answer = 0;

    for (int i = 0; i < numsSize; ++i) {
        int root = find(uf, nums[i]);
        count[root]++;
        if (count[root] > answer) answer = count[root];
    }

    free(count);
    freeUnionFind(uf);
    return answer;
}

// Example usage
// int main() {
//     int nums[] = {4, 6, 15, 35};
//     int size = sizeof(nums) / sizeof(nums[0]);
//     printf("%d\n", largestComponentSize(nums, size)); // Output: 4
//     return 0;
// }

using System;
using System.Collections.Generic;

public class UnionFind {
    private int[] parent;
    private int[] size;

    public UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public int Find(int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent[x]);
        }
        return parent[x];
    }

    public void Union(int x, int y) {
        int rootX = Find(x);
        int rootY = Find(y);
        if (rootX != rootY) {
            if (size[rootX] < size[rootY]) {
                parent[rootX] = rootY;
                size[rootY] += size[rootX];
            } else {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];
            }
        }
    }

    public int GetSize(int x) {
        return size[Find(x)];
    }
}

public class Solution {
    public int LargestComponentSize(int[] nums) {
        int maxNum = 0;
        foreach (int num in nums) {
            if (num > maxNum) maxNum = num;
        }

        UnionFind uf = new UnionFind(maxNum + 1);

        foreach (int num in nums) {
            for (int factor = 2; factor <= Math.Sqrt(num); factor++) {
                if (num % factor == 0) {
                    uf.Union(num, factor);
                    uf.Union(num, num / factor);
                }
            }
        }

        Dictionary<int, int> count = new Dictionary<int, int>();
        int result = 0;

        foreach (int num in nums) {
            int root = uf.Find(num);
            if (!count.ContainsKey(root)) count[root] = 0;
            count[root]++;
            if (count[root] > result) result = count[root];
        }

        return result;
    }

    // Example usage:
    public static void Main() {
        int[] nums = {4, 6, 15, 35};
        Solution solution = new Solution();
        Console.WriteLine(solution.LargestComponentSize(nums)); // Output: 4
    }
}

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.

Complexity

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.

Try this approach in the editor

Approach 2: 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.

Python

from collections import defaultdict, deque
import math

def largestComponentSize(nums):
    def find_factors(n):
        factors = set()
        for i in range(2, int(math.sqrt(n)) + 1):
            if n % i == 0:
                while n % i == 0:
                    n //= i
                factors.add(i)
        if n > 1:
            factors.add(n)
        return factors

    factor_map = defaultdict(list)
    for num in nums:
        factors = find_factors(num)
        for factor in factors:
            factor_map[factor].append(num)

    visited = set()
    def bfs(start):
        queue = deque([start])
        size = 0
        while queue:
            node = queue.popleft()
            if node not in visited:
                visited.add(node)
                size += 1
                for factor in find_factors(node):
                    for neighbor in factor_map[factor]:
                        if neighbor not in visited:
                            queue.append(neighbor)
        return size

    max_size = 0
    for num in nums:
        if num not in visited:
            size = bfs(num)
            max_size = max(max_size, size)
    return max_size

# Example usage:
nums = [4, 6, 15, 35]
print(largestComponentSize(nums))  # Output: 4

Java

import java.util.*;

public class Solution {
    private List<Integer> findFactors(int n) {
        List<Integer> factors = new ArrayList<>();
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                factors.add(i);
                while (n % i == 0) n /= i;
            }
        }
        if (n > 1) factors.add(n);
        return factors;
    }

    public int largestComponentSize(int[] nums) {
        Map<Integer, List<Integer>> factorMap = new HashMap<>();
        for (int num : nums) {
            List<Integer> factors = findFactors(num);
            for (int factor : factors) {
                factorMap.computeIfAbsent(factor, k -> new ArrayList<>()).add(num);
            }
        }

        Set<Integer> visited = new HashSet<>();
        int maxSize = 0;

        for (int num : nums) {
            if (!visited.contains(num)) {
                int size = bfs(num, factorMap, visited);
                maxSize = Math.max(maxSize, size);
            }
        }

        return maxSize;
    }

    private int bfs(int start, Map<Integer, List<Integer>> factorMap, Set<Integer> visited) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        int size = 0;

        while (!queue.isEmpty()) {
            int node = queue.poll();
            if (visited.add(node)) {
                size++;
                List<Integer> factors = findFactors(node);
                for (int factor : factors) {
                    for (int neighbor : factorMap.getOrDefault(factor, Collections.emptyList())) {
                        if (!visited.contains(neighbor)) {
                            queue.offer(neighbor);
                        }
                    }
                }
            }
        }

        return size;
    }

    // Example usage:
    public static void main(String[] args) {
        int[] nums = {4, 6, 15, 35};
        Solution solution = new Solution();
        System.out.println(solution.largestComponentSize(nums)); // Output: 4
    }
}

C++

#include <iostream>
#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;
// }

JavaScript

function largestComponentSize(nums) {
    function findFactors(num) {
        const factors = new Set();
        for (let i = 2; i <= Math.sqrt(num); i++) {
            if (num % i === 0) {
                factors.add(i);
                while (num % i === 0) num /= i;
            }
        }
        if (num > 1) factors.add(num);
        return factors;
    }

    const factorMap = {};
    for (const num of nums) {
        for (const factor of findFactors(num)) {
            if (!factorMap[factor]) {
                factorMap[factor] = [];
            }
            factorMap[factor].push(num);
        }
    }

    const visited = new Set();
    function bfs(start) {
        const queue = [start];
        let size = 0;

        while (queue.length > 0) {
            const node = queue.shift();
            if (!visited.has(node)) {
                visited.add(node);
                size++;
                for (const factor of findFactors(node)) {
                    for (const neighbor of (factorMap[factor] || [])) {
                        if (!visited.has(neighbor)) {
                            queue.push(neighbor);
                        }
                    }
                }
            }
        }

        return size;
    }

    let maxSize = 0;
    for (const num of nums) {
        if (!visited.has(num)) {
            const size = bfs(num);
            maxSize = Math.max(maxSize, size);
        }
    }

    return maxSize;
}

// Example usage:
let nums = [4, 6, 15, 35];
console.log(largestComponentSize(nums));  // Output: 4

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int* data;
    int size;
    int capacity;
} Vector;

Vector* createVector(int capacity) {
    Vector* vec = (Vector*) malloc(sizeof(Vector));
    vec->data = (int*) malloc(sizeof(int) * capacity);
    vec->size = 0;
    vec->capacity = capacity;
    return vec;
}

void push_back(Vector* vec, int value) {
    if (vec->size == vec->capacity) {
        vec->capacity *= 2;
        vec->data = (int*) realloc(vec->data, sizeof(int) * vec->capacity);
    }
    vec->data[vec->size++] = value;
}

void freeVector(Vector* vec) {
    free(vec->data);
    free(vec);
}

int* findFactors(int n, int* returnSize) {
    Vector* factors = createVector(10);
    for (int i = 2; i <= sqrt(n); ++i) {
        if (n % i == 0) {
            push_back(factors, i);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) push_back(factors, n);
    *returnSize = factors->size;
    int* result = (int*) malloc(sizeof(int) * factors->size);
    memcpy(result, factors->data, factors->size * sizeof(int));
    freeVector(factors);
    return result;
}

int largestComponentSize(int* nums, int numsSize) {
    int maxFactorMap[100001] = {0};
    for (int i = 0; i < numsSize; ++i) {
        int returnSize;
        int* factors = findFactors(nums[i], &returnSize);
        for (int j = 0; j < returnSize; ++j) {
            int factor = factors[j];
            if (maxFactorMap[factor] == 0) maxFactorMap[factor] = nums[i];
        }
        free(factors);
    }

    int visited[100001] = {0};
    int maxSize = 0;

    for (int i = 0; i < numsSize; ++i) {
        if (!visited[nums[i]]) {
            Vector* queue = createVector(10);
            push_back(queue, nums[i]);
            int size = 0;

            while (queue->size > 0) {
                int node = queue->data[--queue->size];
                if (!visited[node]) {
                    visited[node] = 1;
                    size++;
                    int returnSize;
                    int* factors = findFactors(node, &returnSize);
                    for (int j = 0; j < returnSize; ++j) {
                        int factor = factors[j];
                        if (maxFactorMap[factor] && !visited[maxFactorMap[factor]]) {
                            push_back(queue, maxFactorMap[factor]);
                        }
                    }
                    free(factors);
                }
            }
            freeVector(queue);
            if (size > maxSize) maxSize = size;
        }
    }

    return maxSize;
}

// Example usage:
// int main() {
//     int nums[] = {4, 6, 15, 35};
//     int numsSize = sizeof(nums) / sizeof(int);
//     printf("%d\n", largestComponentSize(nums, numsSize)); // Output: 4
//     return 0;
// }

using System;
using System.Collections.Generic;

public class Solution {
    private List<int> findFactors(int n) {
        var factors = new List<int>();
        for (int i = 2; i <= Math.Sqrt(n); i++) {
            if (n % i == 0) {
                factors.Add(i);
                while (n % i == 0) n /= i;
            }
        }
        if (n > 1) factors.Add(n);
        return factors;
    }

    public int LargestComponentSize(int[] nums) {
        var factorMap = new Dictionary<int, List<int>>();
        foreach (int num in nums) {
            var factors = findFactors(num);
            foreach (int factor in factors) {
                if (!factorMap.ContainsKey(factor)) {
                    factorMap[factor] = new List<int>();
                }
                factorMap[factor].Add(num);
            }
        }

        var visited = new HashSet<int>();
        int maxSize = 0;

        foreach (int num in nums) {
            if (!visited.Contains(num)) {
                int size = bfs(num, factorMap, visited);
                maxSize = Math.Max(maxSize, size);
            }
        }
        return maxSize;
    }

    private int bfs(int start, Dictionary<int, List<int>> factorMap, HashSet<int> visited) {
        var queue = new Queue<int>();
        queue.Enqueue(start);
        int size = 0;

        while (queue.Count > 0) {
            int node = queue.Dequeue();
            if (visited.Add(node)) {
                size++;
                var factors = findFactors(node);
                foreach (var factor in factors) {
                    foreach (var neighbor in factorMap.GetValueOrDefault(factor, new List<int>())) {
                        if (!visited.Contains(neighbor)) {
                            queue.Enqueue(neighbor);
                        }
                    }
                }
            }
        }

        return size;
    }

    // Example usage:
    public static void Main() {
        int[] nums = {4, 6, 15, 35};
        Solution solution = new Solution();
        Console.WriteLine(solution.LargestComponentSize(nums)); // Output: 4
    }
}

The Python solution constructs an adjacency list using numbers and their factors. A BFS is used to find and measure components in the graph, and the maximum size of these components is returned as the answer.

Complexity

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.

Try this approach in the editor

Approach 3: Default Approach

func largestComponentSize(nums []int) int {
	m := slices.Max(nums)
	p := make([]int, m+1)
	for i := range p {
		p[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	union := func(a, b int) {
		pa, pb := find(a), find(b)
		if pa != pb {
			p[pa] = pb
		}
	}
	for _, v := range nums {
		i := 2
		for i <= v/i {
			if v%i == 0 {
				union(v, i)
				union(v, v/i)
			}
			i++
		}
	}
	cnt := make([]int, m+1)
	for _, v := range nums {
		t := find(v)
		cnt[t]++
	}
	return slices.Max(cnt)
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Union-Find with Prime Factorization	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.
Graph-based BFS/DFS Approach	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.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Graph BFS/DFS with Factor Mapping	O(n * sqrt(max(A)))	O(n + factors)	Useful when modeling the connectivity graph explicitly for clarity or learning graph traversal
Union-Find with Prime Factorization	O(n log M)	O(n)	Best general solution for large inputs; avoids building full graph and scales efficiently

Frequently asked questions

Is Largest Component Size by Common Factor easy or hard?

Largest Component Size by Common Factor is categorized as a Hard problem. The challenge comes from recognizing that shared factors imply graph connectivity and then implementing an efficient Union-Find solution combined with number factorization.

Largest Component Size by Common Factor Python/Java solution

Most implementations use Union-Find plus prime factorization. The logic is language-independent: factorize each number, map factors to indices, union indices sharing factors, and count component sizes. Python, Java, C++, and JavaScript solutions follow the same structure with minor syntax differences.

How to solve Largest Component Size by Common Factor in O(n)?

Strict O(n) is difficult because each number must be factorized. The closest practical complexity is about O(n log M) using Union-Find with prime factorization. Each factor connects numbers through union operations, forming components without building a full graph.

What is the best approach for Largest Component Size by Common Factor?

Union-Find with prime factorization is the most efficient and commonly expected approach. Each number is factorized and union operations connect numbers sharing the same prime factor. With path compression and union-by-rank, the algorithm runs around O(n log M) time and O(n) space.

Is Largest Component Size by Common Factor asked at Google/Amazon/Meta?

This problem frequently appears in interviews at large tech companies because it combines number theory and disjoint set data structures. Variations of factor-based connectivity problems have been reported in interviews at Google, Amazon, and Meta.

What data structure is used in Largest Component Size by Common Factor?

The primary data structure is Disjoint Set Union (Union-Find) to maintain connected components. Hash maps are also used to track which numbers share prime factors, enabling quick union operations between related nodes.

What is the time complexity of Largest Component Size by Common Factor?

The optimal Union-Find solution runs in about O(n log M) time, where n is the number of elements and M is the maximum value in the array. Factorization contributes the log or sqrt component, while union and find operations are nearly constant due to path compression.

Largest Component Size by Common Factor solution and explanation

The problem

Approach overview

Approach 1: Union-Find with Prime Factorization

Approach 2: Graph-based BFS/DFS Approach

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Largest Component Size by Common Factor solution and explanation

The problem

Approach overview

Approach 1: Union-Find with Prime Factorization

Approach 2: Graph-based BFS/DFS Approach

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems