Count connected components in lcm graph

Array Hash Table Math Union-Find Number Theory

31.0% acceptance

Feb 24, 2026

You are given an array of integers nums of size n and a positive integer threshold. There is a graph consisting of n nodes with the ith node having a value of nums[i]. Two nodes i and j in the graph are connected via an undirected edge if lcm(nums[i], nums[j]) <= threshold. Return the number of connected components in this graph. A connected component is a subgraph of a graph in which there exists a path between any two vertices, and no vertex of the subgraph shares an edge with a vertex outside of the subgraph. The term lcm(a, b) denotes the least common multiple of a and b.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_components(nums: Vec<i32>, threshold: i32) -> i32 {
    // Key insight: lcm(a,b) <= threshold only if BOTH a <= threshold AND b <= threshold
    // So any num > threshold is isolated.
    // For nums <= threshold: connect multiples via Union-Find keyed on value
    // Enumerate multiples: for each v in 1..=threshold, if it appears in nums,
    // connect v with all its multiples that also appear in nums (via v, 2v, 3v, ...)
    
    let n = nums.len();
    let t = threshold as usize;
    
    // Map value -> index
    let mut val_to_idx = std::collections::HashMap::new();
    for (i, &x) in nums.iter().enumerate() {
      val_to_idx.insert(x as usize, i);
    }
    
    // Union-Find
    let mut parent: Vec<usize> = (0..n).collect();
    let mut rank = vec![0u32; n];
    
    fn find(parent: &mut Vec<usize>, x: usize) -> usize {
      if parent[x] != x {
        parent[x] = find(parent, parent[x]);
      }
      parent[x]
    }
    
    fn union(parent: &mut Vec<usize>, rank: &mut Vec<u32>, a: usize, b: usize) {
      let ra = find(parent, a);
      let rb = find(parent, b);
      if ra == rb { return; }
      if rank[ra] < rank[rb] { parent[ra] = rb; }
      else if rank[ra] > rank[rb] { parent[rb] = ra; }
      else { parent[rb] = ra; rank[ra] += 1; }
    }
    
    // For each value m <= threshold: enumerate all divisors of m that appear in nums
    // and union them all (since lcm(a,b) | m => lcm(a,b) <= threshold)
    for m in 1..=t {
      let mut first_idx: Option<usize> = None;
      // enumerate proper divisors of m
      let mut d = 1usize;
      while d * d <= m {
        if m % d == 0 {
          for &dv in &[d, m / d] {
            if let Some(&idx) = val_to_idx.get(&dv) {
              if let Some(fi) = first_idx {
                union(&mut parent, &mut rank, fi, idx);
              } else {
                first_idx = Some(idx);
              }
            }
          }
        }
        d += 1;
      }
    }
    
    // Count unique roots
    let mut roots = std::collections::HashSet::new();
    for i in 0..n {
      roots.insert(find(&mut parent, i));
    }
    roots.len() as i32
  }
}