2782

2782. Number of Unique Categories (Medium)

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.

 

Example 1:

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:

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:

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

Companies: Amazon

Related Topics:
Union Find, Interactive, Counting

Hints:

• It can be proven that all pairs should be asked from the helper function.
• Iterate from the first element. For each element i, ask the helper function i with all j < i.
• If there is some j < i that i and j belong to the same group, go to next i. Otherwise, add one to the current number of groups.

Solution 1.

// OJ: https://leetcode.com/problems/number-of-unique-categories
// Author: github.com/lzl124631x
// Time: O(N^2 * logN)
// Space: O(N)
class UnionFind {
    vector<int> id;
    int cnt;
public:
    UnionFind(int N) : id(N), cnt(N) {
        iota(begin(id), end(id), 0);
    }
    int find(int x) { return id[x] == x ? x : (id[x] = find(id[x])); }
    void connect(int a, int b) {
        int p = find(a), q = find(b);
        if (p == q) return;
        id[p] = q;
        cnt--;
    }
    int getCount() { return cnt; }
};
class Solution {
public:
    int numberOfCategories(int n, CategoryHandler* categoryHandler) {
        UnionFind uf(n);
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (categoryHandler->haveSameCategory(i, j)) uf.connect(i, j);
            }
        }
        return uf.getCount();
    }
};