952. Largest Component Size by Common Factor

Largest Component Size by Common Factor (LeetCode 952) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Union-Find (Disjoint Set Union - DSU) subpattern.

How to solve Largest Component Size by Common Factor

Largest Component Size by Common Factor is a Union-Find problem, part of Graph Traversal Patterns (DFS & BFS). Master Union-Find data structure with path compression and union by rank for connectivity problems.

Work towards the solution in these steps:

1. Think of the problem as building a graph where each number is a node and edges exist based on shared factors, then finding the largest connected component.
2. Since explicitly checking all pairs for common factors is costly, consider using a Union-Find (Disjoint Set Union) data structure to efficiently group connected nodes.
3. Focus on connecting numbers through their prime factors rather than checking pairs; if two numbers share a prime factor, they belong to the same connected component.

The reference solution runs in O(n * sqrt(m) * alpha(n)) time and O(n + m) space.

The Largest Component Size by Common Factor solution and editorial walks through the full approach with reference code.

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 10^4

- 1 <= nums[i] <= 10^5

- All the values of nums are unique.

Topics and companies

Topics: Array, Hash Table, Math, Union Find, Number Theory.

Reported in interviews at Google.

How to practise Largest Component Size by Common Factor on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n * sqrt(m) * alpha(n)) time and O(n + m) space.

Open Largest Component Size by Common Factor in the code editor, or read the Largest Component Size by Common Factor editorial for a worked solution with its approach and complexity analysis.

Where Largest Component Size by Common Factor sits in the DSA pattern sheet

• Graph Traversal Patterns (DFS & BFS) pattern guide
• Union-Find (Disjoint Set Union - DSU) subpattern
• The full DSA patterns sheet

Problems related to Largest Component Size by Common Factor

Other problems that use the same Union-Find (Disjoint Set Union - DSU) and Graph Traversal Patterns (DFS & BFS) techniques:

• Accounts Merge — Medium, same subpattern
• Graph Valid Tree — Medium, same subpattern
• Greatest Common Divisor Traversal — Hard, same subpattern
• Most Stones Removed with Same Row or Column — Medium, same subpattern
• Number of Connected Components in an Undirected Graph — Medium, same subpattern
• Number of Islands II — Hard, same subpattern

Largest Component Size by Common Factor FAQ