Week 1 · Arrays & Hashing

Group Anagrams

Group words that are anagrams of each other. The core move is choosing a canonical key that identical anagrams share.

Medium Arrays & Hashing Week 1 Practice runner

Frame the problem

Every input string belongs to exactly one group.
Output group order is not important in the interview unless specified.
The key must preserve character multiplicity.

1. Reveal example inputs and outputs

Example 1

Input:

group_anagrams([
  "eat",
  "tea",
  "tan",
  "ate",
  "nat",
  "bat"
])

Output:

[
  [
    "eat",
    "tea",
    "ate"
  ],
  [
    "tan",
    "nat"
  ],
  [
    "bat"
  ]
]

Example 2

Input:

group_anagrams([
  "abc"
])

Output:

[
  [
    "abc"
  ]
]

2. Brute force first

How would you compare each new word with every existing group? What repeated comparison can a canonical key remove?

3. Reveal the insight ladder

Anagrams become identical when sorted by characters.
Use that canonical sorted tuple or string as a hash-map key.
Append each word to the bucket for its key.
Return the buckets as the answer.

4. Dry run before code

eat, tea, and ate all map to aet.
tan and nat map to ant.
bat maps to abt.
The buckets are the anagram groups.

5. Reveal final Python solution

from collections import defaultdict

def group_anagrams(strs):
    groups = defaultdict(list)
    for word in strs:
        groups["".join(sorted(word))].append(word)
    return list(groups.values())

Complexity: Time O(n * m log m) using sorted keys, where m is max word length. Space O(n * m) for grouped output and keys.

Interview narration

The key design is the interview decision.
Sorting is simple and reliable; a 26-count tuple can improve per-word key cost for lowercase letters.
The hash map groups all words sharing the same canonical representation.

Common traps

Using set(word) loses duplicate letters.
Depending on output order when the problem does not require it.
Forgetting the empty string has a valid key.

Follow-up drills

1. How would you avoid sorting every word?

For lowercase English letters, build a 26-count tuple and use it as the key. That changes key creation to O(m).

2. What if the input is a stream?

Keep the hash map open and append each arriving word to its key bucket. You can emit groups at the end or maintain live buckets.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.