49. Group Anagrams — DSA Atlas

MediumArrays and HashingHash mapCanonical key bucketing

Group Anagrams

Given an array of strings strs, group the strings that are anagrams of one another (same letters with the same multiplicities). Return the groups as a list of lists in any order.

Open official problem prompt ↗

In plain English

Partition the input words into equivalence classes where two words are equivalent if one is a rearrangement of the other.

Picture it like this

Sorting scrambled-letter tiles into labeled trays: you first alphabetize each word's tiles to get a tray label, then drop the original word into the tray with that label.

Example

Input: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
Why: eat/tea/ate share letters a,e,t; tan/nat share a,n,t; bat is alone.

Constraints

1 <= strs.length <= 10^40 <= strs[i].length <= 100strs[i] consists of lowercase English letters

Pattern lesson

See the pattern, then code

Canonical key bucketing

↗

Arrays and Hashing

Duplicates, frequency counts, grouping, membership tests, or pair lookup.. Two words are anagrams exactly when their sorted letters match, so the sorted string is a fingerprint. Use that fingerprint as a dictionary key and append each word to its bucket.

New words, made simpleKnow these before the algorithm

Anagram: A word formed by rearranging the letters of another, using each letter the same number of times.
Canonical key: A normalized representative (here the sorted letters) that is identical for all members of a group.
Bucket: A list collecting all items that share the same key.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Pairwise anagram check

Quadratic in the number of words; wasteful because it recomputes relationships a key would capture once.

Compare every pair of strings to see if they are anagrams and union groups.

Time O(n^2 * k)Space O(n)

Best choiceSorted-string key

Simple and fast; sorting each word of length k dominates. Recommended.

Map each word to the string of its sorted letters and bucket by that key.

Time O(n * k log k)Space O(n * k)

The rule we keep true

Invariant

At every step, two words reside in the same bucket if and only if they have produced the identical canonical key, which happens exactly when they are anagrams.

Why this is correct

Reasoning

Sorting is a canonical function: anagrams have identical multisets of letters, so their sorted forms are byte-for-byte equal, and non-anagrams differ in some letter count and therefore in the sorted form. Equal keys collide into one bucket; unequal keys stay apart.

The algorithm in three movesSay these aloud before coding

1Create an empty map from canonical key to list of words

'eat' -> key 'aet' -> {aet: [eat]}

2For each word, build a canonical key (its sorted characters)

'tea' -> key 'aet' -> {aet: [eat, tea]}

3Append the word to the list under that key

'ate' -> key 'aet' -> {aet: [eat, tea, ate]}

4Return all the map's value lists

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

eat0

tea1

tan2

ate3

nat4

bat5

1 · Readkey 'aet'

2 · AskDoes 'aet' exist?

3 · Update state{}

4 · ResultCreate bucket -> {aet: [eat]}

Key takeaway

eat, tea, and ate all collapse to the key 'aet', landing in the same bucket.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Group map
Maps a canonical key to the running list of matching words.
2
Lines 4-6Key and bucket
sorted(s) returns a list of characters; join makes a hashable string key, and setdefault creates the bucket on first sight.
3
Lines 7Emit groups
The values of the map are exactly the anagram groups.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

The empty string "" forms its own valid group (key is "")
A single-word input returns one group of one
All words identical collapse into a single bucket

Common beginner mistakes

Using the sorted list itself as a key — lists are unhashable, so it must be joined into a string or made a tuple
Assuming a fixed output order; LeetCode accepts any group ordering
Reaching for a character-count key without normalizing format, causing subtle key mismatches

Check your understanding

Instead of sorting, how could you build a key in O(k) rather than O(k log k) per word?

Group Anagrams

Group Anagrams

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Arrays and Hashing