Largest component size by common factor

Array Hash Table Math Union-Find Number Theory

42.4% acceptance

Feb 25, 2026

1722

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.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn largest_component_size(nums: Vec<i32>) -> i32 {
    let max_val = *nums.iter().max().unwrap() as usize + 1;
    let mut parent: Vec<usize> = (0..max_val).collect();
    fn find(p: &mut Vec<usize>, x: usize) -> usize {
      if p[x] != x { p[x] = find(p, p[x]); }
      p[x]
    }
    fn union(p: &mut Vec<usize>, x: usize, y: usize) {
      let px = find(p, x);
      let py = find(p, y);
      if px != py { p[px] = py; }
    }
    for &num in &nums {
      let num = num as usize;
      let mut f = 2;
      let mut n = num;
      while f * f <= n {
        if n % f == 0 {
          union(&mut parent, num, f);
          while n % f == 0 { n /= f; }
        }
        f += 1;
      }
      if n > 1 { union(&mut parent, num, n); }
    }
    let mut count = std::collections::HashMap::new();
    let mut ans = 0;
    for &num in &nums {
      let root = find(&mut parent, num as usize);
      let c = count.entry(root).or_insert(0);
      *c += 1;
      ans = ans.max(*c);
    }
    ans
  }
}