Grouping with a hash map

The problem we are solving:

You are given an array of words [“eat”, “tea”, “ate”, “bat”, “tab”] and asked: group all anagrams together.

One approach: nested loops and anagram checks.

function groupAnagramsNaive(words) {
  const groups = [];
  const used = new Array(words.length).fill(false);
  
  for (let i = 0; i < words.length; i++) {
    if (used[i]) continue;
    
    const group = [words[i]];
    used[i] = true;
    
    // For each word, check all remaining words
    for (let j = i + 1; j < words.length; j++) {
      if (!used[j] && areAnagrams(words[i], words[j])) {
        group.push(words[j]);
        used[j] = true;
      }
    }
    
    groups.push(group);
  }
  
  return groups;
}

function areAnagrams(s, t) {
  if (s.length !== t.length) return false;
  const sorted1 = s.split('').sort().join('');
  const sorted2 = t.split('').sort().join('');
  return sorted1 === sorted2;
}

This is O(n² · m log m) where n is the number of words and m is the average word length.

The grouping pattern idea:

Instead, use a hash map where the value is a list, not a count. For each word, compute its group key (the letters sorted), then append it to the list under that key.

function groupAnagrams(words) {
  const map = new Map();  // key → [list of words]
  
  for (let word of words) {
    // Compute the group key: sorted letters
    const key = word.split('').sort().join('');
    
    // Append this word to the list under that key
    if (!map.has(key)) {
      map.set(key, []);
    }
    map.get(key).push(word);
  }
  
  // Return all groups
  return Array.from(map.values());
}

// Example: ["eat", "tea", "ate", "tan", "nat"]
// "eat" → key "aet" → map["aet"] = ["eat"]
// "tea" → key "aet" → map["aet"] = ["eat", "tea"]
// "ate" → key "aet" → map["aet"] = ["eat", "tea", "ate"]
// "tan" → key "ant" → map["ant"] = ["tan"]
// "nat" → key "ant" → map["ant"] = ["tan", "nat"]
// Result: [["eat", "tea", "ate"], ["tan", "nat"]]

One loop, O(n · m log m) time (n words, each taking m log m to sort and hash). One hash map, O(n) space.

Why it works:

• Same key, same group: all anagrams of a word have the same sorted letters, so they compute the same key and land in the same bucket.
• Order does not matter: if “aet” comes before “ate”, they both map to “aet” and merge into one list.
• One pass: as you iterate, items that belong together collide on purpose under the same key.

The shape of grouping:

The pattern is: for each item: key = f(item); map[key].push(item).

Key design is the heart of grouping. The right key makes items that belong together collide:

• Anagrams: key = sorted letters. “eat”, “tea”, “ate” all map to “aet”.
• Remainder groups: key = n % k. Numbers 5, 11, 17 with k=6 all map to 5 (remainder).
• First letter: key = word[0]. “apple”, “apricot” both map to “a”.
• Age bracket: key = Math.floor(age / 10). Ages 23, 24, 25 all map to 2 (20s).
• Row in a grid: key = point.row. Points (3, 1), (3, 5), (3, 9) all map to row 3.

Grouping vs. frequency counting:

• Frequency: map[key] is a count (a number). How many times does each key appear?
• Grouping: map[key] is a list (an array). Which items map to this key?

Frequency answers “how many”. Grouping answers “which ones”.

Example:

// Frequency: count characters in "mississippi"
const freq = new Map();
for (let char of "mississippi") {
  freq.set(char, (freq.get(char) ?? 0) + 1);
}
// freq: m→1, i→4, s→4, p→2

// Grouping: group characters by value in "mississippi"
const groups = new Map();
for (let char of "mississippi") {
  if (!groups.has(char)) groups.set(char, []);
  groups.get(char).push(char);
}
// groups: m→['m'], i→['i','i','i','i'], s→['s','s','s','s'], p→['p','p']