Group Anagrams Using Hash Map in DSA Typescript

Mental Model

Group words that have the same letters by sorting their letters and using that as a key.

Analogy: Imagine sorting letters of each word like sorting colored beads in a bag; bags with the same colors in the same order belong together.

words: ["eat", "tea", "tan", "ate", "nat", "bat"]
keys:  ["aet", "aet", "ant", "aet", "ant", "abt"]
HashMap:
"aet" -> ["eat", "tea", "ate"]
"ant" -> ["tan", "nat"]
"abt" -> ["bat"]

Dry Run Walkthrough

Input: words: ["eat", "tea", "tan", "ate", "nat", "bat"]

Goal: Group words that are anagrams into lists together

Step 1: Take first word "eat", sort letters to get "aet", add "eat" to group "aet"

"aet" -> ["eat"]

Why: Sorting letters creates a key to group anagrams

Step 2: Take second word "tea", sort letters to get "aet", add "tea" to group "aet"

"aet" -> ["eat", "tea"]

Why: Words with same sorted letters belong to same group

Step 3: Take third word "tan", sort letters to get "ant", add "tan" to group "ant"

"aet" -> ["eat", "tea"]
"ant" -> ["tan"]

Why: New sorted key creates a new group

Step 4: Take fourth word "ate", sort letters to get "aet", add "ate" to group "aet"

"aet" -> ["eat", "tea", "ate"]
"ant" -> ["tan"]

Why: Add to existing group with same key

Step 5: Take fifth word "nat", sort letters to get "ant", add "nat" to group "ant"

"aet" -> ["eat", "tea", "ate"]
"ant" -> ["tan", "nat"]

Why: Add to existing group with same key

Step 6: Take sixth word "bat", sort letters to get "abt", add "bat" to group "abt"

"aet" -> ["eat", "tea", "ate"]
"ant" -> ["tan", "nat"]
"abt" -> ["bat"]

Why: New sorted key creates a new group

Result:

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

Annotated Code

DSA Typescript

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

// Driver code
const solution = new Solution();
const input = ["eat", "tea", "tan", "ate", "nat", "bat"];
const result = solution.groupAnagrams(input);
for (const group of result) {
  console.log(group);
}

for (const word of strs) {

iterate over each word to process

const sorted = word.split('').sort().join('');

sort letters of word to create key

if (!map.has(sorted)) { map.set(sorted, []); }

create new group if key not present

map.get(sorted)!.push(word);

add word to its anagram group

return Array.from(map.values());

return all grouped anagrams as array of arrays

Output

[ 'eat', 'tea', 'ate' ]

[ 'tan', 'nat' ]

[ 'bat' ]

Complexity Analysis

Time: O(n * k log k) because we sort each of the n words of length k

Space: O(n * k) because we store all words and keys in the map

vs Alternative: Naive approach compares each word with others (O(n^2 * k)), hash map reduces to sorting keys and grouping in O(n * k log k)

Edge Cases

empty input array

returns empty array with no groups

DSA Typescript

for (const word of strs) {

words with single letter

groups single letters correctly by their letter

DSA Typescript

const sorted = word.split('').sort().join('');

all words are identical

all words grouped into one group

DSA Typescript

map.get(sorted)!.push(word);

When to Use This Pattern

When you need to group words that have the same letters in any order, use a hash map with sorted letters as keys to group anagrams efficiently.

Common Mistakes

Mistake: Using the original word as key instead of sorted letters
Fix: Sort the letters of the word before using it as a key in the map

Mistake: Not initializing the group array before pushing
Fix: Check if key exists in map; if not, create an empty array before pushing

Summary

Groups words that are anagrams by sorting their letters and using a hash map.

Use when you want to collect words that have the same letters regardless of order.

The key insight is that sorted letters form a unique signature for 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