Problem

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.

Examples

Example 1

1
2
3
4
5
6
7
8


![](https://assets.leetcode.com/uploads/2018/12/01/ex1.png)

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

Example 2

1
2
3
4
5
6
7
8


![](https://assets.leetcode.com/uploads/2018/12/01/ex2.png)

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

Example 3

1
2
3
4
5
6
7
8


![](https://assets.leetcode.com/uploads/2018/12/01/ex3.png)

    
    
    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.

Solution

Method 1 – Union-Find with Factor Mapping

Intuition

If two numbers share a common factor greater than 1, they should be in the same component. We can use union-find to group numbers by their factors. For each number, union it with all its factors greater than 1. The largest component is the one with the most numbers.

Approach

  1. For each number, find all its factors greater than 1.
  2. Use union-find to union the number with each of its factors.
  3. After processing all numbers, count the size of each component by grouping numbers by their root parent.
  4. Return the size of the largest component.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int largestComponentSize(vector<int>& nums) {
        int n = *max_element(nums.begin(), nums.end());
        vector<int> par(n+1);
        iota(par.begin(), par.end(), 0);
        function<int(int)> find = [&](int x) { return par[x] == x ? x : par[x] = find(par[x]); };
        for (int x : nums) {
            for (int f = 2; f * f <= x; ++f) {
                if (x % f == 0) {
                    par[find(x)] = find(f);
                    par[find(x)] = find(x/f);
                }
            }
        }
        unordered_map<int, int> cnt;
        int ans = 0;
        for (int x : nums) ans = max(ans, ++cnt[find(x)]);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func largestComponentSize(nums []int) int {
    n := 0
    for _, x := range nums { if x > n { n = x } }
    par := make([]int, n+1)
    for i := range par { par[i] = i }
    var find func(int) int
    find = func(x int) int { if par[x] != x { par[x] = find(par[x]) }; return par[x] }
    for _, x := range nums {
        for f := 2; f*f <= x; f++ {
            if x%f == 0 {
                par[find(x)] = find(f)
                par[find(x)] = find(x/f)
            }
        }
    }
    cnt := map[int]int{}
    ans := 0
    for _, x := range nums {
        fx := find(x)
        cnt[fx]++
        if cnt[fx] > ans { ans = cnt[fx] }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    public int largestComponentSize(int[] nums) {
        int n = Arrays.stream(nums).max().getAsInt();
        int[] par = new int[n+1];
        for (int i = 0; i <= n; ++i) par[i] = i;
        for (int x : nums) {
            for (int f = 2; f * f <= x; ++f) {
                if (x % f == 0) {
                    union(par, x, f);
                    union(par, x, x/f);
                }
            }
        }
        Map<Integer, Integer> cnt = new HashMap<>();
        int ans = 0;
        for (int x : nums) {
            int fx = find(par, x);
            cnt.put(fx, cnt.getOrDefault(fx, 0) + 1);
            ans = Math.max(ans, cnt.get(fx));
        }
        return ans;
    }
    private int find(int[] par, int x) {
        if (par[x] != x) par[x] = find(par, par[x]);
        return par[x];
    }
    private void union(int[] par, int x, int y) {
        par[find(par, x)] = find(par, y);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    fun largestComponentSize(nums: IntArray): Int {
        val n = nums.maxOrNull()!!
        val par = IntArray(n+1) { it }
        fun find(x: Int): Int = if (par[x] == x) x else { par[x] = find(par[x]); par[x] }
        for (x in nums) {
            var f = 2
            while (f * f <= x) {
                if (x % f == 0) {
                    par[find(x)] = find(f)
                    par[find(x)] = find(x/f)
                }
                f++
            }
        }
        val cnt = mutableMapOf<Int, Int>()
        var ans = 0
        for (x in nums) {
            val fx = find(x)
            cnt[fx] = cnt.getOrDefault(fx, 0) + 1
            ans = maxOf(ans, cnt[fx]!!)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def largestComponentSize(self, nums: list[int]) -> int:
        n = max(nums)
        par = list(range(n+1))
        def find(x: int) -> int:
            if par[x] != x:
                par[x] = find(par[x])
            return par[x]
        for x in nums:
            for f in range(2, int(x**0.5)+1):
                if x % f == 0:
                    par[find(x)] = find(f)
                    par[find(x)] = find(x//f)
        cnt = {}
        ans = 0
        for x in nums:
            fx = find(x)
            cnt[fx] = cnt.get(fx, 0) + 1
            ans = max(ans, cnt[fx])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

impl Solution {
    pub fn largest_component_size(nums: Vec<i32>) -> i32 {
        let n = *nums.iter().max().unwrap() as usize;
        let mut par: Vec<usize> = (0..=n).collect();
        fn find(par: &mut Vec<usize>, x: usize) -> usize {
            if par[x] != x { par[x] = find(par, par[x]); }
            par[x]
        }
        for &x in &nums {
            let mut f = 2;
            while f * f <= x {
                if x % f == 0 {
                    let fx = find(&mut par, x as usize);
                    let ff = find(&mut par, f as usize);
                    par[fx] = ff;
                    let fx = find(&mut par, x as usize);
                    let ff = find(&mut par, (x/f) as usize);
                    par[fx] = ff;
                }
                f += 1;
            }
        }
        let mut cnt = std::collections::HashMap::new();
        let mut ans = 0;
        for &x in &nums {
            let fx = find(&mut par, x as usize);
            let c = cnt.entry(fx).or_insert(0);
            *c += 1;
            if *c > ans { ans = *c; }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    largestComponentSize(nums: number[]): number {
        const n = Math.max(...nums)
        const par = Array.from({length: n+1}, (_, i) => i)
        const find = (x: number): number => par[x] === x ? x : (par[x] = find(par[x]))
        for (const x of nums) {
            for (let f = 2; f * f <= x; ++f) {
                if (x % f === 0) {
                    par[find(x)] = find(f)
                    par[find(x)] = find(Math.floor(x/f))
                }
            }
        }
        const cnt = new Map<number, number>()
        let ans = 0
        for (const x of nums) {
            const fx = find(x)
            cnt.set(fx, (cnt.get(fx) ?? 0) + 1)
            ans = Math.max(ans, cnt.get(fx)!)
        }
        return ans
    }
}

Complexity

  • ⏰ Time complexity: O(n * sqrt(M)), where n is the length of nums and M is the maximum value in nums. For each number, we check all its factors up to sqrt(M).
  • 🧺 Space complexity: O(M), for the union-find parent array and counting map.