We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Unique Categories

Number: 2995

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

You are given an integer n and an object categoryHandler of class CategoryHandler. There are n elements (numbered 0 to n - 1) where each element belongs to a category. Using the provided function haveSameCategory(a, b) from categoryHandler, determine the number of unique categories among the elements.

Key Insights

  • The only way to compare two elements' categories is via the function haveSameCategory.
  • A straightforward approach is to group elements together using pairwise comparisons.
  • Using a Union-Find (disjoint-set) data structure helps in efficiently grouping elements that belong to the same category.
  • Given n is small (n <= 100), an O(n^2) solution is acceptable.

Space and Time Complexity

Time Complexity: O(n^2) – Each pair of elements may be compared in the worst case. Space Complexity: O(n) – To store the union-find parent (and optionally rank) arrays.

Solution

We use the Union-Find (disjoint-set) data structure to solve the problem. Initially, each element is its own set. We then iterate over every pair of elements (i, j). If categoryHandler.haveSameCategory(i, j) returns true, we union their sets. After processing all possible pairs, the number of unique categories is equal to the number of unique representative parents across all elements. Special care is taken to ensure that every union operation is done via a find function with path compression to keep the tree flat and union-by-rank if desired (though rank is optional for n up to 100).

Code Solutions

# Python Code

class UnionFind:
    def __init__(self, n):
        # Initialize the parent list where each element is its own parent.
        self.parent = [i for i in range(n)]
        
    def find(self, x):
        # Recursively find the root with path compression.
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        # Union the sets of x and y.
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            self.parent[rootY] = rootX

def countUniqueCategories(n, categoryHandler):
    # Create a UnionFind instance for n elements.
    uf = UnionFind(n)
    
    # Compare each pair only once
    for i in range(n):
        for j in range(i + 1, n):
            # If elements i and j are in the same category, union them
            if categoryHandler.haveSameCategory(i, j):
                uf.union(i, j)
    
    # Use a set to count unique parent (representative) for each element.
    unique_categories = set()
    for i in range(n):
        unique_categories.add(uf.find(i))
    
    return len(unique_categories)

# Example: to test, you would need to implement or mock the CategoryHandler class.
← Back to All Questions