Largest Component Size by Common Factor

Hard

#0906Time: O(N^2 * log(M)), where N is the length of `nums` and M is the maximum value in `nums`. Building the graph requires checking `O(N^2)` pairs, and each check involves a GCD calculation which takes `O(log(M))` time. The subsequent graph traversal is dominated by the graph construction time.Space: O(N^2), where N is the number of elements in `nums`. This is for storing the adjacency list, which can have up to `O(N^2)` edges in a dense graph.

Patterns

Math Number Theory

Algorithms

Union Find

Data structures

Array Hash Table

Prompt

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⁴
1 <= nums[i] <= 10⁵
All the values of nums are unique.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly translates the problem statement into a graph data structure. It builds an explicit graph where nodes are the numbers from the input array. An edge is added between two nodes if their corresponding numbers share a common factor greater than 1. After building the graph, a standard graph traversal algorithm like Depth-First Search (DFS) or Breadth-First Search (BFS) is used to find the sizes of all connected components.

Algorithm

Initialize an adjacency list to represent the graph. The nodes correspond to the indices of the nums array.
Iterate through every unique pair of numbers (nums[i], nums[j]) from the input array.
For each pair, calculate their Greatest Common Divisor (GCD) using the Euclidean algorithm.
If gcd(nums[i], nums[j]) > 1, add an edge between node i and node j in the adjacency list.
Initialize a visited array to keep track of visited nodes and a variable maxSize to store the size of the largest component found so far.
Iterate from i = 0 to nums.length - 1. If node i has not been visited:
- Start a DFS or BFS traversal from node i.
- Count the number of nodes in the component discovered by the traversal.
- Update maxSize with the maximum of its current value and the size of the new component.
Return maxSize.

Walkthrough

1class Solution {2    public int largestComponentSize(int[] nums) {3        int n = nums.length;4        List<List<Integer>> adj = new ArrayList<>();5        for (int i = 0; i < n; i++) {6            adj.add(new ArrayList<>());7        }8 9        for (int i = 0; i < n; i++) {10            for (int j = i + 1; j < n; j++) {11                if (gcd(nums[i], nums[j]) > 1) {12                    adj.get(i).add(j);13                    adj.get(j).add(i);14                }15            }16        }17 18        boolean[] visited = new boolean[n];19        int maxSize = 0;20        for (int i = 0; i < n; i++) {21            if (!visited[i]) {22                int currentSize = dfs(i, adj, visited);23                maxSize = Math.max(maxSize, currentSize);24            }25        }26        return maxSize;27    }28 29    private int dfs(int u, List<List<Integer>> adj, boolean[] visited) {30        visited[u] = true;31        int count = 1;32        for (int v : adj.get(u)) {33            if (!visited[v]) {34                count += dfs(v, adj, visited);35            }36        }37        return count;38    }39 40    private int gcd(int a, int b) {41        while (b != 0) {42            int temp = b;43            b = a % b;44            a = temp;45        }46        return a;47    }48}

Complexity

Time

O(N^2 * log(M)), where N is the length of `nums` and M is the maximum value in `nums`. Building the graph requires checking `O(N^2)` pairs, and each check involves a GCD calculation which takes `O(log(M))` time. The subsequent graph traversal is dominated by the graph construction time.

Space

O(N^2), where N is the number of elements in `nums`. This is for storing the adjacency list, which can have up to `O(N^2)` edges in a dense graph.

Trade-offs

Pros

Simple to understand and directly follows the problem definition.

Cons

Inefficient for the given constraints. N^2 operations are too slow.
The space complexity can be very high, up to O(N^2), if the graph is dense.
This approach will likely result in a "Time Limit Exceeded" or "Memory Limit Exceeded" error on competitive programming platforms.

This approach improves upon the brute-force method by avoiding the explicit construction of the graph. It uses a Disjoint Set Union (DSU) or Union-Find data structure to group numbers into connected components. The key insight is that two numbers are in the same component if they share a common prime factor. We can iterate through each number, find its prime factors, and union it with any other number that shares one of those primes.

Algorithm

