LeetCode 2782 - Number of Unique Categories

This problem asks us to determine how many distinct categories exist among n elements. The elements are labeled from 0 to n - 1, but we are not given the category values directly.

leetcodemediumunion-findinteractivecounting

LeetCode Problem 2782

Difficulty: 🟡 Medium
Topics: Union-Find, Interactive, Counting

Solution

Problem Understanding

This problem asks us to determine how many distinct categories exist among n elements. The elements are labeled from 0 to n - 1, but we are not given the category values directly. Instead, we interact with the hidden categorization through the provided API:

haveSameCategory(a, b)

This function tells us whether two elements belong to the same category.

In other words, the categories are hidden, and the only operation we can perform is comparing pairs of elements. Our goal is to group together all elements that belong to the same category and then count how many such groups exist.

The input consists of:

  • n, the number of elements
  • categoryHandler, an interface object that exposes the comparison function

The output is a single integer representing the number of unique categories.

The constraints are small:

1 <= n <= 100

This is important because it tells us we can afford algorithms with quadratic time complexity. Since there are at most 100 elements, even checking all pairs is completely reasonable.

The problem is essentially asking us to identify connected groups of equivalent elements. If element a is in the same category as b, and b is in the same category as c, then all three belong to one category. This transitive grouping behavior is exactly what Union-Find, also called Disjoint Set Union or DSU, is designed for.

Several edge cases are important:

  • Every element could belong to a different category, so the answer would be n.
  • All elements could belong to one category, so the answer would be 1.
  • Categories may contain only a single element.
  • The comparison API is the only source of information, so we must avoid assumptions about category IDs or ordering.
  • Because haveSameCategory() returns false for invalid indices, we must ensure we only query valid element indices.

Approaches

Brute Force Approach

A straightforward solution is to build groups manually.

We can iterate through every element and try to place it into an existing category group. For each element, we compare it against a representative element from every previously discovered group. If it matches one of them, we place it into that group. Otherwise, we create a new group.

This works because if an element belongs to a category, it must match at least one representative of that category.

For example:

  • Start with no groups.
  • Process element 0, create a new group.
  • Process element 1, compare with group representatives.
  • If it matches an existing representative, join that group.
  • Otherwise create another group.

Since we may compare each element against many representatives, the total complexity becomes quadratic.

Although this approach is acceptable for n <= 100, it does not explicitly model connectivity relationships between elements.

Optimal Approach, Union-Find

The key insight is that elements belonging to the same category form connected components.

If:

haveSameCategory(a, b) == true

then a and b belong to the same set.

Union-Find is ideal for this kind of grouping problem because it efficiently merges connected elements and tracks which elements belong to the same component.

The algorithm works as follows:

  • Initially, every element is its own category.
  • Compare every pair (i, j).
  • If they belong to the same category, union their sets.
  • After processing all pairs, count how many unique roots remain.

This directly models the category structure.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Maintains explicit category groups
Optimal O(n² * α(n)) O(n) Uses Union-Find to merge equivalent elements

Here, α(n) is the inverse Ackermann function, which grows so slowly that it is effectively constant.

Algorithm Walkthrough

Step 1: Initialize Union-Find

Create a parent array where each element initially points to itself.

parent[i] = i

At the beginning, every element is treated as its own category.

Step 2: Define the Find Operation

The find(x) operation returns the representative root of the set containing x.

We use path compression so future lookups become faster.

If an element's parent is not itself, recursively find the root and compress the path.

Step 3: Define the Union Operation

The union(a, b) operation merges the sets containing a and b.

We first find the roots of both elements:

rootA = find(a)
rootB = find(b)

If the roots differ, connect one root to the other.

This merges the two categories into a single component.

Step 4: Compare Every Pair

Iterate through all pairs:

for i in range(n):
    for j in range(i + 1, n):

We only check j > i because comparisons are symmetric.

For each pair:

  • Call haveSameCategory(i, j)
  • If true, union the two elements

This gradually merges all connected elements into the same set.

Step 5: Count Unique Roots

After all unions are complete, each connected component has exactly one representative root.

Compute:

len(set(find(i) for i in range(n)))

This gives the number of unique categories.

Why it works

Union-Find maintains the invariant that all elements in the same connected component share the same root.

Whenever two elements belong to the same category, we union their sets. Because category membership is transitive, repeated unions correctly merge all related elements into one component.

At the end, every category corresponds to exactly one connected component, so counting distinct roots gives the correct answer.

Python Solution

# Definition for a category handler.
# class CategoryHandler:
#     def haveSameCategory(self, a: int, b: int) -> bool:
#         pass

from typing import Optional

class Solution:
    def numberOfCategories(
        self,
        n: int,
        categoryHandler: Optional['CategoryHandler']
    ) -> int:
        
        parent = list(range(n))

        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(a: int, b: int) -> None:
            root_a = find(a)
            root_b = find(b)

            if root_a != root_b:
                parent[root_a] = root_b

        for i in range(n):
            for j in range(i + 1, n):
                if categoryHandler.haveSameCategory(i, j):
                    union(i, j)

        unique_roots = set()

        for i in range(n):
            unique_roots.add(find(i))

        return len(unique_roots)

The implementation begins by initializing the Union-Find parent array. Each element initially belongs to its own set.

The find() function uses path compression. Whenever we search for the root of a node, we directly attach that node to the root. This reduces the depth of the tree and improves future operations.

The union() function merges two components by connecting their roots.

Next, the nested loops compare every pair of elements. Whenever the handler reports that two elements share the same category, we merge their sets.

Finally, we compute the root for every element and insert it into a set. Since each category corresponds to exactly one root, the size of the set is the answer.

