Number of Unique Categories

Problem

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.

Examples

Example 1:

1
2
3


Input: n = 6, categoryHandler = [1,1,2,2,3,3]
Output: 3
Explanation: There are 6 elements in this example. The first two elements belong to category 1, the second two belong to category 2, and the last two elements belong to category 3. So there are 3 unique categories.

Example 2:

1
2
3


Input: n = 5, categoryHandler = [1,2,3,4,5]
Output: 5
Explanation: There are 5 elements in this example. Each element belongs to a unique category. So there are 5 unique categories.

Example 3:

1
2
3


Input: n = 3, categoryHandler = [1,1,1]
Output: 1
Explanation: There are 3 elements in this example. All of them belong to one category. So there is only 1 unique category.

Constraints:

1 <= n <= 100

Solution

Method 1 – Union-Find (Disjoint Set Union)

Intuition

We can use union-find to group elements that are in the same category. For each pair (i, j), if haveSameCategory(i, j) is true, we union them. The number of unique categories is the number of unique roots.

Approach

Initialize a parent array for union-find.
For each i < j, if haveSameCategory(i, j), union i and j.
Count the number of unique roots at the end.

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 numberOfCategories(int n, CategoryHandler categoryHandler) {
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                if (categoryHandler.haveSameCategory(i, j)) union(parent, i, j);
            }
        }
        Set<Integer> roots = new HashSet<>();
        for (int i = 0; i < n; i++) roots.add(find(parent, i));
        return roots.size();
    }
    private int find(int[] parent, int x) {
        if (parent[x] != x) parent[x] = find(parent, parent[x]);
        return parent[x];
    }
    private void union(int[] parent, int x, int y) {
        parent[find(parent, x)] = find(parent, y);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution:
    def numberOfCategories(self, n: int, categoryHandler: 'CategoryHandler') -> int:
        parent = list(range(n))
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        def union(x, y):
            parent[find(x)] = find(y)
        for i in range(n):
            for j in range(i+1, n):
                if categoryHandler.haveSameCategory(i, j):
                    union(i, j)
        return len(set(find(i) for i in range(n)))

 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 numberOfCategories(int n, CategoryHandler& categoryHandler) {
        vector<int> parent(n);
        iota(parent.begin(), parent.end(), 0);
        function<int(int)> find = [&](int x) {
            return parent[x] == x ? x : parent[x] = find(parent[x]);
        };
        auto union_set = [&](int x, int y) {
            parent[find(x)] = find(y);
        };
        for (int i = 0; i < n; ++i) {
            for (int j = i+1; j < n; ++j) {
                if (categoryHandler.haveSameCategory(i, j)) union_set(i, j);
            }
        }
        unordered_set<int> roots;
        for (int i = 0; i < n; ++i) roots.insert(find(i));
        return roots.size();
    }
};

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


func numberOfCategories(n int, categoryHandler CategoryHandler) int {
    parent := make([]int, n)
    for i := range parent { parent[i] = i }
    var find func(int) int
    find = func(x int) int {
        if parent[x] != x { parent[x] = find(parent[x]) }
        return parent[x]
    }
    union := func(x, y int) { parent[find(x)] = find(y) }
    for i := 0; i < n; i++ {
        for j := i+1; j < n; j++ {
            if categoryHandler.HaveSameCategory(i, j) { union(i, j) }
        }
    }
    roots := map[int]struct{}{}
    for i := 0; i < n; i++ { roots[find(i)] = struct{}{} }
    return len(roots)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
    fun numberOfCategories(n: Int, categoryHandler: CategoryHandler): Int {
        val parent = IntArray(n) { it }
        fun find(x: Int): Int {
            if (parent[x] != x) parent[x] = find(parent[x])
            return parent[x]
        }
        fun union(x: Int, y: Int) { parent[find(x)] = find(y) }
        for (i in 0 until n) {
            for (j in i+1 until n) {
                if (categoryHandler.haveSameCategory(i, j)) union(i, j)
            }
        }
        return (0 until n).map { find(it) }.toSet().size
    }
}

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


impl Solution {
    pub fn number_of_categories(n: i32, category_handler: &mut 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 (a, b) = (find(&mut parent, i), find(&mut parent, j));
                    parent[a] = b;
                }
            }
        }
        let mut roots = std::collections::HashSet::new();
        for i in 0..n { roots.insert(find(&mut parent, i)); }
        roots.len() as i32
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution {
    numberOfCategories(n: number, categoryHandler: { haveSameCategory(a: number, b: number): boolean }): number {
        const parent = Array.from({length: n}, (_, i) => i)
        const find = (x: number): number => parent[x] === x ? x : (parent[x] = find(parent[x]))
        const union = (x: number, y: number) => { parent[find(x)] = find(y) }
        for (let i = 0; i < n; i++) {
            for (let j = i+1; j < n; j++) {
                if (categoryHandler.haveSameCategory(i, j)) union(i, j)
            }
        }
        const roots = new Set<number>()
        for (let i = 0; i < n; i++) roots.add(find(i))
        return roots.size
    }
}

Complexity

⏰ Time complexity: O(n^2 * α(n)) (α is inverse Ackermann, nearly constant)
🧺 Space complexity: O(n)

Problem#

Examples#

Solution#

Method 1 – Union-Find (Disjoint Set Union)#

Intuition#

Approach#

Code#

Complexity#