Complexity Analysis
def group_anagrams(words):
groups = {}
for w in words:
key = tuple(sorted(w))
groups.setdefault(key, []).append(w)
return list(groups.values())What is the time and space complexity?
Work it out before scrolling down.
Time
O(n × k log k)
Space
O(n × k)
How to derive it
n words, each of average length k. Sorting each word is O(k log k), done n times → O(n × k log k). The dict stores all n words (total characters = n × k). The sorting dominates — if you used a character count instead of sorting, you'd get O(n × k).