LeetCode 49 · Arrays & Hashing

Group Anagrams, explained with a picture

Sorting words into jars by their letters.

MediumArrays & Hashing
▶ Watch it step by step

The problem

Given a list of words, group together the words that are anagrams of each other (same letters, different order). Return the groups.

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

Picture it

Picture a row of glass jars, each with a label. To decide where a word goes, sort its letters alphabetically: “tea” becomes “aet”. That sorted spelling is the label on its jar. Words with the same letters always produce the same label, so they land in the same jar. A new label means a new jar.

How to recognise it

  • You must sort items into groups, where two items belong together if they are "the same" in some looser sense.
  • That sameness can be turned into a key: a value every member of a group shares and no outsider has. Here, anagrams share the same letters in sorted order.
  • Grouping by a key is a dictionary from key to list.
  • Up to 10^4 words means comparing every word with every other word is too slow.

Start with brute force

Keep a list of groups. For each word, compare it with the first word of every existing group; join the first group it matches, or start a new one.

def group_anagrams_brute(words):
    groups = []
    for w in words:
        for g in groups:
            if sorted(g[0]) == sorted(w):
                g.append(w)
                break
        else:                       # no group matched
            groups.append([w])
    return groups

With n words of length up to k, each word may be compared with up to n groups, and each comparison sorts two words: O(n² · k log k) time. If no two words are anagrams, n = 10^4 gives about 5 × 10^7 comparisons, each sorting two words of up to 100 letters. Space is O(n · k) for the groups.

From brute force to the idea

  1. Find the waste. Each word is compared against every group, and each group's first word is re-sorted every time.
  2. Give every word a label. Sort a word's letters once: "eat", "tea" and "ate" all become "aet". Anagrams get the same label, and non-anagrams never do.
  3. Look the label up. A dictionary from label to list finds the right group in O(1) on average, instead of scanning all groups.
  4. Join to make it hashable. sorted(w) returns a list, which cannot be a dictionary key, so the code joins it back into a string.
  5. Let defaultdict start groups. jars[key].append(w) creates an empty list the first time a key appears.

This is the key idea: map each word to a canonical key (its sorted letters) and group by that key.

The key idea

Give every word a “signature” that all its anagrams share (its sorted letters) and use it as a dictionary key.

Python solution

def group_anagrams(words):
    jars = defaultdict(list)
    for w in words:
        key = "".join(sorted(w))     # same letters, same key
        jars[key].append(w)
    return list(jars.values())

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import defaultdict

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n² · k log k): each word is compared with every groupO(n · k): the groups hold every word
Sorted-letters key (shown code)O(n · k log k): one sort per word, one O(1) average dictionary stepO(n · k): the keys and the groups

Here n is the number of words and k the length of the longest word.

Edge cases

  • Empty word ([""]): its key is "", so it forms its own group, [[""]]. Several empty words land in one group.
  • Single word: returns one group containing it.
  • Repeated words (["ab", "ba", "ab"]): all three go into one group; duplicates are kept, not removed.
  • Output order: groups appear in the order their first word appeared, and words keep their input order, because Python dictionaries preserve insertion order. LeetCode accepts any order.
  • Missing import: the code needs from collections import defaultdict; without it the call raises NameError.

Common mistakes

  • Using sorted(w) directly as the key. It is a list, so Python raises TypeError: unhashable type: 'list'.
  • Using set(w) or frozenset(w) as the key, which forgets counts, so "aab" and "ab" land together.
  • Returning jars.values() without list(...). It is a view, not a list, which some callers and tests reject.

A faster key for long words is a tuple of 26 letter counts, which takes O(k) to build instead of O(k log k).

Your turn: group shifted strings

Two lowercase words belong together if shifting every letter of one by the same amount (wrapping from z to a) gives the other: "abc", "bcd" and "xyz" are one group, and "az" and "ba" are another. Group a list of non-empty words this way. Describe your approach, then write it if you like.

Compare with our answer

Find a key that every shift of a word shares. Measure each letter's distance from the first letter, modulo 26. Shifting the whole word changes every letter by the same amount, so the distances stay the same.

from collections import defaultdict

def group_shifted(words):
    jars = defaultdict(list)
    for w in words:
        key = tuple((ord(ch) - ord(w[0])) % 26 for ch in w)
        jars[key].append(w)
    return list(jars.values())

"az" gives (0, 25) and "ba" gives (0, 25) too, thanks to the modulo. Time O(n · k), space O(n · k).

A strong answer mentions: a key that does not change under the shift, the % 26 for wrap-around, and a tuple (not a list) so the key is hashable.

Check what stuck

1. You must group words that use the same set of letters, ignoring repeats, so "aab" and "ab" belong together. Which approach fits?

2. Why is the shown code O(n · k log k) rather than O(n²)?

3. A learner writes key = sorted(w) without the "".join. What happens when the function runs on ["eat", "tea"]?

Score 60% or more and the lesson is marked complete.