Group Anagrams

Difficulty: Medium

Problem

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

Example

Input: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
Explanation: Strings that are anagrams of each other are grouped together.

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)