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?"

Practice

1. What is the main idea behind grouping anagrams using a hash map?

easy

A. Use the first character of the string as the key

B. Use the length of the string as the key

C. Use sorted strings as keys to group words with the same letters

D. Use the last character of the string as the key

Solution

1. Step 1: Understand anagrams

   Anagrams are words with the same letters in different orders.

2. Step 2: Use sorted strings as keys

   Sorting letters of each word gives a common key for all anagrams.

3. Final Answer:

   Use sorted strings as keys to group words with the same letters -> Option C

4. Quick Check:

   Sorted string key groups anagrams = C [OK]

Hint: Sort each word to find its anagram group key [OK]

Common Mistakes:

• Using string length as key groups wrong words
• Using first or last character misses many anagrams
• Not sorting letters before using as key

2. Which of the following Python code snippets correctly initializes an empty hash map (dictionary) to group anagrams?

easy

A. anagrams = {}

B. anagrams = ()

C. anagrams = set()

D. anagrams = []

Solution

1. Step 1: Identify dictionary initialization

   In Python, an empty dictionary is created with curly braces {}.

2. Step 2: Check other options

   List uses [], set uses set(), tuple uses (). Only {} is dictionary.

3. Final Answer:

   anagrams = {} -> Option A

4. Quick Check:

   Empty dictionary = {} [OK]

Hint: Use {} to create an empty dictionary in Python [OK]

Common Mistakes:

• Using [] which creates a list, not a dictionary
• Using set() which creates a set, not a dictionary
• Using () which creates a tuple, not a dictionary

3. What is the output of the following code?

words = ["eat", "tea", "tan", "ate", "nat", "bat"]
anagrams = {}
for word in words:
    key = ''.join(sorted(word))
    if key not in anagrams:
        anagrams[key] = []
    anagrams[key].append(word)
print(list(anagrams.values()))

medium

A. [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

B. [['eat', 'tea'], ['tan', 'nat'], ['bat', 'ate']]

C. [['eat', 'ate'], ['tan', 'nat'], ['bat', 'tea']]

D. [['eat'], ['tea'], ['tan'], ['ate'], ['nat'], ['bat']]

Solution

1. Step 1: Sort each word and group

   Words "eat", "tea", "ate" sorted become "aet"; grouped together. "tan", "nat" sorted "ant"; grouped. "bat" sorted "abt"; alone.

2. Step 2: Collect groups in dictionary values

   Values are lists of grouped anagrams: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

3. Final Answer:

   [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']] -> Option A

4. Quick Check:

   Sorted keys group words correctly = A [OK]

Hint: Sort letters, use as key, group words in list [OK]

Common Mistakes:

• Appending words to wrong keys
• Not sorting words before grouping
• Mixing groups or missing words

4. Find the error in this code that tries to group anagrams:

words = ["abc", "bca", "cab"]
anagrams = {}
for word in words:
    key = sorted(word)
    if key not in anagrams:
        anagrams[key] = []
    anagrams[key].append(word)
print(anagrams)

medium

A. The dictionary is not initialized correctly

B. The print statement syntax is wrong

C. The append method is used incorrectly

D. sorted(word) returns a list, which cannot be used as a dictionary key

Solution

1. Step 1: Check key type used in dictionary

   sorted(word) returns a list, but lists are not hashable and cannot be dictionary keys.

2. Step 2: Fix by converting list to string or tuple

   Use key = ''.join(sorted(word)) or key = tuple(sorted(word)) to make hashable key.

3. Final Answer:

   sorted(word) returns a list, which cannot be used as a dictionary key -> Option D

4. Quick Check:

   Dictionary keys must be hashable, list is not [OK]

Hint: Convert sorted list to string or tuple before using as key [OK]

Common Mistakes:

• Using list as dictionary key causes TypeError
• Not converting sorted result to string or tuple
• Ignoring error messages about unhashable types

5. Given the list words = ["listen", "silent", "enlist", "google", "gogole", "abc"], which code snippet correctly groups the anagrams and returns the groups sorted alphabetically by their first word?

hard

A. anagrams = {}
for w in words:
key = w
anagrams[key] = w
print(list(anagrams.values()))

B. anagrams = {}
for w in words:
key = ''.join(sorted(w))
anagrams.setdefault(key, []).append(w)
groups = list(anagrams.values())
groups.sort(key=lambda x: x[0])
print(groups)

C. anagrams = {}
for w in words:
key = ''.join(sorted(w))
anagrams[key] = w
print(list(anagrams.keys()))

D. anagrams = []
for w in words:
anagrams.append(sorted(w))
print(anagrams)

Solution

1. Step 1: Group words by sorted key using dictionary

   anagrams = {} for w in words: key = ''.join(sorted(w)) anagrams.setdefault(key, []).append(w) groups = list(anagrams.values()) groups.sort(key=lambda x: x[0]) print(groups) uses sorted word as key and appends words to list correctly.

2. Step 2: Sort groups by first word

   anagrams = {} for w in words: key = ''.join(sorted(w)) anagrams.setdefault(key, []).append(w) groups = list(anagrams.values()) groups.sort(key=lambda x: x[0]) print(groups) sorts the list of groups by the first word in each group, meeting requirement.

3. Final Answer:

   Correctly groups anagrams using sorted keys, setdefault, append, and sorts groups by first word -> Option B

4. Quick Check:

   Group by sorted key + sort groups by first word = A [OK]

Hint: Use setdefault for grouping and sort groups by first element [OK]

Common Mistakes:

• Using word itself as key loses grouping
• Overwriting dictionary values instead of appending
• Using list instead of dictionary for grouping