Properties graph

Array Hash Table Depth-First Search Breadth-First Search Union-Find Graph Theory

48.5% acceptance

Feb 25, 2026

You are given a 2D integer array properties having dimensions n x m and an integer k. Define a function intersect(a, b) that returns the number of distinct integers common to both arrays a and b. Construct an undirected graph where each index i corresponds to properties[i]. There is an edge between node i and node j if and only if intersect(properties[i], properties[j]) >= k, where i and j are in the range [0, n - 1] and i != j. Return the number of connected components in the resulting graph.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_components(properties: Vec<Vec<i32>>, k: i32) -> i32 {
    use std::collections::HashSet;
    let n = properties.len();
    let k = k as usize;
    // Build sets for each node
    let sets: Vec<HashSet<i32>> = properties.iter().map(|p| p.iter().copied().collect()).collect();
    // Union-Find
    let mut parent: Vec<usize> = (0..n).collect();
    fn find(parent: &mut Vec<usize>, x: usize) -> usize {
      if parent[x] != x { parent[x] = find(parent, parent[x]); }
      parent[x]
    }
    for i in 0..n {
      for j in i+1..n {
        let intersection = sets[i].intersection(&sets[j]).count();
        if intersection >= k {
          let pi = find(&mut parent, i);
          let pj = find(&mut parent, j);
          if pi != pj { parent[pi] = pj; }
        }
      }
    }
    let components: HashSet<usize> = (0..n).map(|i| find(&mut parent, i)).collect();
    components.len() as i32
  }
}