Go Solution

/**
 * Definition for a category handler.
 * type CategoryHandler interface {
 *     HaveSameCategory(int, int) bool
 * }
 */

func numberOfCategories(n int, categoryHandler CategoryHandler) int {
	parent := make([]int, n)

	for i := 0; i < n; i++ {
		parent[i] = i
	}

	var find func(int) int

	find = func(x int) int {
		if parent[x] != x {
			parent[x] = find(parent[x])
		}
		return parent[x]
	}

	union := func(a int, b int) {
		rootA := find(a)
		rootB := find(b)

		if rootA != rootB {
			parent[rootA] = rootB
		}
	}

	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if categoryHandler.HaveSameCategory(i, j) {
				union(i, j)
			}
		}
	}

	uniqueRoots := make(map[int]bool)

	for i := 0; i < n; i++ {
		root := find(i)
		uniqueRoots[root] = true
	}

	return len(uniqueRoots)
}

The Go implementation follows the same logic as the Python version.

One difference is that Go does not support nested named functions as naturally as Python, so find is declared as a function variable before assignment.

Instead of using a Python set, Go uses a map[int]bool to track unique roots.

There are no integer overflow concerns because the values are very small, and Go slices provide efficient array-like storage for the parent structure.

Worked Examples

Example 1

n = 6
categories = [1,1,2,2,3,3]

Initially:

Element Parent
0 0
1 1
2 2
3 3
4 4
5 5

Comparisons:

Pair Same Category? Action
(0,1) True Union 0 and 1
(0,2) False None
(0,3) False None
(0,4) False None
(0,5) False None
(1,2) False None
(1,3) False None
(2,3) True Union 2 and 3
(4,5) True Union 4 and 5

Final groups:

{0,1}
{2,3}
{4,5}

Number of unique roots:

3

Example 2

n = 5
categories = [1,2,3,4,5]

No pair shares a category.

No unions occur.

Final roots:

0,1,2,3,4

Answer:

5

Example 3

n = 3
categories = [1,1,1]

Comparisons:

Pair Same Category? Action
(0,1) True Union
(0,2) True Union
(1,2) True Already connected

All elements end in the same component.

Answer:

1

Complexity Analysis

Measure Complexity Explanation
Time O(n² * α(n)) Every pair is checked once, Union-Find operations are nearly constant
Space O(n) Parent array and root tracking set

The nested loops dominate the runtime because we compare all pairs of elements. There are approximately n² / 2 comparisons.

Union-Find operations use path compression, making each operation effectively constant time for practical input sizes.

The space usage is linear because we store one parent entry per element.

Test Cases

class MockCategoryHandler:
    def __init__(self, categories):
        self.categories = categories

    def haveSameCategory(self, a, b):
        return self.categories[a] == self.categories[b]

solution = Solution()

# Example 1
handler = MockCategoryHandler([1, 1, 2, 2, 3, 3])
assert solution.numberOfCategories(6, handler) == 3  # three groups

# Example 2
handler = MockCategoryHandler([1, 2, 3, 4, 5])
assert solution.numberOfCategories(5, handler) == 5  # all unique

# Example 3
handler = MockCategoryHandler([1, 1, 1])
assert solution.numberOfCategories(3, handler) == 1  # all same

# Single element
handler = MockCategoryHandler([7])
assert solution.numberOfCategories(1, handler) == 1  # minimum input size

# Two identical elements
handler = MockCategoryHandler([4, 4])
assert solution.numberOfCategories(2, handler) == 1  # single category

# Two different elements
handler = MockCategoryHandler([4, 5])
assert solution.numberOfCategories(2, handler) == 2  # distinct categories

# Mixed grouping
handler = MockCategoryHandler([1, 2, 1, 3, 2, 3])
assert solution.numberOfCategories(6, handler) == 3  # interleaved groups

# Larger repeated groups
handler = MockCategoryHandler([1,1,1,2,2,3,3,3,3])
assert solution.numberOfCategories(9, handler) == 3  # uneven group sizes

# Every element unique
handler = MockCategoryHandler(list(range(100)))
assert solution.numberOfCategories(100, handler) == 100  # worst-case categories

# All elements same
handler = MockCategoryHandler([1] * 100)
assert solution.numberOfCategories(100, handler) == 1  # maximum merging
Test Why
[1,1,2,2,3,3] Validates multiple equal-sized groups
[1,2,3,4,5] Validates all unique categories
[1,1,1] Validates complete merging
[7] Tests minimum input size
[4,4] Tests smallest non-trivial merge
[4,5] Tests smallest distinct case
[1,2,1,3,2,3] Tests interleaved category structure
[1,1,1,2,2,3,3,3,3] Tests uneven component sizes
range(100) Tests maximum distinct groups
[1] * 100 Tests maximum connectivity

Edge Cases

All Elements Belong to Different Categories

In this scenario, every call to haveSameCategory(i, j) returns false.

A buggy implementation might accidentally merge unrelated elements or incorrectly initialize the Union-Find structure.

The current implementation handles this correctly because unions occur only when the API explicitly reports equality. Every element remains its own root, producing an answer of n.

All Elements Belong to One Category

When every element belongs to the same category, nearly every comparison returns true.

An incorrect implementation could repeatedly merge already-connected components inefficiently or corrupt parent relationships.

The Union-Find implementation avoids this issue because it first checks whether two roots are already equal before merging. This keeps the structure valid and efficient.

Single Element Input

When n = 1, there are no pairs to compare.

A naive implementation might incorrectly return 0 because no unions occur.

The current solution initializes the single element as its own component, and the final root-counting step correctly returns 1.