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.