Problem 2 · Arrays & Hashing

Group Anagrams

MediumClassic DSA & systems

01Problem

Given a list of strings, group the strings that are anagrams of each other.

02Key insight

Anagrams share a canonical key. The sorted string works for any alphabet (case and Unicode included) at O(k log k) per word; a 26-count tuple is O(k) but only valid when input is guaranteed lowercase a-z. Either way it's a GROUP BY on a derived column.

03Solution

solution.pypython7 lines

from collections import defaultdict

def group_anagrams(words: list[str]) -> list[list[str]]:
    groups: dict[str, list[str]] = defaultdict(list)
    for w in words:
        groups["".join(sorted(w))].append(w)
    return list(groups.values())

Try it first.

TimeO(n*k log k)

SpaceO(n*k)

tests.py · 4 passing

tests.pypython5 lines

norm = lambda g: sorted(sorted(x) for x in g)
assert norm(group_anagrams(["eat","tea","tan","ate","nat","bat"])) == [["ate","eat","tea"],["bat"],["nat","tan"]]
assert group_anagrams([""]) == [[""]]
assert group_anagrams([]) == []
assert norm(group_anagrams(["Tan", "nan"])) == [["Tan"], ["nan"]]

04Staff-level follow-up

How would you do this over billions of words? MapReduce/Spark: map each word to (canonical_key, word), shuffle by key, reduce collects groups; watch for skewed hot keys.