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

↓

Collect all lists from hash map as grouped anagrams

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

Execution Sample

DSA C#

string[] words = {"eat", "tea", "tan", "ate", "nat", "bat"};
var groups = new Dictionary<string, List<string>>();
foreach (var word in words) {
  var key = String.Concat(word.OrderBy(c => c));
  if (!groups.ContainsKey(key)) groups[key] = new List<string>();
  groups[key].Add(word);
}

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

Execution Table

Step	Operation	Current Word	Sorted Key	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	Collect groups	-	-	[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]	Groups: eat, tea, ate | tan, nat | bat
8	End	-	-	Completed grouping	Final groups formed

💡 All words processed and grouped by their sorted keys.

Variable Tracker

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

Key Moments - 3 Insights

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

Sorting the word puts all anagrams into the same order, so they share the same key in the hash map. See execution_table rows 1, 2, and 4 where 'eat', 'tea', and 'ate' all map to 'aet'.

What happens if the key does not exist in the hash map?

We create a new list for that key and add the current word. This is shown in execution_table row 1 for key 'aet' and row 3 for key 'ant'.

How do we collect the final groups after processing all words?

We take all the lists stored as values in the hash map and return them as grouped anagrams. This is shown in execution_table row 7.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the hash map state?

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

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

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

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

💡 Hint

Check the 'Hash Map State' column at step 4 in the execution_table.

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

A Step 3

B Step 5

C Step 6

D Step 2

💡 Hint

Look for the first occurrence of 'abt' in the 'Sorted Key' column in the execution_table.

If the word 'tab' was added after 'bat', which key would it map to and how would the groups change?

A Key 'bat', group would be ["bat", "tab"]

B Key 'abt', group would be ["bat", "tab"]

C Key 'tab', group would be ["bat", "tab"]

D Key 'abt', group would be ["bat"] and ["tab"] separately

💡 Hint

Words with same letters sorted have the same key; see variable_tracker for key values.

Concept Snapshot

Group Anagrams Using Hash Map:
- Sort each word's letters to create a key.
- Use the sorted key in a hash map to group words.
- Append words to list if key exists, else create new list.
- Collect all lists as grouped anagrams.
- Efficiently groups anagrams in O(N*K log K) time (N=words, K=word length).

Full Transcript

This concept groups words that are anagrams by sorting each word's letters to create a key. We use a hash map where each key is the sorted word, and the value is a list of words that match that key. For each word, we sort it, check if the key exists in the hash map, and add the word to the corresponding list. If the key does not exist, we create a new list. After processing all words, we collect all lists from the hash map as groups of anagrams. The execution table shows each step with the current word, its sorted key, the hash map state, and the visual grouping. The variable tracker shows how variables change after each step. Key moments clarify why sorting is needed, what happens when keys are new, and how final groups are collected. The visual quiz tests understanding of the hash map state at different steps and the effect of adding new words. This method efficiently groups anagrams by leveraging sorted keys in a hash map.

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 letters

B. Use the length of the word as the key to group anagrams

C. Use the first letter of the word as the key to group anagrams

D. Use the last letter of the word as the key to group anagrams

Solution

1. Step 1: Understand anagrams

   Anagrams are words with the same letters in different orders.

2. Step 2: Use sorted string as key

   Sorting letters of each word gives a unique key for all anagrams.

3. Final Answer:

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

4. Quick Check:

   Sorted string key groups anagrams [OK]

Hint: Sort each word and use it as key in hash map [OK]

Common Mistakes:

• Using word length as key causes wrong grouping
• Using first or last letter misses many anagrams
• Not sorting letters before using as key

2. Which of the following C# code snippets correctly initializes a hash map to group anagrams?

easy

A. var map = new Dictionary();

B. var map = new List>();

C. var map = new Dictionary();

D. var map = new Dictionary();

Solution

1. Step 1: Identify correct dictionary type

   We need keys as strings (sorted words) and values as lists of strings (anagrams).

2. Step 2: Check each option

   var map = new Dictionary(); uses Dictionary which fits the requirement.

3. Final Answer:

   var map = new Dictionary(); -> Option A

4. Quick Check:

   Dictionary with string keys and list values [OK]

Hint: Use Dictionary for grouping anagrams [OK]

Common Mistakes:

• Using List of dictionaries instead of dictionary
• Using wrong key or value types
• Using Dictionary which can't group anagrams

3. What is the output of the following C# code?

var strs = new string[] {"eat", "tea", "tan", "ate", "nat", "bat"};
var map = new Dictionary();
foreach (var s in strs) {
  var key = String.Concat(s.OrderBy(c => c));
  if (!map.ContainsKey(key)) map[key] = new List<string>();
  map[key].Add(s);
}
foreach (var group in map.Values) {
  Console.WriteLine(string.Join(", ", group));
}

medium

A. "eat, tea\nate, tan\nbat, nat"

B. "eat, tan, bat\ntea, ate, nat"

C. "eat, tea, ate\ntan, nat\nbat"

D. "eat, tea, ate, tan, nat, bat"

Solution

1. Step 1: Sort each word to find keys

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

2. Step 2: Group words by keys and print

   Groups are ["eat", "tea", "ate"], ["tan", "nat"], ["bat"]. Printed line by line.

3. Final Answer:

   "eat, tea, ate\ntan, nat\nbat" -> Option C

4. Quick Check:

   Sorted keys group anagrams correctly [OK]

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

Common Mistakes:

• Printing all words in one line
• Grouping by unsorted words
• Mixing groups incorrectly

4. Identify the bug in this C# code snippet for grouping anagrams:

var map = new Dictionary();
foreach (var s in strs) {
  var key = s.OrderBy(c => c).ToString();
  if (!map.ContainsKey(key)) map[key] = new List<string>();
  map[key].Add(s);
}

medium

A. Not checking if key exists before adding

B. Missing initialization of map dictionary

C. Using List<string> instead of List<char> for values

D. Using ToString() on IEnumerable<char> does not produce sorted string key

Solution

1. Step 1: Understand s.OrderBy(c => c)

   This returns IEnumerable<char>, not a string.

2. Step 2: Using ToString() on IEnumerable<char>

   ToString() returns type name, not sorted string key. Need to join chars to string.

3. Final Answer:

   Using ToString() on IEnumerable<char> does not produce sorted string key -> Option D

4. Quick Check:

   Use String.Concat or new string() to convert chars to string [OK]

Hint: Convert sorted chars to string with String.Concat, not ToString() [OK]

Common Mistakes:

• Calling ToString() on IEnumerable<char> expecting string
• Not initializing dictionary before use
• Ignoring key existence check

5. Given a list of strings, how would you modify the grouping anagrams code to ignore case differences (e.g., "Eat" and "tea" should be grouped)?

hard

A. Group by string length only

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

C. Sort strings but keep original case for keys

D. Use the original string as key without sorting

Solution

1. Step 1: Normalize case for grouping

   Convert each string to lowercase to treat "Eat" and "tea" the same.

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

   Sorting lowercase letters groups anagrams ignoring case.

3. Final Answer:

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

4. Quick Check:

   Lowercase + sort = case-insensitive grouping [OK]

Hint: Lowercase strings before sorting for case-insensitive grouping [OK]

Common Mistakes:

• Sorting without case normalization
• Using original case keys causing separate groups
• Grouping by length which is insufficient