Group Anagrams

Group Anagrams is a clean lesson in canonical keys: turn each item into a fingerprint, then bucket items by that fingerprint with a hash map.

The slow way first

The obvious idea: compare every pair of words and ask "are these two anagrams?" Checking one pair takes O(k) work (sort or count the letters), and there are O(n²) pairs, so the whole thing is O(n² k). For a long list that is far too slow, and stitching the matches into groups is fiddly.

The question to ask: what do all anagrams have in common that I can compute once per word? Their sorted letters. "eat", "tea", and "ate" all become "aet". That shared string is a perfect map key.

The idea: a canonical key

Walk the list once. For each word w, build its canonical key by sorting its letters: "".join(sorted(w)). Use that key to look up a bucket in a hash map and append w to it. Anagrams collapse onto the same key automatically, so they land in the same bucket.

The key insight: anagrams are defined by having the same multiset of letters, and sorting turns that multiset into one canonical string. Equal multisets → equal key → same bucket.

Walk through it

Step through the animation. The pointer w scans the words left to right. For each word we show its sorted key, then watch the matching bucket fill. "eat", "tea", "ate" all route to "aet"; "tan" and "nat" route to "ant"; "bat" lands alone in "abt". At the end we return the buckets.

Pseudocode

make an empty map "groups" whose default value is an empty list
for each word w in words:
    key = the letters of w, sorted, joined into a string
    append w to groups[key]
return all the lists stored in groups

The Python solution

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        key = "".join(sorted(w))
        groups[key].append(w)
    return list(groups.values())

• defaultdict(list) means an unseen key auto-creates an empty list, so we never check "does this bucket exist yet?"
• sorted(w) returns the word's characters in order; "".join(...) glues them back into a string like "aet".
• groups[key].append(w) is the whole algorithm — one O(1) lookup, then add the word.
• list(groups.values()) hands back the groups; the order is unspecified, which the problem allows.

Complexity

Sorting each word costs O(k log k), done n times. We trade O(n k) extra space (the map of buckets) for a big speed win. Using a 26-letter count tuple as the key instead of a sorted string drops the per-word cost to O(k), giving O(n k) overall.

When this pattern shows up

Practice