Cracking The Coding Interview Together – Problem 10.2: Group Anagrams

Have you ever stared at a massive array of strings, knowing that hidden relationships bind them together, only to realize that finding those relationships naively will melt your CPU? That is the exact challenge we face when dealing with text transformation problems in distributed systems and search engines. Today, we are tackling a classic algorithmic puzzle that bridges the gap between basic string manipulation and advanced sorting strategies.

As we continue our journey through Cracking the Coding Interview, we encounter Problem 10.2. At first glance, it looks like a simple text-processing task. But as we scale our inputs from a few dozen words to millions of records, our architectural choices make the difference between a system that hums smoothly and one that times out. Let's dive in together and build a robust, production-ready solution.

Problem Statement

Write a method to sort an array of strings so that all the anagrams are next to each other. An anagram is a word or phrase formed by rearranging the letters of a different, using all the original letters exactly once. Our operational goal is to rearrange the given array in-place or return a restructured array where every group of anagrams sits contiguously, without imposing any strict ordering requirements on the individual groups themselves.

Analyze the Problem Together

Let's break down the constraints and find the "Aha!" conflict in this problem. What defines an anagram fundamentally? Two strings are anagrams if and only if their sorted character sequences are identical. For example, "eat", "tea", and "ate" all normalize to the sorted string "aet".

If we look at naive approaches, we might be tempted to compare every single string against every other string using nested loops. That gives us an O(N^2) or O(N^3) time complexity depending on string length, which falls apart instantly at scale. Alternatively, we could generate all possible permutations of every string—an absolute non-starter.

Instead, our architectural choice centers around transformation and hashing. By transforming each string into a canonical representation (its sorted character array), we can group them effectively. We can leverage a hash map to collect anagram buckets, and then dump those buckets back into our array, or we can implement a custom comparator for our sorting algorithm.

Questions for the Interviewer

Before we write a single line of code, a senior engineer always clarifies the operating environment. Here are the questions we would ask:

• Character Set: Are we dealing strictly with ASCII characters, or do we need to support full Unicode and multi-byte UTF-8 characters?
• Case Sensitivity: Are uppercase and lowercase letters treated as distinct (e.g., 'A' and 'a'), or should we normalize case before grouping?
• Input Scale: What is the expected size of the array, and what is the maximum length of an individual string?
• Memory Constraints: Do we have strict memory limits that preclude using an auxiliary hash map, forcing us into an in-place sorting solution?

Think About the Solution

Let's design our high-level architecture. We have two primary paths: a hash-map-based bucketing approach and a custom-comparator sorting approach.

The hash map approach involves iterating through the array, sorting the characters of each string to form a key, and adding the original string to a list mapped to that key. Once processed, we iterate through the map values and rewrite the original array. This runs in O(N * K log K) time where N is the number of strings and K is the maximum length of a string.

The custom comparator approach involves writing a sorting algorithm that uses the sorted string as the comparison key. While cleaner in terms of pure sorting semantics, it can be less efficient because standard sorting algorithms will repeatedly compute sorted keys during comparisons unless we cache them.

Let's build the hash map grouping strategy, as it directly achieves our goal of placing anagrams next to each other while offering optimal average-case performance.

Write Code and Explain

Here is the production-ready Java implementation for grouping anagrams together:

import java.util.Arrays;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class AnagramGrouper {

    /**
     * Sorts an array of strings so that all anagrams are adjacent.
     * 
     * @param array The array of strings to process.
     */
    public void sortAnagrams(String[] array) {
        if (array == null || array.length <= 1) {
            return;
        }

        // Map to hold the canonical sorted string key and its corresponding original strings
        HashMap<String, List<String>> map = new HashMap<>();

        for (String s : array) {
            String sortedKey = sortChars(s);
            map.computeIfAbsent(mapKey -> new ArrayList<>()).add(s);
        }

        int index = 0;
        for (List<String> group : map.values()) {
            for (String s : group) {
                array[index++] = s;
            }
        }
    }

    /**
     * Helper method to sort the characters of a string.
     */
    private String sortChars(String s) {
        char[] content = s.toCharArray();
        Arrays.sort(content);
        return new String(content);
    }
}

Let's walk through what this code does step-by-step:

1. Guard Clauses: We check if the array is null or has one or fewer elements. If so, it's already sorted by definition, and we exit early.
2. Canonical Key Generation: For every string s, we call sortChars(s), which converts the string to a character array, sorts it via Dual-Pivot Quicksort, and rebuilds a new string. This acts as our unique anagram signature.
3. Bucket Collection: We use a HashMap where the sorted string serves as the key. We group matching original strings into an ArrayList.
4. Array Reconstruction: Finally, we iterate through the map's grouped values and overwrite our original array sequentially, ensuring all anagrams sit side-by-side.

Time & Space Complexity

Let's analyze our resource consumption rigorously:

• Time Complexity: O(N * K log K), where N is the number of strings in the array and K is the maximum length of a string. We iterate through N strings, and for each string, we sort its characters which takes O(K log K) time. Map insertions and array reconstruction run in linear time relative to total character volume.
• Space Complexity: O(N * K). We allocate auxiliary memory for our hash map, which stores every original string and its sorted key counterpart. In the worst-case scenario where no strings are anagrams, storage scales directly with total input size.

Why This Problem Matters (The Senior Perspective)

In real-world enterprise architectures, grouping anagrams is not just a theoretical interview trope. It mirrors problems found in duplicate detection, fuzzy search indexing, and NLP data normalization. When dealing with user-generated content—such as tags, product titles, or search queries—typos and character permutations create massive data pollution.

By transforming raw inputs into canonical hash keys, you are effectively implementing a rudimentary feature extractor. In distributed systems, this exact pattern is used in MapReduce jobs to shuffle and group related records across cluster nodes before aggregation.

Final Thoughts

Sorting and grouping problems test your ability to look past brute-force iteration and identify mathematical or structural invariants—in this case, the canonical sorted character representation. Take this solution, experiment with custom comparators, and think about how you would scale this to stream processing architectures.

Keep building, keep questioning, and I'll see you in the next post!