Skip to content

Sorting the Mail Room

Jump to bottom
Andrew Burke edited this page Aug 19, 2026 · 1 revision

TIP103 Unit 11 Session 1 (Click for link to problem statements)

Sorting the Mail Room

The mail room receives a pile of labels and wants to bundle together any labels that are rearrangements of the same letters. Given a list of strings words, group the ones that are anagrams of each other.

Return a list of groups; the order of the groups and the order within each group do not matter.

def group_anagrams(words):
    pass

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-25 mins
  • 🛠️ Topics: Strings, Hash Maps, Anagrams, Sorting

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?

  • Q: What makes two labels belong in the same bundle?

    • A: They are anagrams of each other, meaning they contain exactly the same letters with the same counts, just in a different order (e.g., "eat" and "tea").

  • Q: Does the order of the groups, or the order of words within a group, matter?

    • A: No. Any ordering of the groups and any ordering within each group is accepted.

  • Q: Can the same word appear more than once in words?

    • A: Yes. Duplicate words are anagrams of each other, so all copies belong in the same group.
HAPPY CASE
Input: words = ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
Explanation: "eat", "tea", and "ate" all use the letters a, e, t. "tan" and "nat" use a, n, t. "bat" shares its letters with no other label, so it forms a group by itself.

EDGE CASE
Input: words = []
Output: []
Explanation: With no labels to bundle, there are no groups.

Input: words = ["bat"]
Output: [['bat']]
Explanation: A single label forms its own group of one.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Grouping / Categorization Problems, we can consider the following approaches:

  • Hash Map with a Canonical Key: Map each word to a signature that is identical for all of its anagrams, and collect words that share a signature. Sorting a word's letters produces such a signature ("eat", "tea", and "ate" all sort to "aet").
  • Frequency-Count Key: Alternatively, a tuple of 26 letter counts can serve as the signature, avoiding the sort at the cost of a bulkier key.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Two words are anagrams exactly when their letters, sorted alphabetically, are identical. Build a dictionary that maps each sorted-letter signature to the list of words that produce it. Every word in words gets sorted, looked up, and appended to its bucket. The dictionary's values are the anagram groups.

1) Create an empty dictionary `groups` mapping signature -> list of words.
2) For each `word` in `words`:
   a) Compute the signature by sorting the letters of `word` and joining them into a string.
   b) If the signature is not yet a key in `groups`, add it with an empty list.
   c) Append `word` to the list at that signature.
3) Return the lists stored in `groups` as the final answer.

⚠️ Common Mistakes

  • Using sorted(word) (a list) directly as a dictionary key — lists are unhashable, so join it into a string or convert it to a tuple first.
  • Comparing every pair of words with a nested loop, which turns an O(N) pass into O(N^2) anagram checks.
  • Returning the dictionary itself instead of its values — the problem asks for a list of groups.

4: I-mplement

Implement the code to solve the algorithm.

def group_anagrams(words):
    groups = {}
    for word in words:
        # Words that are anagrams share the same sorted letters
        key = "".join(sorted(word))
        if key not in groups:
            groups[key] = []
        groups[key].append(word)
    return list(groups.values())

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Input: words = ["eat", "tea", "tan", "ate", "nat", "bat"]

    • "eat" → key "aet", groups = {"aet": ["eat"]}
    • "tea" → key "aet", groups = {"aet": ["eat", "tea"]}
    • "tan" → key "ant", groups = {"aet": ["eat", "tea"], "ant": ["tan"]}
    • "ate" → key "aet", groups = {"aet": ["eat", "tea", "ate"], "ant": ["tan"]}
    • "nat" → key "ant", groups = {"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"]}
    • "bat" → key "abt", groups = {"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"]}
    • Output: 'eat', 'tea', 'ate'], ['tan', 'nat'], ['bat'

  • Input: words = []

    • The loop never runs, so groups stays empty.
    • Output: []

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of words and K is the length of the longest word.

  • Time Complexity: O(N * K log K) because each of the N words is sorted in O(K log K) time to build its signature; dictionary insertions and lookups are O(K) on average.
  • Space Complexity: O(N * K) to store every word (and its signature key) in the dictionary.

Using a 26-letter frequency-count tuple as the key would drop the per-word cost to O(K), giving O(N * K) overall time at the expense of slightly more bookkeeping.

Clone this wiki locally