Group Anagrams Using Hash Map in DSA Javascript

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]
map:   {
  '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 together in lists

Step 1: Take first word 'eat', sort letters to get 'aet', add 'eat' to map under key 'aet'

{ 'aet': ['eat'] }

Why: Sorting letters creates a unique key for all anagrams

Step 2: Take second word 'tea', sort letters to get 'aet', add 'tea' to map under key '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 map under key 'ant'

{ 'aet': ['eat', 'tea'], 'ant': ['tan'] }

Why: New sorted key means new group

Step 4: Take fourth word 'ate', sort letters to get 'aet', add 'ate' to map under key 'aet'

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

Why: Add to existing group of anagrams

Step 5: Take fifth word 'nat', sort letters to get 'ant', add 'nat' to map under key 'ant'

{ 'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'] }

Why: Add to existing group of anagrams

Step 6: Take sixth word 'bat', sort letters to get 'abt', add 'bat' to map under key 'abt'

{ 'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat'] }

Why: New group for different letters

Result:

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

Annotated Code

DSA Javascript

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

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.join(', '));
}

const sorted = [...word].sort().join('');

sort letters of current 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 groups 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 grouped in the map

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

Edge Cases

empty input array

returns empty array with no groups

DSA Javascript

for (const word of strs) {

words with single letter

groups single letters correctly by their letter

DSA Javascript

const sorted = [...word].sort().join('');

all words are identical

all words grouped together under one key

DSA Javascript

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

When to Use This Pattern

When you need to group words that are made of the same letters, use sorting as a key and a hash map 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

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

Summary

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

Use when you want to find all sets of words that have the same letters.

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