Skip to main content
Talentd

Number of Unique Categories - Solution & Explanation

MediumPremiumFree on FleetCodeUnion FindInteractiveCounting6 min readAsked at: Amazon
Practice this problem

Problem Statement

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

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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Pairwise Comparison with Union FindO(n²)O(n)Simple baseline when constraints are small or query cost is irrelevant
Representative Comparison + Union FindO(n·k)O(n)Best practical approach when minimizing interactive API calls
Representative Tracking without DSUO(n·k)O(k)Works if only the category count is required and explicit unions are unnecessary

Video Solution

LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,273 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Number of Unique Categories with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Consecutive Sequence

Next

Surrounded Regions