Group Anagrams: Hash Map Grouping Pattern

Group Anagrams is one of the most popular medium-difficulty problems on LeetCode, and for good reason. It is a clean, practical introduction to the grouping hash map pattern. If you have already solved Two Sum and Contains Duplicate, this is the natural next step. Same data structure, different trick.

Let's break it down.

The problem

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

Two strings are anagrams if they contain the exact same characters in the exact same frequencies, just rearranged. "eat" and "tea" are anagrams. "eat" and "bat" are not.

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

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

The question is: how do you efficiently figure out which words belong together?

The brute force approach

The most obvious way: for each word, compare it against every other word and check if they are anagrams. Two words are anagrams if sorting both gives the same result. That comparison is O(k log k) where k is the word length, and you do it for every pair of words, giving you O(n^2 * k log k).

That is way too slow for large inputs. And it is unnecessarily complicated. There is a much simpler way to think about this.

The key insight

Here is the trick: if you sort the characters of a word, all anagrams produce the exact same sorted string. "eat" becomes "aet". "tea" becomes "aet". "ate" becomes "aet". That sorted string is a canonical key that uniquely identifies the anagram group.

So the algorithm is:

1. For each word, sort its characters to get a key
2. Use that key to look up (or create) a group in a hash map
3. Append the original word to that group
4. Return all the groups

One pass through the array. One hash map. Done.

Visual walkthrough

Let's trace through ["eat", "tea", "tan", "ate", "nat", "bat"] step by step. Watch how each word gets sorted into a key, and how the hash map groups them automatically.

That is the whole algorithm. After processing all six words, the map has three entries. The values of the map are our answer.

The code

Here is the clean Python solution:

from collections import defaultdict

def group_anagrams(strs: list[str]) -> list[list[str]]:
    groups = defaultdict(list)
    for word in strs:
        key = "".join(sorted(word))
        groups[key].append(word)
    return list(groups.values())

Let's walk through what each line does:

• groups = defaultdict(list) creates a hash map where missing keys auto-initialize to an empty list. This avoids the "check if key exists, then create" boilerplate.
• key = "".join(sorted(word)) sorts the characters and joins them back into a string. "tea" becomes "aet". This is the canonical key.
• groups[key].append(word) adds the original (unsorted) word to the group for that key. If the key already exists, it appends. If not, defaultdict creates a new list first.
• return list(groups.values()) extracts all the groups. We do not need the keys in the output, just the grouped words.

Alternative: character count key

There is another way to generate the key without sorting. Instead of sorting each word, you count the frequency of each character and use that count as the key:

from collections import defaultdict

def group_anagrams(strs: list[str]) -> list[list[str]]:
    groups = defaultdict(list)
    for word in strs:
        count = [0] * 26
        for ch in word:
            count[ord(ch) - ord('a')] += 1
        key = tuple(count)
        groups[key].append(word)
    return list(groups.values())

This avoids sorting entirely. Instead of O(k log k) per word, the key computation is O(k). For very long words, this is faster. In practice, the difference is negligible since word lengths in interview problems are usually small. But it is worth knowing both approaches.

Complexity analysis

Sorted key approach:

Time: O(n * k log k). We iterate through n words. For each word, sorting its k characters costs O(k log k). The hash map operations (lookup and insert) are O(k) for hashing the key string.

Space: O(n * k). We store every word in the hash map. In the worst case (no anagrams), we have n groups each with one word.

Character count approach:

Time: O(n * k). We iterate through n words. For each word, counting characters is O(k). The hash map operations are O(1) for a fixed-size tuple key (26 elements).

Space: O(n * k). Same as above. The 26-element count tuples add a constant factor.

Both approaches are efficient enough for interview purposes. The sorted key version is easier to explain and write. The count version is technically faster and can be a good follow-up if the interviewer asks for optimization.

Edge cases to watch for

A few things that come up with this problem:

• Empty strings. "" sorted is still "". Multiple empty strings will correctly group together under the key "". No special handling needed.
• Single-character strings. ["a", "a", "b"] groups to [["a", "a"], ["b"]]. The algorithm handles this without any changes.
• All words are anagrams. If every word maps to the same key, you get one big group. The algorithm does not care.
• No anagrams at all. Every word gets its own group. The output has n single-element lists. Still works.

The building blocks

This problem is built from one core building block that shows up in many other problems:

Group-by-key

The act of iterating through a collection, computing a key for each element, and grouping elements that share the same key. The template looks like this:

from collections import defaultdict

groups = defaultdict(list)
for item in collection:
    key = compute_key(item)
    groups[key].append(item)

The only thing that changes between problems is what compute_key does:

• Group Anagrams: compute_key sorts the characters
• Group by first letter: compute_key returns word[0]
• Group by length: compute_key returns len(word)
• Group by frequency: compute_key returns the count of some property

The pattern is always identical. You pick a key function, iterate, and group. Once you have this brick internalized, any "group these items by some property" problem becomes trivial.

Canonical form

The second idea here is canonicalization: transforming different representations of the same thing into a single standard form. "eat", "tea", and "ate" look different, but they are the same set of characters. Sorting them produces the canonical form "aet" that makes the equivalence obvious.

This concept appears beyond anagrams. Checking if two binary trees are mirrors of each other, normalizing paths in a file system, or reducing equivalent graph states all use some form of canonicalization. The core idea is always: find a transformation that maps equivalent inputs to identical outputs.

Problems that use the same bricks

Once you have group-by-key down, try these:

• Valid Anagram: the single-pair version. Just compare sorted strings or character counts directly.
• Group Shifted Strings: same grouping pattern, different key function (shift differences instead of sorted characters)
• Encode and Decode Strings: uses key encoding, a related hash map skill
• Top K Frequent Elements: frequency counting into a hash map, then extracting the top groups

Why you will forget this (and how to fix it)

Group Anagrams feels almost too easy once you see the solution. "Obviously you sort each word and use it as a dictionary key." But the next time you hit a grouping problem with a less obvious key function, you might not make the connection.

The building block here is not "sort the word." It is "compute a canonical key and group by it." That is the abstraction you need to internalize, because the key function changes in every problem but the grouping template stays the same.

Spaced repetition locks this in. You practice typing the group-by-key template from scratch at increasing intervals. After a few cycles, the moment you see a problem that says "group these items by some shared property," the defaultdict pattern fires automatically. You are not searching for the approach. You already know the approach. You just need to figure out the key function.

Related posts

• Hash Map Patterns - Group Anagrams is the canonical example of the grouping pattern, one of the three core hash map techniques
• Two Sum - The complement lookup pattern, another core hash map technique
• Contains Duplicate - The simplest hash set problem, a good warm-up before Group Anagrams