Group Anagrams Using Hash Map in DSA C - Time & Space Complexity

Time Complexity: Group Anagrams Using Hash Map

O(n * k log k)

Understanding Time Complexity

We want to understand how the time needed to group anagrams grows as the list of words gets bigger.

Specifically, how does the code handle checking and grouping words that are anagrams?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void groupAnagrams(char* strs[], int strsSize) {
    // Create a hash map to group anagrams
    for (int i = 0; i < strsSize; i++) {
        char key[100];
        strcpy(key, strs[i]);
        qsort(key, strlen(key), sizeof(char), cmpChar); // sort characters in the string
        hashmapInsert(key, strs[i]);
    }
    // Output groups from hashmap
}
    

This code groups words by sorting each word's letters and using the sorted word as a key in a hash map.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting each word's characters inside the loop.
• How many times: Once for each word in the list (strsSize times).

How Execution Grows With Input

As the number of words grows, the code sorts each word, so the time grows with both the number of words and their length.

Input Size (n)	Approx. Operations
10 words	10 × sorting each word (depends on word length)
100 words	100 × sorting each word
1000 words	1000 × sorting each word

Pattern observation: The total work grows linearly with the number of words, but sorting each word adds extra cost depending on word length.

Final Time Complexity

Time Complexity: O(n * k log k)

This means the time grows with the number of words (n) times the cost to sort each word of length k.

Common Mistake

[X] Wrong: "Sorting all words is just O(n) because we do it once per word."

[OK] Correct: Sorting each word takes time depending on its length (k log k), so total time depends on both number of words and word length.

Interview Connect

Understanding how sorting inside loops affects time helps you explain your solution clearly and shows you know how to analyze code performance.

Self-Check

"What if we used counting sort for each word instead of general sorting? How would the time complexity change?"