Difficulty: Medium | Asked at: Amazon, Meta, Uber
Given an array of strings, group the anagrams together.
Input: ["eat","tea","tan","ate","nat","bat"]
Output: [["eat","tea","ate"],["tan","nat"],["bat"]]
💡 Hint: Two words are anagrams if and only if their sorted characters are identical. That sorted string makes a perfect hash key.
Solution:
python
from collections import defaultdict
def group_anagrams(strs):
groups = defaultdict(list)
for s in strs:
key = ''.join(sorted(s))
groups[key].append(s)
return list(groups.values())
Complexity: O(n · k log k) time, where n is the number of strings and k is the max string length - sorting each string dominates. Space O(n · k).
Common mistake: Trying to compare every pair of strings directly (O(n²) comparisons) instead of using a canonical key to bucket them in one pass. Any time you see "group things that share a property," ask: "what's the key I can compute once per item?"
Bonus optimization: instead of sorting (O(k log k)), you can build a character-count tuple as the key in O(k) time - faster for long strings. Worth mentioning if you want to show extra depth.
Sorted-string-as-key or character-count-as-key - which would you reach for first? 👇