Group Anagrams Using Hash Map in DSA Javascript - 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

↓

If key exists: append word to list

↓

Else: create new list with word

↓

Repeat for all words

↓

Collect all lists from hash map

↓

Return grouped anagrams

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

Execution Sample

DSA Javascript

function groupAnagrams(words) {
  const map = new Map();
  for (const word of words) {
    const key = [...word].sort().join('');
    if (!map.has(key)) map.set(key, []);
    map.get(key).push(word);
  }
  return [...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	Start	-	-	{}	{}
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"]]

💡 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	After 7	Final
word	-	eat	tea	tan	ate	nat	bat	-	-
key	-	aet	aet	ant	aet	ant	abt	-	-
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"]}	-	-

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' (see steps 2, 3, 5 in execution_table). This groups them together.

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 (see step 2 for 'aet' and step 4 for 'ant'). This ensures new groups start correctly.

How do we get the final grouped anagrams from the hash map?

We collect all the lists stored as values in the hash map (step 8 in execution_table), which represent groups of anagrams.

Visual Quiz - 3 Questions

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

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

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

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

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

💡 Hint

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

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

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look at the 'Sorted Key' and 'Hash Map State' columns in execution_table to find when 'abt' is added.

If the word 'bat' was processed before 'tan', how would the hash map state change at step 4?

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

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

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

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

💡 Hint

Consider the order of processing and when keys are created in the hash map (see variable_tracker).

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 word to existing list or create new list.
- Return all grouped lists from hash map values.
- Efficiently groups anagrams by shared sorted key.

Full Transcript

This concept groups words that are anagrams by sorting their letters to create a unique 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 added to the existing list; if not, a new list is created. After processing all words, the values of the hash map are collected as groups of anagrams. The execution table shows each step with the current word, its sorted key, and the state of the hash map. The variable tracker follows the changes in the word, key, and map variables. Key moments clarify why sorting is needed, how new keys are handled, and how final groups are collected. The visual quiz tests understanding of the hash map state at different steps and the effect of processing order.

Practice

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

easy

A. Group words by their length using a hash map

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

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

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

Solution

1. Step 1: Understand anagrams

   Anagrams are words with the same letters in different orders, so sorting letters gives a unique key.

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.

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 = C [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 of the following JavaScript code snippets correctly initializes an empty hash map to group anagrams?

easy

A. const map = {};

B. const map = Map();

C. const map = [];

D. const map = new Set();

Solution

1. Step 1: Identify hash map initialization in JavaScript

   JavaScript objects ({}) are commonly used as hash maps for key-value pairs.

2. Step 2: Analyze the options

   {} creates a simple hash map using bracket notation like map[key]. Map() without new throws TypeError. [] creates an array unsuitable for key-value pairs. new Set() stores unique values, not mappings.

3. Final Answer:

   const map = {}; -> Option A

4. Quick Check:

   Object literal {} is simplest hash map = A [OK]

Hint: Use {} to create a simple hash map in JavaScript [OK]

Common Mistakes:

• Using array [] instead of object
• Using Set which doesn't store key-value pairs
• Confusing Map and object initialization

3. What is the output of the following code?

function groupAnagrams(words) {
  const map = {};
  for (const word of words) {
    const sorted = word.split('').sort().join('');
    if (!map[sorted]) map[sorted] = [];
    map[sorted].push(word);
  }
  return Object.values(map);
}

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

medium

A. SyntaxError

B. [['bat'], ['tab'], ['eat'], ['tea'], ['ate']]

C. [['bat', 'tab'], ['eat', 'tea', 'ate']]

D. [['bat', 'tab', 'eat', 'tea', 'ate']]

Solution

1. Step 1: Sort each word and group in map

   Words 'bat' and 'tab' both sort to 'abt', so grouped together. 'eat', 'tea', 'ate' all sort to 'aet', grouped together.

2. Step 2: Return grouped anagrams as array of arrays

   Object.values(map) returns arrays of grouped words: [['bat', 'tab'], ['eat', 'tea', 'ate']].

3. Final Answer:

   [['bat', 'tab'], ['eat', 'tea', 'ate']] -> Option C

4. Quick Check:

   Sorted keys group words = [['bat','tab'],['eat','tea','ate']] [OK]

Hint: Sort words, group by sorted key, return grouped arrays [OK]

Common Mistakes:

• Returning flat list instead of grouped arrays
• Not sorting words before grouping
• Syntax errors from missing brackets

4. Find the error in this code snippet for grouping anagrams:

function groupAnagrams(words) {
  const map = {};
  for (const word of words) {
    const sorted = word.sort().join('');
    if (!map[sorted]) map[sorted] = [];
    map[sorted].push(word);
  }
  return Object.values(map);
}

medium

A. map should be initialized as a Map object

B. word.sort() is invalid because word is a string, not an array

C. Missing return statement

D. Using Object.values on map is incorrect

Solution

1. Step 1: Identify the error in sorting

   word is a string, and strings do not have a sort() method. It must be split into an array first.

2. Step 2: Correct approach to sort letters

   Use word.split('').sort().join('') to sort letters of the string correctly.

3. Final Answer:

   word.sort() is invalid because word is a string, not an array -> Option B

4. Quick Check:

   Strings need split() before sort() = B [OK]

Hint: Split string to array before sorting letters [OK]

Common Mistakes:

• Calling sort() directly on string
• Not splitting string before sorting
• Confusing Map object with plain object

5. Given the input array ['listen', 'silent', 'enlist', 'google', 'gogole', 'abc', 'cab'], which of the following is the correct grouped anagrams output using a hash map approach?

hard

A. [['listen', 'silent', 'enlist'], ['google', 'gogole'], ['abc', 'cab']]

B. [['listen', 'silent'], ['enlist', 'google'], ['gogole', 'abc', 'cab']]

C. [['listen'], ['silent'], ['enlist'], ['google'], ['gogole'], ['abc'], ['cab']]

D. [['listen', 'silent', 'enlist', 'google', 'gogole', 'abc', 'cab']]

Solution

1. Step 1: Sort each word to find keys

   'listen', 'silent', 'enlist' all sort to 'eilnst'; 'google', 'gogole' sort to 'eggloo'; 'abc', 'cab' sort to 'abc'.

2. Step 2: Group words by sorted keys

   Group words with same sorted key together: [['listen', 'silent', 'enlist'], ['google', 'gogole'], ['abc', 'cab']].

3. Final Answer:

   [['listen', 'silent', 'enlist'], ['google', 'gogole'], ['abc', 'cab']] -> Option A

4. Quick Check:

   Sorted keys group anagrams correctly = A [OK]

Hint: Sort letters, group by key, collect arrays [OK]

Common Mistakes:

• Mixing groups with different sorted keys
• Grouping by word length instead of letters
• Returning flat list instead of grouped arrays