Group Anagrams Using Hash Map in DSA C - Execution Trace

Concept Flow - Group Anagrams Using Hash Map

Start with list of words

↓

For each word: Sort letters

↓

Use sorted word as key in hash map

↓

If key exists: Append original word to list

↓

If key not exists: Create new list with word

↓

Repeat for all words

↓

Return all lists of grouped anagrams

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

Execution Sample

DSA C

words = ["eat", "tea", "tan", "ate", "nat", "bat"];
for each word:
  sorted_word = sort_letters(word);
  hashmap[sorted_word].append(word);
return hashmap.values();

Groups words by their sorted letter form using a hash map.

Execution Table

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

💡 All words processed and grouped by sorted keys in hash map.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	Final
Current Word	-	eat	tea	tan	ate	nat	bat	-
Sorted Key	-	aet	aet	ant	aet	ant	abt	-
Hash Map	{}	{"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"]}	Groups returned

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. For example, 'eat', 'tea', and 'ate' all become 'aet'. This groups them together in the hash map as shown in steps 1, 2, and 4 in the execution table.

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

A new list is created for that key and the current word is added. This is shown in step 3 when 'ant' key is created for 'tan'.

How does the hash map store multiple words for the same key?

It stores a list of words. Each time a word with the same sorted key is found, it appends to the list. See steps 2 and 5 where words are appended to the 'aet' and 'ant' keys.

Visual Quiz - 3 Questions

Look at the execution table, what is the hash map state after processing the word 'ate'?

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

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

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

D {"aet": ["eat", "tea", "ate"], "abt": ["bat"]}

💡 Hint

Check step 4 in the execution table for the hash map state after 'ate' is processed.

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

A Step 5

B Step 6

C Step 4

D Step 7

💡 Hint

Look at the 'Sorted Key' and 'Hash Map State' columns in the execution table.

If the word 'bat' was processed first, how would the hash map state after step 1 change?

A {"abt": ["bat"]}

B {"aet": ["bat"]}

C {"bat": ["bat"]}

D {}

💡 Hint

The sorted key for 'bat' is 'abt', check how keys are formed in the execution table.

Concept Snapshot

Group Anagrams Using Hash Map:
- Sort letters of each word to create a key.
- Use key in hash map to group words.
- Append words to list if key exists.
- Create new list if key not found.
- Return all grouped lists as result.

Full Transcript

This concept groups words that are anagrams by sorting their letters to create a key. Each word is processed by sorting its letters, then using this sorted string as a key in a hash map. If the key exists, the word is appended to the list for that key. If not, a new list is created. This groups all anagrams together. The execution table shows step-by-step how words are added and how the hash map changes. Key moments clarify why sorting is needed and how the hash map stores groups. The visual quiz tests understanding of the hash map state at different steps. The snapshot summarizes the process in simple steps.

Practice

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

easy

A. Use the length of words as keys to group anagrams

B. Store words in a list without any sorting or grouping

C. Group words by their first character only

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

Solution

1. Step 1: Understand anagrams and their properties

   Anagrams are words made of the same letters in any order, so sorting letters gives a unique key for each group.

2. Step 2: Use sorted strings as hash map keys

   By sorting each word and using it as a key, all anagrams map to the same key and can be grouped together.

3. Final Answer:

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

4. Quick Check:

   Sorted word keys group anagrams [OK]

Hint: Sort each word and use as key to group anagrams [OK]

Common Mistakes:

• Grouping by word length only
• Using first character as key
• Not sorting words before grouping

2. Which of the following is the correct way to declare a hash map (dictionary) in C for grouping anagrams?

easy

A. map anagramGroups;

B. unordered_map anagramGroups;

C. unordered_map anagramGroups;

D. vector<string> anagramGroups;

Solution

1. Step 1: Identify the data types needed for grouping anagrams

   We need a map from a string key (sorted word) to a list of strings (anagrams).

2. Step 2: Choose the correct C++ STL container

   unordered_map fits this need perfectly.

3. Final Answer:

   unordered_map anagramGroups; -> Option B

4. Quick Check:

   Map from string to vector<string> groups anagrams [OK]

Hint: Use unordered_map for grouping anagrams [OK]

Common Mistakes:

• Using map which mismatches key and value types
• Using vector<string> alone without mapping keys
• Using unordered_map which is unrelated

3. What is the output of the following C++ code snippet? vector<string> words = {"eat", "tea", "tan", "ate", "nat", "bat"}; unordered_map groups; for (auto &word : words) { string sortedWord = word; sort(sortedWord.begin(), sortedWord.end()); groups[sortedWord].push_back(word); } for (auto &pair : groups) { sort(pair.second.begin(), pair.second.end()); for (auto &w : pair.second) cout << w << " "; cout << endl; }

medium

A. bat
nat tan
eat tea ate

B. eat tea ate
bat
tan nat

C. tea ate eat
bat
tan nat

D. ate eat tea
bat
nat tan

Solution

1. Step 1: Group words by sorted keys

   Words "eat", "tea", "ate" all sort to "aet" and group together; "tan", "nat" to "ant"; "bat" to "abt".

2. Step 2: Sort each group and print

   Each group is sorted alphabetically before printing: "ate eat tea", "bat", "nat tan".

3. Final Answer:

   bat nat tan eat tea ate -> Option A

4. Quick Check:

   Sorted keys group anagrams; groups sorted before print [OK]

Hint: Sort words and groups before printing for consistent output [OK]

Common Mistakes:

• Not sorting groups before printing
• Printing groups in wrong order
• Confusing sorted keys with original words

4. Identify the bug in this C++ code for grouping anagrams: vector<string> words = {"abc", "bca", "cab"}; unordered_map groups; for (auto word : words) { string key = word; sort(word.begin(), word.end()); groups[key].push_back(word); }

medium

A. Sorting is done on 'word' but key uses unsorted string

B. Using unordered_map instead of map causes error

C. Loop variable should be reference to avoid copies

D. Missing initialization of groups map

Solution

1. Step 1: Check how key and sorted string are assigned

   Key is assigned before sorting, so key is unsorted original word.

2. Step 2: Sorting is done on 'word' but key remains unsorted

   Groups use unsorted key, so anagrams won't group correctly.

3. Final Answer:

   Sorting is done on 'word' but key uses unsorted string -> Option A

4. Quick Check:

   Key must be sorted string for correct grouping [OK]

Hint: Sort string before assigning key for hash map [OK]

Common Mistakes:

• Assigning key before sorting
• Sorting wrong variable
• Not using reference in loop (less critical here)

5. Given a list of words, how can you modify the hash map grouping approach to handle case-insensitive anagrams (e.g., "Eat" and "tea" grouped together)?

hard

A. Group words by their first letter ignoring case

B. Use word length as key instead of sorted string

C. Convert all words to lowercase before sorting and grouping

D. Sort words without changing case and group normally

Solution

1. Step 1: Understand case-insensitive grouping

   "Eat" and "tea" differ in case but are anagrams ignoring case.

2. Step 2: Normalize words by converting to lowercase before sorting

   This ensures keys match regardless of original case.

3. Final Answer:

   Convert all words to lowercase before sorting and grouping -> Option C

4. Quick Check:

   Lowercase normalization groups case-insensitive anagrams [OK]

Hint: Lowercase words before sorting to group case-insensitive anagrams [OK]

Common Mistakes:

• Grouping by length only
• Ignoring case normalization
• Sorting without case conversion