How do you group anagrams together from a list of words?
Anagrams share the same sorted letters, so use the sorted word as a hash map key and collect each word under its key. The map values are the groups.
Explain it simply
Imagine sorting letters in a college library by their first-letter bundle. Two words are anagrams if they contain the same letters, so if you sort the letters of each word you get an identical "signature". "eat", "tea" and "ate" all become "aet".
Use that signature as a key in a map. Every word goes into the list stored under its signature, and at the end the lists are your groups.
Example
function groupAnagrams(words) {
const groups = new Map();
for (const word of words) {
const key = word.split("").sort().join("");
if (!groups.has(key)) groups.set(key, []);
groups.get(key).push(word);
}
return [...groups.values()];
}
console.log(JSON.stringify(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"])));
// Output: [["eat","tea","ate"],["tan","nat"],["bat"]]Complexity
Time O(n k log k) for n words of length up to k, space O(n k).
What to say in the interview
"I use the sorted letters of each word as a key in a Map and push the word into that key's list. For n words of maximum length k, time is O(n k log k) because of sorting each word, and space is O(n k). A letter-count signature can replace sorting to get O(n k)."
Common mistakes
- Using an object with a numeric-looking key and expecting insertion order.
- Comparing every pair of words, which is O(n squared).