Group Anagrams Using Hash Map in DSA Python - Execution Trace

Concept Flow - Group Anagrams Using Hash Map

Start with list of words

↓

For each word: Sort letters to form key

↓

Check if key in hash map?

No→Create new list for key

↓

Add word to list

↓

Add word to existing list for key

↓

After all words processed

↓

Return all grouped anagrams as lists

We take each word, sort its letters to get a key, then group words with the same key together in a hash map.

Execution Sample

DSA Python

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

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

Execution Table

Step	Operation	Current Word	Key (Sorted Letters)	Hash Map State	Visual State
1	Process word	eat	aet	{"aet": ["eat"]}	[aet] -> ["eat"]
2	Process word	tea	aet	{"aet": ["eat", "tea"]}	[aet] -> ["eat", "tea"]
3	Process word	tan	ant	{"aet": ["eat", "tea"], "ant": ["tan"]}	[aet] -> ["eat", "tea"] [ant] -> ["tan"]
4	Process word	ate	aet	{"aet": ["eat", "tea", "ate"], "ant": ["tan"]}	[aet] -> ["eat", "tea", "ate"] [ant] -> ["tan"]
5	Process word	nat	ant	{"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"]}	[aet] -> ["eat", "tea", "ate"] [ant] -> ["tan", "nat"]
6	Process word	bat	abt	{"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"]}	[aet] -> ["eat", "tea", "ate"] [ant] -> ["tan", "nat"] [abt] -> ["bat"]
7	Return grouped anagrams	-	-	[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]	Groups: ["eat", "tea", "ate"], ["tan", "nat"], ["bat"]

💡 All words processed and grouped by their sorted letter keys.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	Final
words	["eat", "tea", "tan", "ate", "nat", "bat"]	["eat", "tea", "tan", "ate", "nat", "bat"]	["eat", "tea", "tan", "ate", "nat", "bat"]	["eat", "tea", "tan", "ate", "nat", "bat"]	["eat", "tea", "tan", "ate", "nat", "bat"]	["eat", "tea", "tan", "ate", "nat", "bat"]	["eat", "tea", "tan", "ate", "nat", "bat"]	["eat", "tea", "tan", "ate", "nat", "bat"]
key	-	aet	aet	ant	aet	ant	abt	-
result	{}	{"aet": ["eat"]}	{"aet": ["eat", "tea"]}	{"aet": ["eat", "tea"], "ant": ["tan"]}	{"aet": ["eat", "tea", "ate"], "ant": ["tan"]}	{"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"]}	{"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"]}	{"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"]}

Key Moments - 3 Insights

Why do we sort the letters of each word before using it as a key?

Sorting letters creates a unique key for all anagrams because anagrams have the same letters in different orders. This is shown in execution_table rows 1, 2, and 3 where different words like 'eat' and 'tea' share the same key 'aet'.

What happens if a key is not already in the hash map?

If the key is not in the hash map, a new list is created for that key before adding the word. This is shown in execution_table row 1 where 'aet' key is created for 'eat', and row 3 where 'ant' key is created for 'tan'.

How do we know when all words have been grouped?

When the loop finishes processing all words, the hash map contains all groups. This is shown in execution_table row 7 where the final grouped anagrams are returned.

Visual Quiz - 3 Questions

Look at the execution_table at step 4. What is the hash map state after processing the word 'ate'?

A {"aet": ["ate"], "ant": ["tan"]}

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

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

D {"aet": ["eat", "tea"], "ant": ["tan"]}

💡 Hint

Check execution_table row 4 under 'Hash Map State' to see the exact state after 'ate' is processed.

At which step does the key 'abt' first appear in the hash map?

A Step 6

B Step 3

C Step 5

D Step 7

💡 Hint

Look at the 'Key (Sorted Letters)' and 'Hash Map State' columns in execution_table to find when 'abt' is added.

If the word 'tab' was added after 'bat', how would the hash map change?

A A new key 'abt' with ['bat', 'tab'] would be created.

B 'tab' would be added to the existing list under key 'abt'.

C 'tab' would create a new key 'tab' separate from 'abt'.

D 'tab' would replace 'bat' in the list under key 'abt'.

💡 Hint

Recall that sorted letters are used as keys; 'bat' and 'tab' have the same sorted key 'abt'.

Concept Snapshot

Group Anagrams Using Hash Map:
- Sort letters of each word to create a key.
- Use the key in a hash map to group words.
- If key not present, create new list.
- Append word to list for that key.
- Return all grouped lists after processing all words.

Full Transcript

To group anagrams, we take each word and sort its letters to form a key. This key is the same for all anagrams. We use a hash map where keys are these sorted strings and values are lists of words matching that key. For each word, we check if the key exists in the map. If not, we create a new list. Then we add the word to the list. After processing all words, the hash map contains groups of anagrams. For example, 'eat', 'tea', and 'ate' all have the key 'aet' and are grouped together. This method efficiently groups anagrams by leveraging sorted keys and hash map lookups.