How to Solve Largest Component Size by Common Factor

This problem requires identifying the largest connected component among numbers linked by shared factors. By combining array scanning with a hash map for union-find tracking, you can efficiently group numbers by their prime factors. The solution avoids redundant factor checks and leverages the unique integer constraints to maintain optimal performance while ensuring correctness across all input sizes.

Problem Statement

You are given an array of unique positive integers nums. Construct an undirected graph where each integer is a node, and there is an edge between two numbers if they share a common factor greater than one. The task is to find the size of the largest connected component in this graph.

For example, given nums = [4,6,15,35], nodes 4 and 6 are connected through factor 2, 6 and 15 share factor 3, and 15 and 35 share factor 5. The largest connected component includes all four numbers, so the output is 4. You must return this largest component size for any valid input array.

Examples

Example 1

Input: nums = [4,6,15,35]

Output: 4

Example details omitted.

Example 2

Input: nums = [20,50,9,63]

Output: 2

Example details omitted.

Example 3

Input: nums = [2,3,6,7,4,12,21,39]

Output: 8

Example details omitted.

Constraints

• 1 <= nums.length <= 2 * 104
• 1 <= nums[i] <= 105
• All the values of nums are unique.

Solution Approach

Prime Factorization with Union-Find

For each number in the array, find its prime factors and map them to the number using a hash map. Use union-find to merge sets of numbers sharing the same factor. This ensures numbers with a common factor are grouped efficiently, avoiding direct pairwise comparisons which are too slow for large arrays.

Path Compression Optimization

While performing union operations, apply path compression to flatten the union-find tree structure. This reduces the time complexity for subsequent find operations, making repeated merges and queries faster, especially in dense factor sharing scenarios.

Count Component Sizes

After all union operations, iterate over each number and determine its root in the union-find structure. Maintain a count of numbers per root, and return the maximum count. This directly yields the size of the largest connected component while leveraging the factor-based grouping.

Complexity Analysis

Time complexity depends on factorization and union-find operations, roughly O(N sqrt(M)) where N is array length and M is max value. Space complexity is O(N + M) for parent and factor maps. Optimizations like path compression help maintain near-linear performance.

What Interviewers Usually Probe

• Candidate attempts naive pairwise GCD checks, which is inefficient for large inputs.
• Candidate successfully maps numbers to prime factors, indicating understanding of factor-based graph structure.
• Candidate applies union-find with path compression or other optimizations to manage large component merging efficiently.

Common Pitfalls or Variants

Common pitfalls

• Trying to compare every pair with GCD, causing TLE on large arrays.
• Forgetting to merge all numbers sharing a factor, leading to undercounting component sizes.
• Neglecting path compression, resulting in slower union-find operations and exceeding time limits.

Follow-up variants

• Compute largest component size considering only prime numbers in the array.
• Find the number of connected components rather than the largest size using the same factor-based graph.
• Determine largest component size when edges exist for numbers sharing any divisor within a given threshold, not necessarily prime factors.

How GhostInterview Helps

• Highlights factorization plus union-find pattern and guides through efficient implementation.
• Identifies failure modes like naive pairwise comparison and missing path compression optimization.
• Provides stepwise reasoning to track number-to-factor mapping and correct component size calculation.

Topic Pages

• Array
• Hash Table
• Math
• Union Find
• Number Theory

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the key insight for solving Largest Component Size by Common Factor?

The main insight is mapping each number to its prime factors and using union-find to merge numbers sharing any factor.

Can I use pairwise GCD checks for this problem?

Direct pairwise GCD checks are too slow for large arrays and will likely exceed time limits, making factor mapping essential.

Why is path compression important in this problem?

Path compression reduces the depth of union-find trees, speeding up subsequent find operations and overall component size calculations.

How do I count the size of each connected component efficiently?

After union operations, find each number's root and maintain a frequency map per root, then return the maximum count as the largest component size.

Does this approach work if numbers are not unique?

The solution assumes unique integers for correct mapping of factors; duplicates would require additional handling to merge all occurrences correctly.