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.

Description Hints 3 Solution

2782. Number of Unique Categories

Medium83.8% acceptance1 companyPremium elsewhere, free here

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

Asked at 1 company

Amazon

Topics

Hints open one at a time

Hint 1

It can be proven that all pairs should be asked from the helper function.

Hint 2

Iterate from the first element. For each element `i`, ask the helper function `i` with all `j < i`.

Hint 3

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.

Still stuck?Read the written solution.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

6
[1,1,2,2,3,3]

Input

5
[1,2,3,4,5]

Input

3
[1,1,1]

Your code is saved on this device.Solution