Scale Engineer

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
MathNumber Theory
Algorithms
Union Find
Data structures
ArrayHash 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 * 104
  • 1 <= nums[i] <= 105
  • 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

class Solution {    public int largestComponentSize(int[] nums) {        int n = nums.length;        List<List<Integer>> adj = new ArrayList<>();        for (int i = 0; i < n; i++) {            adj.add(new ArrayList<>());        }         for (int i = 0; i < n; i++) {            for (int j = i + 1; j < n; j++) {                if (gcd(nums[i], nums[j]) > 1) {                    adj.get(i).add(j);                    adj.get(j).add(i);                }            }        }         boolean[] visited = new boolean[n];        int maxSize = 0;        for (int i = 0; i < n; i++) {            if (!visited[i]) {                int currentSize = dfs(i, adj, visited);                maxSize = Math.max(maxSize, currentSize);            }        }        return maxSize;    }     private int dfs(int u, List<List<Integer>> adj, boolean[] visited) {        visited[u] = true;        int count = 1;        for (int v : adj.get(u)) {            if (!visited[v]) {                count += dfs(v, adj, visited);            }        }        return count;    }     private int gcd(int a, int b) {        while (b != 0) {            int temp = b;            b = a % b;            a = temp;        }        return a;    }}

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.

Solutions

class 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 ; } }

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 →

Next problem