Group Anagrams Using Hash Map in DSA Typescript - Execution Trace

Concept Flow - Group Anagrams Using Hash Map

Start with list of words

↓

For each word: Sort letters alphabetically

↓

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

↓

After all words processed

↓

Collect all lists from hash map as grouped anagrams

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 Typescript

function groupAnagrams(words: string[]): string[][] {
  const map = new Map<string, string[]>();
  for (const word of words) {
    const key = word.split('').sort().join('');
    if (!map.has(key)) map.set(key, []);
    map.get(key)!.push(word);
  }
  return Array.from(map.values());
}

This code groups words that are anagrams by sorting letters and 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
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	N/A	N/A	Groups: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]	[Group 1] eat, tea, ate [Group 2] tan, nat [Group 3] bat
8	End	N/A	N/A	Final grouped anagrams returned	Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

💡 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
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"]}	[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
current word	N/A	"eat"	"tea"	"tan"	"ate"	"nat"	"bat"	N/A
sorted key	N/A	"aet"	"aet"	"ant"	"aet"	"ant"	"abt"	N/A

Key Moments - 3 Insights

Why do we sort the word to create the key?

Sorting letters puts all anagrams into the same order, so they share the same key in the hash map (see execution_table steps 1, 2, 4).

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

We create a new list for that key and add the current word (see execution_table step 3 and 6).

Why do we use a hash map instead of just comparing words directly?

Hash map lets us group words efficiently by their sorted key without checking every pair, saving time (see variable_tracker map growth).

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", "ate"], "ant": ["tan"]}

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

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

💡 Hint

Check execution_table row 4 under 'Hash Map State' column.

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

A Step 5

B Step 3

C Step 6

D Step 2

💡 Hint

Look at execution_table rows and see when "bat" is processed and its sorted key "abt" is added.

If the input list had an extra word "tab", where would it appear in the hash map?

A Under key "abt" with "bat"

B Under key "aet" with "eat"

C Under key "ant" with "tan"

D As a new key "tab" alone

💡 Hint

Remember sorting letters of "tab" results in "abt", same as "bat" (see variable_tracker sorted key).

Concept Snapshot

Group Anagrams Using Hash Map:
- Sort each word's letters to create a key.
- Use a hash map with sorted key to group words.
- Append words to list at that key.
- Return all grouped lists.
- Efficiently groups anagrams by shared sorted keys.

Full Transcript

To group anagrams, we take each word and sort its letters alphabetically. This sorted word acts as a key in a hash map. If the key exists, we add the original word to the list for that key. If not, we create a new list. After processing all words, we collect all lists from the hash map. This groups all anagrams together because they share the same sorted key. For example, "eat", "tea", and "ate" all sort to "aet" and are grouped together. The hash map grows as we process each word, and the final output is a list of grouped anagrams.

Practice

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

easy

A. Count the number of vowels in each word and group by count

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

C. Group words by their length using a hash map

D. Use the first letter of each word as the key in the hash map

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 its anagrams.

3. Final Answer:

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

4. Quick Check:

   Sorted word key groups anagrams = A [OK]

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

Common Mistakes:

• Grouping by word length only
• Using first letter as key
• Counting vowels instead of letters

2. Which TypeScript syntax correctly initializes a hash map to group anagrams?

easy

A. const map = new Map();

B. const map = new Map();

C. const map = new Map();

D. const map = new Map();

Solution

1. Step 1: Identify key and value types

   Keys are sorted strings, values are arrays of strings (anagrams).

2. Step 2: Match types in Map initialization

   Map matches key as string and value as string array.

3. Final Answer:

   const map = new Map(); -> Option A

4. Quick Check:

   Map key=string, value=string array = D [OK]

Hint: Map keys are strings; values are arrays of strings [OK]

Common Mistakes:

• Using number as key instead of string
• Using number array as value
• Confusing value type with number

3. What is the output of this TypeScript code?

function groupAnagrams(strs: string[]): string[][] {
  const map = new Map();
  for (const str of strs) {
    const key = str.split('').sort().join('');
    if (!map.has(key)) map.set(key, []);
    map.get(key)!.push(str);
  }
  return Array.from(map.values());
}

console.log(groupAnagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat']));

medium

A. [["eat", "tan", "bat"], ["tea", "nat", "ate"]]

B. [["eat"], ["tea"], ["tan"], ["ate"], ["nat"], ["bat"]]

C. [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

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

Solution

1. Step 1: Sort each word to create keys

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

2. Step 2: Group words by keys in map

   Map groups: "aet" -> ["eat", "tea", "ate"], "ant" -> ["tan", "nat"], "abt" -> ["bat"].

3. Final Answer:

   [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]] -> Option C

4. Quick Check:

   Sorted keys group anagrams = B [OK]

Hint: Sort letters to find groups, then collect values [OK]

Common Mistakes:

• Mixing groups by length or first letter
• Returning individual words instead of groups
• Incorrect grouping order

4. Identify the bug in this TypeScript code for grouping anagrams:

function groupAnagrams(strs: string[]): string[][] {
  const map = new Map();
  for (const str of strs) {
    const key = str.split('').sort();
    if (!map.has(key)) map.set(key, []);
    map.get(key)!.push(str);
  }
  return Array.from(map.values());
}

medium

A. The key is an array, should be a string after join()

B. map.get(key) returns undefined, should check with has() first

C. Using Map instead of plain object causes error

D. Missing return type annotation on function

Solution

1. Step 1: Check key creation

   str.split('').sort() returns an array, not a string key.

2. Step 2: Fix key by joining sorted array

   Use str.split('').sort().join('') to create string key for map.

3. Final Answer:

   The key is an array, should be a string after join() -> Option A

4. Quick Check:

   Key must be string, not array = A [OK]

Hint: Join sorted array to form string key [OK]

Common Mistakes:

• Using array as map key without joining
• Ignoring map.has() check
• Confusing Map with plain object

5. Given the input array ['abc', 'bca', 'cab', 'xyz', 'zyx', 'zxy', 'aabb', 'baba'], which code snippet correctly groups anagrams using a hash map and filters out groups with less than 3 words?

hard

A. const map = new Map();
for (const str of strs) {
const key = str[0];
if (!map.has(key)) map.set(key, []);
map.get(key)!.push(str);
}
return Array.from(map.values()).filter(group => group.length >= 3);

B. const map = new Map();
for (const str of strs) {
const key = str.length.toString();
if (!map.has(key)) map.set(key, []);
map.get(key)!.push(str);
}
return Array.from(map.values()).filter(group => group.length >= 3);

C. const map = new Map();
for (const str of strs) {
const key = str.split('').reverse().join('');
if (!map.has(key)) map.set(key, []);
map.get(key)!.push(str);
}
return Array.from(map.values()).filter(group => group.length >= 3);

D. const map = new Map();
for (const str of strs) {
const key = str.split('').sort().join('');
if (!map.has(key)) map.set(key, []);
map.get(key)!.push(str);
}
return Array.from(map.values()).filter(group => group.length >= 3);

Solution

1. Step 1: Create keys by sorting letters

   Sorting letters groups anagrams correctly, e.g., "abc", "bca", "cab" all become "abc".

2. Step 2: Filter groups with 3 or more words

   Use filter to keep only groups where length >= 3.

3. Final Answer:

   Code snippet using sorted keys and filtering groups by length >= 3 -> Option D

4. Quick Check:

   Sort keys + filter groups >= 3 = C [OK]

Hint: Sort letters for keys, then filter groups by size [OK]

Common Mistakes:

• Using word length or first letter as key
• Reversing letters instead of sorting
• Not filtering groups by size