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 of word

↓

Use sorted word as key in hash map

↓

Add original word to hash map[key

↓

After all words processed

↓

Collect all hash map values as groups

↓

Return grouped anagrams

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

Execution Sample

DSA C++

vector<vector<string>> groupAnagrams(vector<string>& strs) {
  unordered_map<string, vector<string>> map;
  for (auto& s : strs) {
    string key = s; sort(key.begin(), key.end());
    map[key].push_back(s);
  }
  vector<vector<string>> result;
  for (auto& p : map) result.push_back(p.second);
  return result;
}

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

Execution Table

Step	Operation	Current Word	Sorted Key	Hash Map State	Visual State
1	Start	-	-	{}	Empty map
2	Process word	eat	aet	{"aet": ["eat"]}	aet -> [eat]
3	Process word	tea	aet	{"aet": ["eat", "tea"]}	aet -> [eat, tea]
4	Process word	tan	ant	{"aet": ["eat", "tea"], "ant": ["tan"]}	aet -> [eat, tea], ant -> [tan]
5	Process word	ate	aet	{"aet": ["eat", "tea", "ate"], "ant": ["tan"]}	aet -> [eat, tea, ate], ant -> [tan]
6	Process word	nat	ant	{"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"]}	aet -> [eat, tea, ate], ant -> [tan, nat]
7	Process word	bat	abt	{"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"]}	aet -> [eat, tea, ate], ant -> [tan, nat], abt -> [bat]
8	Collect groups	-	-	[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]	Groups: 3 arrays
9	Return result	-	-	[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]	Final grouped anagrams
10	End	-	-	-	All words processed and grouped

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

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	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"]}	-	{"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"]}
Result Groups	[]	[]	[]	[]	[]	[]	[]	[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]	[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Key Moments - 3 Insights

Why do we sort the word before using it as a key in the hash map?

Sorting the word creates a unique key for all anagrams because anagrams have the same letters in different orders. This is shown in steps 2-7 in the execution_table where different words like 'eat', 'tea', and 'ate' share the same sorted key 'aet'.

What happens if two words are not anagrams? How are they stored?

Words that are not anagrams have different sorted keys, so they are stored in separate groups in the hash map. For example, 'bat' has key 'abt' which is different from 'aet' or 'ant', so it forms its own group as seen in step 7.

Why do we collect the values of the hash map at the end?

The hash map keys are sorted words, but the original words are stored as values. Collecting the values gives us the groups of anagrams without the sorted keys, as shown in step 8 and 9.

Visual Quiz - 3 Questions

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

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

B {"aet": ["eat"], "tan": ["tan"]}

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

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

💡 Hint

Check the 'Hash Map State' column in row 4 of the execution_table.

At which step does the word 'bat' get added to the hash map?

A Step 5

B Step 7

C Step 6

D Step 8

💡 Hint

Look for the step where the current word is 'bat' in the execution_table.

If the word 'tab' was added after 'bat', what would be the hash map state for key 'abt'?

A ["bat", "tab"]

B ["bat"]

C ["tab"]

D ["bat", "tan"]

💡 Hint

Words 'bat' and 'tab' are anagrams and share the same sorted key 'abt'.

Concept Snapshot

Group Anagrams Using Hash Map:
- Sort each word's letters to create a key.
- Use the sorted word as key in a hash map.
- Append original words to the list at that key.
- After processing all words, collect all lists as groups.
- Returns groups of anagrams together.

Full Transcript

This concept groups words that are anagrams by sorting each word to create a key. We use a hash map where the key is the sorted word and the value is a list of original words matching that key. We process each word by sorting it, then adding it to the hash map under the sorted key. After all words are processed, we collect all the lists from the hash map to get groups of anagrams. The execution table shows each step adding words and updating the map. The variable tracker shows how the current word, sorted key, and hash map change after each step. Key moments clarify why sorting is needed, how non-anagrams are stored separately, and why we collect values at the end. The visual quiz tests understanding of the hash map state at different steps and how new words affect groups.

Practice

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

easy

A. Use sorted strings as keys to group words with the same characters

B. Use the length of the string as the key to group words

C. Use the first character of the string as the key

D. Use the last character of the string as the key

Solution

1. Step 1: Understand anagram grouping

   Anagrams have the same characters in different orders, so sorting the string gives a unique key for all anagrams.

2. Step 2: Use sorted string as hash map key

   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 characters -> Option A

4. Quick Check:

   Sorted string key = group anagrams [OK]

Hint: Sort each word to find its anagram group key [OK]

Common Mistakes:

• Using string length as key misses different anagrams
• Using first or last character groups unrelated words
• Not sorting strings before using as keys

2. Which of the following C++ code snippets correctly declares a hash map to group anagrams where the key is a string and the value is a vector of strings?

easy

A. std::unordered_map anagramGroups;

B. std::map> anagramGroups;

C. std::unordered_map> anagramGroups;

D. std::unordered_map anagramGroups;

Solution

1. Step 1: Identify key and value types

   The key should be a string (sorted word), and the value should be a vector of strings (group of anagrams).

2. Step 2: Match correct declaration

   std::unordered_map> anagramGroups; uses unordered_map with key as string and value as vector<string>, which is correct for grouping anagrams.

3. Final Answer:

   std::unordered_map> anagramGroups; -> Option C

4. Quick Check:

   Key=string, Value=vector<string> [OK]

Hint: Use unordered_map for grouping [OK]

Common Mistakes:

• Using int as key instead of string
• Using vector<char> as key (not hashable)
• Using string as value instead of vector<string>

3. What is the output of the following C++ code snippet?

std::vector words = {"eat", "tea", "tan", "ate", "nat", "bat"};
std::unordered_map> groups;
for (auto &word : words) {
    std::string sortedWord = word;
    std::sort(sortedWord.begin(), sortedWord.end());
    groups[sortedWord].push_back(word);
}
for (auto &pair : groups) {
    std::cout << "Group: ";
    for (auto &w : pair.second) std::cout << w << " ";
    std::cout << std::endl;
}

medium

A. Group: eat tea
Group: tan bat
Group: ate nat

B. Group: eat tea ate
Group: tan nat
Group: bat

C. Group: ate tea
Group: bat tan
Group: eat nat

D. Group: eat tan bat
Group: tea nat ate

Solution

1. Step 1: Sort each word and group by sorted key

   "eat", "tea", "ate" all sort to "aet" so grouped together; "tan", "nat" sort to "ant"; "bat" sorts to "abt".

2. Step 2: Print groups

   Groups printed are: "eat tea ate", "tan nat", and "bat".

3. Final Answer:

   Group: eat tea ate Group: tan nat Group: bat -> Option B

4. Quick Check:

   Sorted keys group anagrams correctly [OK]

Hint: Sort words, group by sorted key, print groups [OK]

Common Mistakes:

• Not sorting words before grouping
• Mixing groups by original word order
• Printing keys instead of grouped words

4. Identify the error in the following code snippet that tries to group anagrams:

std::vector words = {"abc", "bca", "cab"};
std::unordered_map> groups;
for (auto word : words) {
    std::string key = word;
    std::sort(word.begin(), word.end());
    groups[key].push_back(word);
}

medium

A. Sorting is done on 'word' but 'key' is used as map key, causing wrong grouping

B. The vector 'words' is not initialized correctly

C. The map should use vector<char> as key instead of string

D. The loop variable should be a reference to avoid copying

Solution

1. Step 1: Analyze sorting and key usage

   The code sorts 'word' but uses 'key' (unsorted) as the map key, so grouping is incorrect.

2. Step 2: Correct usage

   Sort 'key' and use it as the map key to group anagrams properly.

3. Final Answer:

   Sorting is done on 'word' but 'key' is used as map key, causing wrong grouping -> Option A

4. Quick Check:

   Sort key before using in map [OK]

Hint: Sort the key string, not the original word [OK]

Common Mistakes:

• Sorting wrong variable before using as key
• Using unsorted string as map key
• Ignoring reference vs copy in loop

5. Given a list of strings, how would you modify the grouping anagrams approach to handle case-insensitive grouping (e.g., "Eat" and "tea" should be grouped together)?

hard

A. Sort strings without changing case

B. Use the original string as key without any changes

C. Group by string length only

D. Convert each string to lowercase before sorting and using as key

Solution

1. Step 1: Normalize case for consistent keys

   Convert each string to lowercase so that case differences do not affect grouping.

2. Step 2: Sort the lowercase string and use as key

   Sorting the lowercase string ensures all case variants of anagrams map to the same key.

3. Step 3: Group anagrams using normalized keys

   Use the lowercase sorted string as the hash map key to group anagrams case-insensitively.

4. Final Answer:

   Convert each string to lowercase before sorting and using as key -> Option D

5. Quick Check:

   Lowercase + sort = case-insensitive grouping [OK]

Hint: Lowercase strings before sorting to ignore case [OK]

Common Mistakes:

• Not normalizing case before grouping
• Using original case strings as keys
• Grouping by length or unsorted strings