Group Anagrams Using Hash Map in DSA Python

Mental Model

Group words that have the same letters by sorting their letters and using that as a key.

Analogy: Imagine sorting letters of each word like putting puzzle pieces in order; words with the same pieces fit into the same box.

words: [eat, tea, tan, ate, nat, bat]
keys:  [aet, aet, ant, aet, ant, abt]

Hash Map:
{
  'aet' -> [eat, tea, ate]
  'ant' -> [tan, nat]
  'abt' -> [bat]
}

Dry Run Walkthrough

Input: words: [eat, tea, tan, ate, nat, bat]

Goal: Group words that are anagrams together in lists

Step 1: Take 'eat', sort letters to get 'aet', add 'eat' to group with key 'aet'

{'aet': ['eat']}

Why: Sorting letters creates a unique key for anagrams

Step 2: Take 'tea', sort letters to get 'aet', add 'tea' to group with key 'aet'

{'aet': ['eat', 'tea']}

Why: Words with same sorted letters belong to same group

Step 3: Take 'tan', sort letters to get 'ant', add 'tan' to group with key 'ant'

{'aet': ['eat', 'tea'], 'ant': ['tan']}

Why: New key means new group

Step 4: Take 'ate', sort letters to get 'aet', add 'ate' to group with key 'aet'

{'aet': ['eat', 'tea', 'ate'], 'ant': ['tan']}

Why: Add to existing group for anagrams

Step 5: Take 'nat', sort letters to get 'ant', add 'nat' to group with key 'ant'

{'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat']}

Why: Add to existing group for anagrams

Step 6: Take 'bat', sort letters to get 'abt', add 'bat' to group with key 'abt'

{'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat']}

Why: New key means new group

Result:

Groups:
['eat', 'tea', 'ate']
['tan', 'nat']
['bat']

Annotated Code

DSA Python

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)  # create map from sorted word to list
    for word in words:
        sorted_word = ''.join(sorted(word))  # sort letters to form key
        groups[sorted_word].append(word)  # add word to correct group
    return list(groups.values())

# driver code
words = ["eat", "tea", "tan", "ate", "nat", "bat"]
groups = group_anagrams(words)
for group in groups:
    print(group)

groups = defaultdict(list) # create map from sorted word to list

initialize hash map to hold groups of anagrams

for word in words:

iterate over each word to process

sorted_word = ''.join(sorted(word)) # sort letters to form key

create key by sorting letters of word

groups[sorted_word].append(word) # add word to correct group

append word to its anagram group in map

return list(groups.values())

return all grouped anagrams as list of lists

Output

['eat', 'tea', 'ate']

['tan', 'nat']

['bat']

Complexity Analysis

Time: O(n * k log k) because we sort each of the n words of length k

Space: O(n * k) because we store all words grouped in the hash map

vs Alternative: Compared to checking every pair for anagram (O(n^2 * k)), this is much faster using hashing

Edge Cases

empty list

returns empty list without error

DSA Python

for word in words:

list with one word

returns list with one group containing that word

DSA Python

for word in words:

words with different lengths

groups only words with same letters and length together correctly

DSA Python

sorted_word = ''.join(sorted(word))

When to Use This Pattern

When you need to group words that are rearrangements of each other, use sorting as a key in a hash map to group anagrams efficiently.

Common Mistakes

Mistake: Using the original word as key instead of sorted letters
Fix: Sort the letters of the word before using it as a key

Mistake: Not using a list to store multiple words per key
Fix: Use a list or collection to hold all words that share the same sorted key

Summary

Groups words that are anagrams by sorting letters and using a hash map.

Use when you want to collect all words that have the same letters together.

Sorting letters creates a unique key that identifies anagram groups.