Number of Unique Categories - Practice Coding Problems

Number of Unique Categories - Problem

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:

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 n or less than 0), it returns false.

Return the number of unique categories.

Input & Output

Example 1 — Basic Case

$ Input: n = 6, categories = [0, 1, 2, 0, 1, 2]

› Output: 3

💡 Note: Elements 0,3 are in category 0; elements 1,4 are in category 1; elements 2,5 are in category 2. Total unique categories = 3.

Example 2 — All Same Category

$ Input: n = 4, categories = [1, 1, 1, 1]

› Output: 1

💡 Note: All elements 0,1,2,3 belong to the same category 1. Total unique categories = 1.

Example 3 — All Different Categories

$ Input: n = 3, categories = [0, 1, 2]

› Output: 3

💡 Note: Each element is in a different category: 0→category 0, 1→category 1, 2→category 2. Total unique categories = 3.

Constraints

1 ≤ n ≤ 1000
0 ≤ element_id < n
CategoryHandler.haveSameCategory() returns boolean

Visualization

Tap to expand

Understanding the Visualization

Input

n elements numbered 0 to n-1, each with a hidden category

Process

Use haveSameCategory() to find which elements belong together

Output

Count the number of distinct category groups

Key Takeaway

🎯 Key Insight: This is a graph connectivity problem where elements in the same category form connected components

Asked in

G Google 12 f Facebook 8 a Amazon 6 M Microsoft 4

The key insight is to recognize this as a connected components problem. Use either DFS to explore each component or Union-Find to efficiently group elements. Best approach is Union-Find for its clean structure. Time: O(n² × α(n)), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Union-Find (Disjoint Set Union)	O(n² × α(n))	O(n)	Use Union-Find data structure to efficiently group elements and count unique components
Brute Force with Visited Tracking	O(n²)	O(n)	For each unvisited element, explore all elements it connects to using DFS

Union-Find (Disjoint Set Union) — Algorithm Steps

Initialize Union-Find with n elements
Compare all pairs and union elements in same category
Count distinct root parents to get unique categories

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Each element is its own parent

Union

Merge elements with same category

Count

Count distinct root parents

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct {
    int* categories;
    int size;
} CategoryHandler;

bool haveSameCategory(CategoryHandler* handler, int a, int b) {
    if (a < 0 || a >= handler->size || b < 0 || b >= handler->size) {
        return false;
    }
    return handler->categories[a] == handler->categories[b];
}

typedef struct {
    int* parent;
    int* rank;
    int size;
} UnionFind;

UnionFind* createUnionFind(int n) {
    UnionFind* uf = (UnionFind*)malloc(sizeof(UnionFind));
    uf->parent = (int*)malloc(n * sizeof(int));
    uf->rank = (int*)calloc(n, sizeof(int));
    uf->size = n;
    for (int i = 0; i < n; i++) {
        uf->parent[i] = i;
    }
    return uf;
}

int find(UnionFind* uf, int x) {
    if (uf->parent[x] != x) {
        uf->parent[x] = find(uf, uf->parent[x]);
    }
    return uf->parent[x];
}

void unionSets(UnionFind* uf, int x, int y) {
    int px = find(uf, x);
    int py = find(uf, y);
    if (px == py) return;
    
    if (uf->rank[px] < uf->rank[py]) {
        uf->parent[px] = py;
    } else if (uf->rank[px] > uf->rank[py]) {
        uf->parent[py] = px;
    } else {
        uf->parent[py] = px;
        uf->rank[px]++;
    }
}

int countComponents(UnionFind* uf) {
    bool* isRoot = (bool*)calloc(uf->size, sizeof(bool));
    int count = 0;
    for (int i = 0; i < uf->size; i++) {
        int root = find(uf, i);
        if (!isRoot[root]) {
            isRoot[root] = true;
            count++;
        }
    }
    free(isRoot);
    return count;
}

int solution(int n) {
    // For testing purposes, create a sample CategoryHandler
    CategoryHandler handler;
    handler.categories = (int*)malloc(n * sizeof(int));
    handler.size = n;
    for (int i = 0; i < n; i++) {
        handler.categories[i] = i % 3;
    }
    
    UnionFind* uf = createUnionFind(n);
    
    // Check all pairs and union elements in same category
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (haveSameCategory(&handler, i, j)) {
                unionSets(uf, i, j);
            }
        }
    }
    
    int result = countComponents(uf);
    
    free(handler.categories);
    free(uf->parent);
    free(uf->rank);
    free(uf);
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", solution(n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × α(n))

n² pairs to check, each union/find operation takes α(n) amortized time where α is inverse Ackermann

⚠ Quadratic Growth

Space Complexity

O(n)

Union-Find parent and rank arrays of size n

⚡ Linearithmic Space

12.3K Views

Medium Frequency

~25 min Avg. Time

456 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Union-Find (Disjoint Set Union) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler