Group Anagrams

Medium#49counting

You get a list of words. Put them into groups so that each group holds the words made of the same letters, only in a different order. Our example: [arc, stop, car, pots, rat, tops] — three groups: [arc, car], [stop, pots, tops] and [rat].

49 Group AnagramsWalkthrough · 1×

Example: words [arc, stop, car, pots, rat, tops]. A word's key is its letters in alphabetical order; the map keeps one group per key.

0arc1stop2car3pots4rat5topsgroupskey → words—
not reached yetcurrent word and its keyin a groupthe answer

Start with an empty map: no groups yet

01/29
restart · back · play · step
Speed
1function groupAnagrams(words):
2 groups = empty map
3 for each word in words:
4 key = sort(word)
5 if key not in groups:
6 groups[key] = empty list
7 add word to groups[key]
8 return values of groups
state
word
–
key
–
groups
{}
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Anagrams have the same letters in another order. Put the letters in alphabetical order and all anagrams turn into one string: "arc" and "car" both become "acr". That string is the key.
  2. The map finds the group of a key at once, so one pass over the words is enough: no word is compared with every other.
  3. A word whose key is new opens its own group. "rat" has no anagram here, so its group holds it alone.

Complexity

Time O(n · k log k): n words, and the letters of each word, k of them, are sorted. Counting the 26 letters instead of sorting makes the key in O(k). Memory O(n · k): every word goes into the map once.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.