Group Anagrams - Meta Interview Question & Solution

Group Anagrams

Meta

Array

String

Hash Table

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

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

Example:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Solution Walkthrough

Two strings are anagrams of each other if and only if they produce the same string once sorted. That gives us a natural hash key: sort each word's letters, and group every original word under that sorted key.

Create a hash map from sortedKey → list of original words.
For each word in strs, split it into characters, sort them, and join them back into a string — this is the canonical key for its anagram group.
Push the original word onto the map entry for that key (creating the entry if it doesn't exist yet).
Once every word has been processed, the map's values are exactly the grouped anagrams — return them as an array of arrays.

Sorting each word of length k costs O(k log k), so for n words the total time complexity is O(n · k log k). Space complexity is O(n · k) to store all the words in the map.

function groupAnagrams(strs) {
    const map = new Map();

    for (const word of strs) {
        // Sorting the letters gives a canonical key shared by all anagrams
        const key = word.split('').sort().join('');

        if (!map.has(key)) {
            map.set(key, []);
        }
        map.get(key).push(word);
    }

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

Related Algorithms

Hashing →