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.The key idea in #952 Largest Component Size by Common Factor is to treat each number as a node in a graph and connect nodes that share a common factor greater than 1. Instead of comparing every pair of numbers, which would be too slow, an efficient strategy uses the Union-Find (Disjoint Set Union) data structure.
For each value in the array, compute its factors (typically via prime factorization). Map each factor to the indices or numbers that contain it, and union those numbers together in the DSU structure. This effectively groups numbers that share at least one factor into the same connected component.
After processing all numbers, count the size of each connected component and return the largest one. Optimizations like path compression and union by rank make DSU operations nearly constant time. The overall complexity mainly depends on factorization and union operations, making it efficient for large inputs.
| 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 |
Knowledge Center
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:
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.
1class UnionFind {
2 constructor(n) {
3 this.parent = Array.from({ length: n }
In JavaScript, this solution employs a union-find data structure to manage the connected components. Numbers are factorized and connected based on shared factors, and the maximum size of such connected components is found.
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:
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Prime factorization helps identify shared factors between numbers. If two numbers share any prime factor greater than 1, they belong to the same component, so their sets can be merged using Union-Find.
Yes, this type of problem appears in advanced coding interviews because it combines graph connectivity, number theory, and Union-Find. Companies often use it to test optimization skills and knowledge of DSU.
Union-Find (DSU) is the best data structure for this problem because it efficiently manages connected components. Combined with factorization and a hash map to track factors, it allows fast merging of related numbers.
The optimal approach uses the Union-Find (Disjoint Set Union) data structure. By factoring each number and unioning numbers that share common factors, we can efficiently build connected components without comparing every pair of numbers.
The JavaScript solution builds a graph using an adjacency list connecting numbers by their factors and performs BFS to determine connected component sizes. The largest component size is returned.