Group Anagrams

Difficulty: Medium

Problem

You are given a list of words. Put together the words made of exactly the same letters (rearrangements of one another) into the same bucket, and return the buckets. The buckets may come back in any order.

Example

Input: strs = ["stop", "pots", "tops", "opts", "car", "arc", "sun"]
Output: [["stop", "pots", "tops", "opts"], ["car", "arc"], ["sun"]]
Explanation: Words that are rearrangements of each other share a group; "sun" has no partner, so it is alone.

Brute-force approach

Compare every pair of words to check if they're anagrams. Group matching words together.

Steps

  1. Pick a word (mark as used)
  2. Compare it with every other unused word
  3. If anagrams → put them in the same group
  4. Repeat for next unused word

Time complexity: O(n² × k log k) · Space complexity: O(n)

Trade-offs

  • Quadratic comparisons: comparing every pair is O(n²)
  • Repeated sorting: we sort strings multiple times
  • TLE (Time Limit Exceeded) for large inputs

Optimal approach

Key insight: When you sort 'eat', 'tea', 'ate', they all become 'aet': the same key for all anagrams!

Use a HashMap with a unique 'signature' as the key. All anagrams share the same signature!

Steps

  1. Create an empty HashMap: key → list of words
  2. For each word, generate a unique key (sorted or frequency)
  3. Add the original word to that key's list
  4. Return all the lists (values) from the HashMap

Time complexity: O(n × k log k) · Space complexity: O(n × k)

Pseudocode

function groupAnagrams(strs):
    create empty hashmap (sorted_key -> list of words)
    
    for each word in strs:
        key = sort characters of word
        add word to hashmap[key]
    
    return all values from hashmap

Hints

  • What's unique about anagrams when you sort their characters?
  • Use the sorted string as a key to group words

Complexity questions

Time to compare all pairs of n strings, checking anagram by sorting (k = word length)?

O(n² × k log k). O(n²) pairs × O(k log k) sorting per comparison = O(n² × k log k)

Time with HashMap + sorted key approach (n strings, k length)?

O(n × k log k). n strings × O(k log k) to sort each = O(n × k log k)

Time with HashMap + frequency key approach (n strings, k length)?

O(n × k). n strings × O(k) to count characters = O(n × k), faster than sorting!

Check your understanding of Group Anagrams

What does 'group anagrams' mean?

Put words that are anagrams of each other together. We need to group words that are anagrams of each other into the same group.

Given ['eat', 'tea', 'tan', 'ate', 'nat', 'bat'], how many groups are there?

3 groups. Three groups: ['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']

What identifies words as belonging to the same group?

Same character frequencies (anagrams). Words with the same character frequencies (same letters appearing same number of times) are anagrams.

Related problems

Keep practising