Skip to main content
Talentd

Largest Component Size by Common Factor - Solution & Explanation

HardArrayHash TableMathUnion Find21 min readAsked at: Microsoft, Google
Practice this problem

Problem Statement

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 * 104
  • 1 <= nums[i] <= 105
  • 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.

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.

Code

PythonC++JavaJavaScriptCC#

Python

C++

Java

JavaScript

C

C#

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.

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.

Code

PythonC++JavaJavaScriptCC#

Python

C++

Java

JavaScript

C

C#

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

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
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ā€”

Detailed Complexity Analysis

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

Video Solution

Largest Component Size by Common Factor | LeetCode 952 | C++, Java, Python ā€¢ Knowledge Center ā€¢ 7,176 views views

Watch 9 more video solutions ā†’

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.

Ready to solve this problem?

Practice Largest Component Size by Common Factor with our built-in code editor and test cases.

Practice on FleetCode
Previous

Distinct Prime Factors of Product of Array

Next

Groups of Strings