Faangprep Logo
Log inStart free
Browse curriculum

Group Anagrams

Group words that are anagrams of each other, using each word's sorted letters as a hash map key.

MediumSolve on LeetCode

Problem Understanding

Group Anagrams: given an array of strings strs, group the words that are anagrams of each other. The groups, and the words inside them, may be returned in any order.

Example: ["eat", "tea", "tan", "ate", "nat", "bat"] returns [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]].

Attempt 1: Compare Every Pair

For each word not yet grouped, compare it with every later word using an anagram check and pull the matches into its group. That is O(n²) anagram checks. The pairwise comparison is the waste: if each word could be turned into a label that all of its anagrams share, words could be sorted into buckets directly.

The Intuition: A Key Every Anagram Shares

Sort a word's letters and every anagram of it produces the same string: "eat", "tea" and "ate" all sort to "aet". Use that string as a hash map key:

  1. For each word, compute key = sorted(word).
  2. If key is new, start an empty list for it.
  3. Append the word to key's list.

One pass, no pairwise comparisons — the map does the matching. It is the same counting idea as Valid Anagram, turned into a key.

Interactive Walkthrough

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

START

eat

tea

tan

ate

nat

bat

groups (key → words)

empty

Key

—

Groups

0

 

groups starts empty: each key will map to the list of words that share it

Next

"eat" sorts to "aet" — every anagram of "eat" sorts to the same key

Words

The words run along the top with each one's sorted key under it. Below them, the map: one row per key, collecting its words as they arrive. Watch "tea" and "ate" land in the row "eat" started.

The approach, step by step

  1. Make a key

    Sort the letters of each word; all anagrams of a word sort to the same string.

  2. Group by key

    If the key is new, start an empty list for it; then append the word to its key's list.

  3. Return the groups

    Return the lists stored in the map, in any order.

Frequently asked questions

How do you group anagrams together?

Give every word a key that all of its anagrams share, such as its letters sorted. Store a hash map from key to a list of words, append each word to its key's list, and return the lists.

What is the time complexity of Group Anagrams?

Sorting each word's letters costs O(k log k) for a word of length k, done for n words: O(n · k log k) time. The map holds every word once, so O(n · k) space.

Is there a key that avoids sorting?

Yes. Count the 26 letters of each word and use the counts as the key. Building it is O(k) per word, so grouping takes O(n · k) time, at the cost of a longer key.