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 <= 100Problem 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.
Python
Java
C++
Go
TypeScript
| 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 |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,273 views views
Watch 9 more video solutions →Practice Number of Unique Categories with our built-in code editor and test cases.
Practice on FleetCode