Number of unique categories

Union-Find Interactive Counting

83.8% acceptance

Mar 31, 2026

You are given an integer n and an object categoryHandler of class CategoryHandler. There are n elements, numbered from 0 to n - 1. Each element has a category, and your task is to find the number of unique categories. The class CategoryHandler contains the following function, which may help you: boolean haveSameCategory(integer a, integer b): Returns true if a and b are in the same category and false otherwise. Also, if either a or b is not a valid number (i.e. it's greater than or equal to nor less than 0), it returns false. Return the number of unique categories.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

/**
 * Definition for a category handler.
 * impl CategoryHandler {
 *     pub fn new(categories: Vec<i32>) -> Self {}
 *     pub fn have_same_category(&self, a: i32, b: i32) -> bool {}
 * }
 */
impl Solution {
  pub fn number_of_categories(n: i32, category_handler: CategoryHandler) -> i32 {
    let n = n as usize;
    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 {
        if category_handler.have_same_category(i as i32, j as i32) {
          let pi = find(&mut parent, i);
          let pj = find(&mut parent, j);
          parent[pi] = pj;
        }
      }
    }
    let mut count = 0;
    for i in 0..n {
      if find(&mut parent, i) == i {
        count += 1;
      }
    }
    count
  }
}