Group Anagrams Using Hash Map in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is an anagram?

An anagram is a word or phrase formed by rearranging the letters of another word or phrase, using all the original letters exactly once.

beginner

Why do we use a hash map to group anagrams?

A hash map helps group words that are anagrams by using a key that represents the sorted letters of the word. Words with the same sorted key are anagrams and stored together.

beginner

How do you create a key for each word to group anagrams?

Sort the letters of the word alphabetically and use the sorted string as the key in the hash map.

intermediate

What is the time complexity of grouping anagrams using a hash map?

The time complexity is O(N * K log K), where N is the number of words and K is the maximum length of a word (due to sorting each word).

beginner

What does the final output look like after grouping anagrams?

The output is a list of lists, where each inner list contains words that are anagrams of each other.

What key is used in the hash map to group anagrams?

A First letter of the word

B Length of the word

C Sorted letters of the word

D Number of vowels in the word

The sorted letters of the word are used as the key because anagrams share the same letters in the same frequency.

Which data structure is best to group anagrams efficiently?

A Hash Map

B Stack

C Queue

D Linked List

Hash Map allows quick grouping by keys, which is ideal for grouping anagrams.

What is the main operation done on each word before using it as a key?

A Converting to uppercase

B Reversing the word

C Counting vowels

D Sorting the letters

Sorting the letters ensures that all anagrams have the same key.

If the input is ['bat', 'tab', 'eat', 'tea'], what will be one group in the output?

A ['bat', 'tab']

B ['bat', 'eat']

C ['tab', 'eat']

D ['eat', 'bat']

‘bat’ and ‘tab’ are anagrams and will be grouped together.

What is the output type of the group anagrams function?

A Single string

B List of lists of strings

C Integer count

D Boolean value

The function returns a list where each element is a list of anagram words.

Explain how to group anagrams using a hash map step-by-step.

Think about how sorting helps identify anagrams and how a hash map stores groups.

Describe the time complexity of grouping anagrams and why sorting each word affects it.

Focus on the sorting step inside the loop over all words.

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