Initialize a Union-Find data structure for N elements, where N is the length of nums. Each number nums[i] initially belongs to its own set.
Create a hash map primeToIndex to store the first index i encountered for each prime factor p.
Iterate through each number x = nums[i] from i = 0 to N-1.
For the current number x, find all its distinct prime factors. A simple way is to use trial division up to sqrt(x).
For each prime factor p of x:
- Check if p exists as a key in primeToIndex.
- If it does, it means we've seen this prime before in another number nums[j], where j = primeToIndex.get(p). We then union the sets of i and j.
- If p does not exist in the map, we are seeing this prime for the first time. Store the current index i in the map: primeToIndex.put(p, i).
After processing all numbers, the DSU structure contains the connected components.
Iterate through all numbers again, count the size of each component (set) using a hash map, and find the maximum size.

Walkthrough

1class Solution {2    public int largestComponentSize(int[] nums) {3        int n = nums.length;4        DSU dsu = new DSU(n);5        Map<Integer, Integer> primeToIndex = new HashMap<>();6 7        for (int i = 0; i < n; i++) {8            int num = nums[i];9            for (int p = 2; p * p <= num; p++) {10                if (num % p == 0) {11                    if (!primeToIndex.containsKey(p)) {12                        primeToIndex.put(p, i);13                    }14                    dsu.union(i, primeToIndex.get(p));15                    while (num % p == 0) {16                        num /= p;17                    }18                }19            }20            if (num > 1) { // Remaining factor is prime21                if (!primeToIndex.containsKey(num)) {22                    primeToIndex.put(num, i);23                }24                dsu.union(i, primeToIndex.get(num));25            }26        }27 28        Map<Integer, Integer> componentCounts = new HashMap<>();29        int maxSize = 0;30        for (int i = 0; i < n; i++) {31            int root = dsu.find(i);32            int count = componentCounts.getOrDefault(root, 0) + 1;33            componentCounts.put(root, count);34            maxSize = Math.max(maxSize, count);35        }36        return maxSize;37    }38}39 40class DSU {41    int[] parent;42    public DSU(int n) {43        parent = new int[n];44        for (int i = 0; i < n; i++) parent[i] = i;45    }46    public int find(int i) {47        if (parent[i] == i) return i;48        return parent[i] = find(parent[i]);49    }50    public void union(int i, int j) {51        int rootI = find(i);52        int rootJ = find(j);53        if (rootI != rootJ) parent[rootJ] = rootI;54    }55}

Complexity

Time

O(N * sqrt(M)), where N is `nums.length` and M is the max value in `nums`. The bottleneck is the prime factorization for each of the N numbers, which takes `O(sqrt(M))` time. Union-Find operations are nearly constant time.

Space

O(N + P), where N is `nums.length` and P is the number of unique prime factors across all numbers. P is bounded by `π(M)`, the number of primes up to the maximum value M. This is efficient.

Trade-offs

Pros

Much more time and space efficient than the brute-force approach.
Avoids building a large O(N^2) graph by using an efficient DSU data structure.

Cons

The prime factorization step, which takes O(sqrt(M)) for each number, can still be a bottleneck if N and M are large.
While much better than brute-force, it may be borderline on passing the time limits for the strictest constraints.

This is the most efficient approach. It builds upon the Union-Find idea but optimizes the prime factorization step. Instead of factoring each number individually, we first pre-compute the smallest prime factor (SPF) for all numbers up to the maximum value in nums using a sieve. This allows for very fast factorization. The DSU structure then connects numbers with their prime factors, efficiently forming the components.

Algorithm

Find the maximum number M in the nums array.
Pre-computation: Create an array spf (Smallest Prime Factor) of size M+1. Populate it using a sieve algorithm in O(M log log M) time. spf[i] will store the smallest prime that divides i.
Union-Find Model: Initialize a DSU structure for M+1 elements. This DSU will manage sets for all numbers from 0 to M, allowing us to directly union a number x with its prime factors p.
Iterate through each number x in the nums array.
For each x, find its distinct prime factors using the pre-computed spf array. This is done by repeatedly dividing x by spf[x] until x becomes 1. This process takes O(log x) time.
For each prime factor p found, perform a union operation between the original number x and the prime p: dsu.union(x, p).
Counting: After processing all numbers, create a map to count the number of nums elements belonging to each component's root.
Iterate through nums one last time. For each x, find its root r = dsu.find(x) and increment the count for r.
The answer is the maximum count found in the map.

Walkthrough

1class Solution {2    public int largestComponentSize(int[] nums) {3        int maxVal = 0;4        for (int num : nums) {5            maxVal = Math.max(maxVal, num);6        }7 8        DSU dsu = new DSU(maxVal + 1);9        int[] spf = sieve(maxVal);10 11        for (int num : nums) {12            int temp = num;13            while (temp > 1) {14                int p = spf[temp];15                dsu.union(num, p);16                while (temp % p == 0) {17                    temp /= p;18                }19            }20        }21 22        Map<Integer, Integer> componentCounts = new HashMap<>();23        int maxSize = 0;24        for (int num : nums) {25            int root = dsu.find(num);26            int count = componentCounts.getOrDefault(root, 0) + 1;27            componentCounts.put(root, count);28            maxSize = Math.max(maxSize, count);29        }30 31        return maxSize;32    }33 34    private int[] sieve(int n) {35        int[] spf = new int[n + 1];36        for (int i = 2; i <= n; i++) {37            spf[i] = i;38        }39        for (int i = 2; i * i <= n; i++) {40            if (spf[i] == i) { // i is prime41                for (int j = i * i; j <= n; j += i) {42                    if (spf[j] == j) { // if spf[j] is not set yet43                        spf[j] = i;44                    }45                }46            }47        }48        return spf;49    }50}51 52class DSU {53    int[] parent;54 55    public DSU(int n) {56        parent = new int[n];57        for (int i = 0; i < n; i++) {58            parent[i] = i;59        }60    }61 62    public int find(int i) {63        if (parent[i] == i) {64            return i;65        }66        return parent[i] = find(parent[i]);67    }68 69    public void union(int i, int j) {70        int rootI = find(i);71        int rootJ = find(j);72        if (rootI != rootJ) {73            parent[rootJ] = rootI;74        }75    }76}

Complexity

Time

O(M log log M + N * log(M) * α(M)), where N is `nums.length`, M is the max value, and α is the inverse Ackermann function. `O(M log log M)` is for the sieve, and `O(N * log M)` is for iterating through numbers and their factors. This is highly efficient.

Space

O(M), where M is the maximum value in `nums`. This space is used for the `spf` array and the DSU `parent` array.

Trade-offs

Pros

Optimal time complexity for the given constraints.
The sieve pre-computation significantly speeds up the critical step of finding prime factors, making the overall solution very fast.

Cons

More complex to implement due to the sieve pre-computation step.
Uses more memory, O(M), which could be large if the maximum number is much larger than N.

Solutions

Solution

1class UnionFind { int [] p ; UnionFind ( int n ) { p = new int [ n ]; for ( int i = 0 ; i < n ; ++ i ) { p [ i ] = i ; } } void union ( int a , int b ) { int pa = find ( a ), pb = find ( b ); if ( pa != pb ) { p [ pa ] = pb ; } } int find ( int x ) { if ( p [ x ] != x ) { p [ x ] = find ( p [ x ]); } return p [ x ]; } } class Solution { public int largestComponentSize ( int [] nums ) { int m = 0 ; for ( int v : nums ) { m = Math . max ( m , v ); } UnionFind uf = new UnionFind ( m + 1 ); for ( int v : nums ) { int i = 2 ; while ( i <= v / i ) { if ( v % i == 0 ) { uf . union ( v , i ); uf . union ( v , v / i ); } ++ i ; } } int [] cnt = new int [ m + 1 ]; int ans = 0 ; for ( int v : nums ) { int t = uf . find ( v ); ++ cnt [ t ]; ans = Math . max ( ans , cnt [ t ]); } return ans ; } }

1class UnionFind { public: vector < int > p ; int n ; UnionFind ( int _n ) : n ( _n ) , p ( _n ) { iota ( p . begin (), p . end (), 0 ); } void unite ( int a , int b ) { int pa = find ( a ), pb = find ( b ); if ( pa != pb ) p [ pa ] = pb ; } int find ( int x ) { if ( p [ x ] != x ) p [ x ] = find ( p [ x ]); return p [ x ]; } }; class Solution { public: int largestComponentSize ( vector < int >& nums ) { int m = * max_element ( nums . begin (), nums . end ()); UnionFind * uf = new UnionFind ( m + 1 ); for ( int v : nums ) { int i = 2 ; while ( i <= v / i ) { if ( v % i == 0 ) { uf -> unite ( v , i ); uf -> unite ( v , v / i ); } ++ i ; } } vector < int > cnt ( m + 1 ); int ans = 0 ; for ( int v : nums ) { int t = uf -> find ( v ); ++ cnt [ t ]; ans = max ( ans , cnt [ t ]); } return ans ; } };

1class UnionFind : def __init__ ( self , n ): self . p = list ( range ( n )) def union ( self , a , b ): pa , pb = self . find ( a ), self . find ( b ) if pa != pb : self . p [ pa ] = pb def find ( self , x ): if self . p [ x ] != x : self . p [ x ] = self . find ( self . p [ x ]) return self . p [ x ] class Solution : def largestComponentSize ( self , nums : List [ int ]) -> int : uf = UnionFind ( max ( nums ) + 1 ) for v in nums : i = 2 while i <= v // i : if v % i == 0 : uf . union ( v , i ) uf . union ( v , v // i ) i += 1 return max ( Counter ( uf . find ( v ) for v in nums ). values ())

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class UnionFind { int [] p ; UnionFind ( int n ) { p = new int [ n ]; for ( int i = 0 ; i < n ; ++ i ) { p [ i ] = i ; } } void union ( int a , int b ) { int pa = find ( a ), pb = find ( b ); if ( pa != pb ) { p [ pa ] = pb ; } } int find ( int x ) { if ( p [ x ] != x ) { p [ x ] = find ( p [ x ]); } return p [ x ]; } } class Solution { public int largestComponentSize ( int [] nums ) { int m = 0 ; for ( int v : nums ) { m = Math . max ( m , v ); } UnionFind uf = new UnionFind ( m + 1 ); for ( int v : nums ) { int i = 2 ; while ( i <= v / i ) { if ( v % i == 0 ) { uf . union ( v , i ); uf . union ( v , v / i ); } ++ i ; } } int [] cnt = new int [ m + 1 ]; int ans = 0 ; for ( int v : nums ) { int t = uf . find ( v ); ++ cnt [ t ]; ans = Math . max ( ans , cnt [ t ]); } return ans ; } }

1class UnionFind { public: vector < int > p ; int n ; UnionFind ( int _n ) : n ( _n ) , p ( _n ) { iota ( p . begin (), p . end (), 0 ); } void unite ( int a , int b ) { int pa = find ( a ), pb = find ( b ); if ( pa != pb ) p [ pa ] = pb ; } int find ( int x ) { if ( p [ x ] != x ) p [ x ] = find ( p [ x ]); return p [ x ]; } }; class Solution { public: int largestComponentSize ( vector < int >& nums ) { int m = * max_element ( nums . begin (), nums . end ()); UnionFind * uf = new UnionFind ( m + 1 ); for ( int v : nums ) { int i = 2 ; while ( i <= v / i ) { if ( v % i == 0 ) { uf -> unite ( v , i ); uf -> unite ( v , v / i ); } ++ i ; } } vector < int > cnt ( m + 1 ); int ans = 0 ; for ( int v : nums ) { int t = uf -> find ( v ); ++ cnt [ t ]; ans = max ( ans , cnt [ t ]); } return ans ; } };

1class UnionFind : def __init__ ( self , n ): self . p = list ( range ( n )) def union ( self , a , b ): pa , pb = self . find ( a ), self . find ( b ) if pa != pb : self . p [ pa ] = pb def find ( self , x ): if self . p [ x ] != x : self . p [ x ] = self . find ( self . p [ x ]) return self . p [ x ] class Solution : def largestComponentSize ( self , nums : List [ int ]) -> int : uf = UnionFind ( max ( nums ) + 1 ) for v in nums : i = 2 while i <= v // i : if v % i == 0 : uf . union ( v , i ) uf . union ( v , v // i ) i += 1 return max ( Counter ( uf . find ( v ) for v in nums ). values ())

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.