Watch 10 video solutions for Largest Component Size by Common Factor, a hard level problem involving Array, Hash Table, Math. This walkthrough by Knowledge Center has 7,047 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |