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.

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