You are given an integer array of unique positive integers nums. Consider the following graph:
nums.length nodes, labeled nums[0] to nums[nums.length - 1],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 * 1041 <= nums[i] <= 105nums are unique.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.
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:
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.
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.
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:
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.
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.
| 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 | — |
| 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 |
Largest Component Size by Common Factor | LeetCode 952 | C++, Java, Python • Knowledge Center • 7,047 views views
Watch 9 more video solutions →Practice Largest Component Size by Common Factor with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor