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

Time Complexity: Group Anagrams Using Hash Map

O(n x 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 program's work increase when we add more words or longer words?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from collections import defaultdict

def group_anagrams(words):
    anagrams = defaultdict(list)
    for word in words:
        sorted_word = ''.join(sorted(word))
        anagrams[sorted_word].append(word)
    return list(anagrams.values())

This code groups words that are anagrams by sorting each word and using the sorted word as a key in a hash map.

Identify Repeating Operations

• Primary operation: Looping over each word and sorting each word.
• How many times: The loop runs once for every word (n times), and sorting runs once per word on its length (k times).

How Execution Grows With Input

As the number of words (n) grows, the program sorts each word of length (k) every time.

Input Size (n)	Approx. Operations
10 (words)	10 x sorting each word (k log k)
100 (words)	100 x sorting each word (k log k)
1000 (words)	1000 x sorting each word (k log k)

Pattern observation: The work grows linearly with the number of words, and sorting each word depends on its length.

Final Time Complexity

Time Complexity: O(n x k log k)

This means the time grows linearly with the number of words and depends on sorting each word's letters.

Common Mistake

[X] Wrong: "Sorting all words is just O(n) because we only loop once."

[OK] Correct: Sorting each word takes extra time depending on word length, so total time depends on both number of words and their length.

Interview Connect

Understanding this time complexity helps you explain how your solution scales with input size, a key skill in interviews.

Self-Check

"What if we used character count arrays instead of sorting each word? How would the time complexity change?"