Group words that are anagrams of each other using a sorted-key dictionary in O(n·k log k). A classic Python interview question with live tests.
The problem
Group the words that are anagrams of each other. Return a list of groups.
The order of the groups, and of words inside a group, does not matter.
Examples
Example 1
Input
group_anagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat'])
Expected output
[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
Example 2
Input
group_anagrams(['a'])
Expected output
[['a']]
+ 3 hidden tests on Submit — empty strings are anagrams.
Edge cases to ask about
- Empty list
- Empty strings
- Single word
Hints
0/3How an interviewer scores this
0/9Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.
Complexity Lab
What does this cost as n grows?
Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and measure your code against the optimal one at growing input sizes.
Pick both to reveal the answer.
Measure it
Runs the function on inputs of size 250 up to 16,000 and records the time and peak memory. Slow solutions stop early — a short curve is itself the answer.
From brute force to optimal
The progression an interviewer wants to hear, one step at a time.
| Approach | Time | Space | Idea |
|---|---|---|---|
| Compare with each existing group | O(n²·k log k) | O(n·k) | Every word is compared against every group. |
| Sorted word as dict key | O(n·k log k) | O(n·k) | All anagrams sort to the same key. |
| bestLetter-count tuple as key | O(n·k) | O(n·k) | A 26-length count tuple avoids the sort. |
Walkthrough of the optimal approach (try it yourself first)
All anagrams share the same sorted letters: "eat", "tea" and "ate" all become "aet". Use that as a dict key and append each word to its group.
For lowercase English you can replace the sort with a 26-slot count tuple, dropping the log k factor.
Complexity: O(n·k log k) time, O(n·k) space. Each of the n words (length up to k) is sorted to build its key; all words are stored once in the groups.
Reveal the reference solution
def group_anagrams(words): groups = {} for w in words: key = "".join(sorted(w)) groups.setdefault(key, []).append(w) return list(groups.values())
The brute force, for comparison
def group_anagrams(words): groups = [] for w in words: for g in groups: if sorted(g[0]) == sorted(w): g.append(w) break else: groups.append([w]) return groups
Follow-ups interviewers ask
- Use a count-tuple key instead of sorting.
- Return only groups with more than one word.
Frequently asked interview questions
Core interview concepts, complexities, and follow-ups scored by hiring teams.
What is the time complexity of Group Anagrams Together in Python?
The optimal solution runs in O(n·k log k) time and O(n·k) auxiliary space. Each of the n words (length up to k) is sorted to build its key; all words are stored once in the groups.
What is the brute-force approach, and how do you optimise it?
Compare with each existing group: O(n²·k log k) time, O(n·k) space. Every word is compared against every group. Sorted word as dict key: O(n·k log k) time, O(n·k) space. All anagrams sort to the same key. Letter-count tuple as key: O(n·k) time, O(n·k) space. A 26-length count tuple avoids the sort.
What follow-up questions do interviewers ask about Group Anagrams Together?
Use a count-tuple key instead of sorting. Return only groups with more than one word.