Number of Unique Categories solution and explanation
The 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): Returnstrueifaandbare in the same category andfalseotherwise. Also, if eitheraorbis not a valid number (i.e. it's greater than or equal tonor less than0), it returnsfalse.
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
Approach overview
Problem Overview: You are given n items, but their categories are hidden. The only operation available is an interactive API haveSameCategory(a, b) that returns whether two items belong to the same category. The goal is to determine how many distinct categories exist using as few checks as possible.
Approach 1: Pairwise Comparison (O(n²) time, O(n) space)
The most direct method compares every pair of items and groups them if the API reports they share the same category. A Union Find structure keeps track of connected components. For each pair (i, j), call haveSameCategory(i, j); if true, union the two indices. After processing all pairs, the number of disjoint sets equals the number of categories. This guarantees correctness but requires up to n(n−1)/2 API calls, which is expensive when n grows.
Approach 2: Representative Comparison with Union Find (O(n·k) time, O(n) space)
A more efficient strategy keeps one representative item for each discovered category. Iterate through the items from 0 to n-1. For the current item i, compare it only with existing representatives using haveSameCategory. If a match is found, union the two items in the Union Find structure and stop checking further representatives. If no match exists, treat i as the representative of a new category and add it to the list. If there are k categories, each item performs at most k checks, resulting in O(n·k) calls instead of O(n²).
This approach leverages the fact that once a representative for a category is known, all future elements only need to be compared against that representative rather than every prior element. The union-find structure maintains connectivity efficiently with path compression.
Recommended for interviews: The representative-based method combined with Union Find is what interviewers expect. The brute-force pairwise comparison demonstrates the core idea of grouping equal items, but the optimized version shows you understand how to minimize interactive queries and apply component tracking effectively. Problems like this combine interactive constraints with counting connected components, a common pattern in system-style interview questions.
Solution
# Definition for a category handler.
# class CategoryHandler:
# def haveSameCategory(self, a: int, b: int) -> bool:
# pass
class Solution:
def numberOfCategories(
self, n: int, categoryHandler: Optional['CategoryHandler']
) -> int:
def find(x: int) -> int:
if p[x] != x:
p[x] = find(p[x])
return p[x]
p = list(range(n))
for a in range(n):
for b in range(a + 1, n):
if categoryHandler.haveSameCategory(a, b):
p[find(a)] = find(b)
return sum(i == x for i, x in enumerate(p))/**
* Definition for a category handler.
* class CategoryHandler {
* public CategoryHandler(int[] categories);
* public boolean haveSameCategory(int a, int b);
* };
*/
class Solution {
private int[] p;
public int numberOfCategories(int n, CategoryHandler categoryHandler) {
p = new int[n];
for (int i = 0; i < n; ++i) {
p[i] = i;
}
for (int a = 0; a < n; ++a) {
for (int b = a + 1; b < n; ++b) {
if (categoryHandler.haveSameCategory(a, b)) {
p[find(a)] = find(b);
}
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
if (i == p[i]) {
++ans;
}
}
return ans;
}
private int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
}/**
* Definition for a category handler.
* class CategoryHandler {
* public:
* CategoryHandler(vector<int> categories);
* bool haveSameCategory(int a, int b);
* };
*/
class Solution {
public:
int numberOfCategories(int n, CategoryHandler* categoryHandler) {
vector<int> p(n);
iota(p.begin(), p.end(), 0);
function<int(int)> find = [&](int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
};
for (int a = 0; a < n; ++a) {
for (int b = a + 1; b < n; ++b) {
if (categoryHandler->haveSameCategory(a, b)) {
p[find(a)] = find(b);
}
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += i == p[i];
}
return ans;
}
};/**
* Definition for a category handler.
* class CategoryHandler {
* constructor(categories: number[]);
* public haveSameCategory(a: number, b: number): boolean;
* }
*/
function numberOfCategories(n: number, categoryHandler: CategoryHandler): number {
const p: number[] = new Array(n).fill(0).map((_, i) => i);
const find = (x: number): number => {
if (p[x] !== x) {
p[x] = find(p[x]);
}
return p[x];
};
for (let a = 0; a < n; ++a) {
for (let b = a + 1; b < n; ++b) {
if (categoryHandler.haveSameCategory(a, b)) {
p[find(a)] = find(b);
}
}
}
let ans = 0;
for (let i = 0; i < n; ++i) {
if (i === p[i]) {
++ans;
}
}
return ans;
}/**
* Definition for a category handler.
* type CategoryHandler interface {
* HaveSameCategory(int, int) bool
* }
*/
func numberOfCategories(n int, categoryHandler CategoryHandler) (ans int) {
p := make([]int, n)
for i := range p {
p[i] = i
}
var find func(int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
for a := 0; a < n; a++ {
for b := a + 1; b < n; b++ {
if categoryHandler.HaveSameCategory(a, b) {
p[find(a)] = find(b)
}
}
}
for i, x := range p {
if i == x {
ans++
}
}
return
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Pairwise Comparison with Union Find | O(n²) | O(n) | Simple baseline when constraints are small or query cost is irrelevant |
| Representative Comparison + Union Find | O(n·k) | O(n) | Best practical approach when minimizing interactive API calls |
| Representative Tracking without DSU | O(n·k) | O(k) | Works if only the category count is required and explicit unions are unnecessary |
Frequently asked questions
Is Number of Unique Categories easy or hard?
The problem is rated Medium because the algorithm itself is simple but requires reasoning about minimizing interactive queries. Understanding when to compare elements and how to track categories efficiently is the main challenge.
Number of Unique Categories Python/Java solution
Most implementations maintain a list of category representatives and a Union Find structure. For each item, call the interactive API against representatives until a match is found or a new category is created. The logic translates directly across Python, Java, C++, Go, and TypeScript.
How to solve Number of Unique Categories in O(n)?
Strict O(n) is not always possible because determining whether two items share a category requires interactive comparisons. The closest practical bound is O(n·k), where each item checks against existing category representatives instead of every previous item.
What is the best approach for Number of Unique Categories?
The representative comparison approach combined with Union Find is the most efficient strategy. Maintain one representative for each discovered category and compare new items only with those representatives using the interactive API. This reduces comparisons from O(n²) to O(n·k), where k is the number of categories.
Is Number of Unique Categories asked at Google/Amazon/Meta?
Problems involving grouping unknown relationships using Union Find and minimizing queries appear frequently in interviews at companies like Google, Amazon, and Meta. Interactive-style problems that limit the available operations test reasoning about queries and component discovery.
What data structure is used in Number of Unique Categories?
Union Find (Disjoint Set Union) is the primary data structure. It efficiently tracks which items belong to the same category and counts the number of connected components after comparisons.
What is the time complexity of Number of Unique Categories?
The optimized solution runs in O(n·k) time where n is the number of items and k is the number of unique categories. Each item is compared only with existing category representatives. Space complexity is O(n) when using a Union Find structure.