Group Anagrams Problem Solution | LeetCode 49

The Group Anagrams problem requires organizing strings into groups where each group contains anagrams of each other. This classic problem tests understanding of hash tables, string manipulation, and algorithmic efficiency in technical interviews.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. What is the expected size of the input array? Are we dealing with small arrays (≤ 100 elements) or potentially large ones (up to 10⁴ elements)?
2. Can the input strings contain duplicates? Should we group identical anagrams together or treat them as separate?
3. What is the expected return format? Should we return a list of lists, or can we return a map from sorted string to list of anagrams?
4. Are we allowed to mutate the input array, or must we preserve it?
5. What is the target time complexity for follow-up? Should we aim for O(n) or O(n log n) where n is the number of strings?

Restate the pattern or problem type in your own words: The group anagrams problem asks us to take a collection of strings and organize them into groups where each group contains all anagrams of one another. An anagram is a word formed by rearranging the letters of another word using all the original letters exactly once.

Clarify the signal words and constraint shape that point to it:

• "Group" or "categorize" - signals classification by some property
• "Anagrams" - specific relationship between elements (letter rearrangement)
• "Same letters, different order" - indicates we need to normalize or canonicalize the strings
• "Multiple strings" - suggests we're working with collections, not individual elements

Note any assumptions you are making:

• Input strings consist only of lowercase English letters (this is a common assumption in coding interviews)
• The problem asks for grouping, not counting or filtering
• We can use string sorting as a canonical representation

Identify whether the pattern is best suited for static, streaming, or online scenarios: This pattern is best suited for static scenarios where we have all the input data upfront. The grouping operation requires a complete view of all strings to form proper groups, making it unsuitable for streaming or online processing where elements arrive one at a time. For streaming scenarios, we'd need a more complex data structure like a hash table with dynamic grouping capabilities.

2. When to Use This Pattern

Signal words and constraint shapes:

• "Group" or "categorize" items that share a common property
• "Anagrams" - words with same letters but different arrangement
• Input consists of string elements that can be transformed or compared
• Need to identify equivalence classes based on character composition

Why this pattern fits better than alternatives: This pattern is ideal when we need to partition data into equivalence classes where the equivalence relation is based on character frequency or sorted character sequences. Compared to brute force O(n²) comparisons, this approach leverages hashing for O(n) grouping. Unlike sorting-based approaches that require O(n log n) total time, the hash-based grouping achieves linear time complexity.

Conditions where variations apply:

• If we only need to identify if two strings are anagrams, use character frequency counting (O(n) time)
• If we're working with streams of data where we can't store all items, use streaming hash maps or rolling hash techniques
• If the problem requires grouping by multiple criteria (e.g., anagrams AND same length), we'd need composite keys or multi-level grouping

Core insight: The key insight is that anagrams are strings with identical character frequencies. By normalizing each string (e.g., sorting characters or counting character frequencies) into a canonical form, we can use that normalized form as a hash key to group all anagrams together in O(1) average lookup time. This transforms the problem from a combinatorial comparison challenge into a simple hashing and grouping operation.

This pattern works particularly well when we have a bounded set of possible inputs (like lowercase English letters) and can efficiently compute a deterministic canonical representation for each item.

3. Approach Evolution

Interview communication script:

My first instinct is to use a brute force approach where I compare every string with every other string to check if they're anagrams, but that's O(n²) time complexity because for each string I'd have to compare it with all others. Let me think about how to optimize this.

I notice that if I sort the characters of each string, anagrams will have identical sorted forms. So instead of comparing strings directly, I can normalize each string by sorting its characters and then group strings that have the same normalized form. This reduces the problem to a simple grouping operation.

If I maintain a map from sorted string to list of original strings, I can process each string once and add it to the appropriate group. This gives me O(n * m log m) where n is the number of strings and m is the average string length, because I sort each string once.

The key insight is that anagrams have identical character frequencies, so sorting the characters makes all anagrams become identical strings. This allows me to use a hash map for grouping in linear time.

Brute-force approach and why it is not ideal:

The brute force approach would involve comparing every string with every other string to check if they're anagrams. For each pair of strings, I'd need to verify that they contain the same characters with the same frequencies. This requires O(m) time for each comparison where m is the string length, and since I have to compare each of the n strings with all others, that's O(n² × m) time complexity. This is inefficient for large inputs and doesn't scale well.

Improved approach and the key optimization:

The key optimization is to normalize each string by sorting its characters. When two strings are anagrams, their sorted character sequences will be identical. This allows me to use a hash map where:

• Key: sorted string (normalized form)
• Value: list of original strings that match this normalized form

By normalizing each string once and using the sorted version as a key, I can group all anagrams in a single pass through the input. This reduces the problem from O(n²) comparisons to O(n × m log m) time where n is string count and m is average string length.

Final approach with step-by-step reasoning:

1. For each string in the input array, I create a normalized version by sorting its characters
2. I use this sorted string as a key in a hash map where the value is a list of original strings that normalize to this key
3. I iterate through all input strings once, normalizing each and adding it to the appropriate group in the hash map
4. Finally, I collect all groups from the hash map to form the result

The invariants that must hold:

• All strings that are anagrams will have identical normalized forms (sorted characters)
• Each string is processed exactly once
• The grouping operation maintains the original strings in their respective groups

Important invariants that must hold:

• Normalized keys are identical for all anagrams in a group
• Each original string appears in exactly one group
• The grouping preserves the relative order of strings within each anagram group

4. Data Structure Choice

For the group anagrams problem, I need to carefully select data structures that support efficient grouping and lookup operations.

Primary Data Structures:

1. HashMap<String, List> - This is the core data structure for grouping anagrams. The key is the sorted version of each string (which serves as a canonical representation for anagrams), and the value is a list of original strings that belong to this group. This allows O(1) average lookup and insertion operations.

2. ArrayList - Used as the value type in the HashMap to store all anagrams that share the same sorted key.

Why Each Data Structure Is Needed:

The HashMap is essential because it provides the most efficient way to group elements by a common property (anagrams having identical sorted forms). Without it, I'd need to scan through all previously seen strings to find matches, resulting in O(n²) complexity.

The ArrayList is needed because each group can contain multiple anagrams, and I need to maintain the original strings in their respective groups.

Time and Space Impact:

• Time: HashMap operations are O(1) average case, so the overall solution is O(nmlog(m)) where n is the number of strings and m is the average string length
• Space: O(n*m) for storing all input strings in the groups

Helper Structure:

I don't need any additional helper structures beyond the HashMap itself. The sorting operation is done in-place on character arrays, which is efficient and doesn't require additional storage beyond what's needed for the sorting algorithm.

The choice of HashMap with sorted strings as keys is optimal because it naturally handles the grouping requirement while maintaining efficient access patterns for both insertion and retrieval operations.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step by step.

Example Input: ["eat", "tea", "tan", "ate", "nat", "bat"]

Step 1: Process first word "eat"

• Sort characters: ['a', 'e', 't'] → "aet"
• Hash map lookup: "aet" not found
• Add to map: map["aet"] = ["eat"]

Step 2: Process second word "tea"

• Sort characters: ['a', 'e', 't'] → "aet"
• Hash map lookup: "aet" exists
• Append to existing list: map["aet"] = ["eat", "tea"]

Step 3: Process third word "tan"

• Sort characters: ['a', 'n', 't'] → "ant"
• Hash map lookup: "ant" not found
• Add to map: map["ant"] = ["tan"]

Step 4: Process fourth word "ate"

• Sort characters: ['a', 'e', 't'] → "aet"
• Hash map lookup: "aet" exists
• Append to existing list: map["aet"] = ["eat", "tea", "ate"]

Step 5: Process fifth word "nat"

• Sort characters: ['a', 'n', 't'] → "ant"
• Hash map lookup: "ant" exists
• Append to existing list: map["ant"] = ["tan", "nat"]

Step 6: Process sixth word "bat"

• Sort characters: ['a', 'b', 't'] → "abt"
• Hash map lookup: "abt" not found
• Add to map: map["abt"] = ["bat"]

Final Map State:

"aet" → ["eat", "tea", "ate"]
"ant" → ["tan", "nat"]
"abt" → ["bat"]

Result: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

The algorithm correctly groups all anagrams together by using sorted character sequences as keys, ensuring that words with identical characters will always map to the same key regardless of their original order.

The algorithm terminates correctly because:

1. Each string is processed exactly once
2. The hash map operations are O(1) average case
3. All strings are accounted for in the final result
4. The grouping is mathematically sound since anagrams have identical character frequencies

6. Java Solution

import java.util.*;

public class GroupAnagrams {
    public List<List<String>> groupAnagrams(String[] strs) {
        // Handle edge case of null or empty input
        if (strs == null || strs.length == 0) {
            return new ArrayList<>();
        }
        
        // HashMap to store groups of anagrams
        // Key: sorted string representation of an anagram group
        // Value: list of original strings that are anagrams of each other
        Map<String, List<String>> anagramGroups = new HashMap<>();
        
        // Process each string in the input array
        for (String str : strs) {
            // Create a sorted version of the string to use as key
            String sortedStr = getSortedString(str);
            
            // Add current string to its anagram group
            anagramGroups.computeIfAbsent(sortedStr, k -> new ArrayList<>()).add(str);
        }
        
        // Return all groups as a list of lists
        return new ArrayList<>(anagramGroups.values());
    }
    
    /**
     * Helper method to create a canonical representation of a string
     * by sorting its characters alphabetically.
     * This ensures that all anagrams will have the same canonical form.
     */
    private String getSortedString(String str) {
        // Convert string to character array for sorting
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        
        // Return sorted characters as a new string
        return new String(chars);
    }
}

This solution uses a hash map to group anagrams by their sorted character representation. For each input string, we create a canonical form by sorting its characters, then use that as a key to group all anagrams together. The time complexity is O(n * m log m) where n is the number of strings and m is the average string length, with space complexity O(n * m).

7. Complexity Analysis

Time Complexity: O(N × M × log M) where N is the number of strings and M is the average length of each string.

• For each string, we need to sort its characters, which takes O(M × log M) time
• We process N strings, so the total time is O(N × M × log M)
• The sorting dominates the overall complexity

Space Complexity: O(N × M) where N is the number of strings and M is the average length of each string.

• We store all input strings in the result map, requiring O(N × M) space
• The sorted string representation uses O(M) space per string
• In the worst case, we may have up to N distinct groups, so space complexity is O(N × M)

Why these bounds are correct:

The time complexity analysis accounts for the fact that we process each string exactly once and perform sorting operations on each string's characters. Since sorting is the most expensive operation, it determines the overall complexity.

The space complexity considers both the storage of input strings in our grouping structure and the temporary space needed for sorting operations. The space required grows linearly with the total amount of input data.

Is this optimal?

Yes, this is near-optimal for the general case. The O(N × M × log M) complexity is optimal for comparison-based sorting approaches. A more advanced solution using character counting (O(N × M)) exists but requires more complex implementation and is not significantly better in practical scenarios. The current solution's trade-off of simplicity versus slightly worse time complexity is reasonable for most production systems.

The solution is optimal in terms of algorithmic approach - we must examine each string at least once to determine grouping, and we must sort characters to identify anagrams. No better approach exists for this specific problem without additional constraints.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty array: Handle gracefully with empty result list
• Single string: Should return list containing that single anagram group
• Empty string: Valid input that should be handled correctly

Duplicate Values and Repeated States

• Duplicate strings: Multiple identical strings should be grouped together
• Same anagram strings: Different orderings of same characters must be grouped
• Case sensitivity: "abc" and "ABC" are treated as different groups (not anagrams)

Boundary Conditions

• Single character strings: Each string forms its own group
• Very long strings: Performance depends on sorting/hash computation cost
• Large input size: Memory usage for hash maps and string operations

Common Implementation Mistakes

• Incorrect grouping logic: Using character frequency comparison incorrectly or missing edge cases in frequency counting
• Mutating input: Modifying the original array when it should remain immutable (if constraints allow)
• Wrong hash key generation: Not properly normalizing strings for comparison (e.g., not sorting characters consistently)
• Memory leaks: Not clearing temporary data structures properly in large-scale processing
• String operations overhead: Repeatedly creating new strings instead of using efficient character array manipulation or precomputed hash values

The most critical pitfall is assuming that anagrams must have identical character frequencies without properly accounting for string normalization or using incorrect hash functions that don't distinguish between truly different anagram groups.

9. Alternative Approaches

There are several alternative approaches to solving the group anagrams problem, each with different trade-offs:

1. Sorting Approach (Alternative to Primary Solution) Instead of using character frequency maps, we can sort the characters in each string and use the sorted string as a key. For example, "eat" becomes "aet", "tea" becomes "aet", and "ate" becomes "aet". All strings that are anagrams will have the same sorted key.

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> groups = new HashMap<>();
    
    for (String str : strs) {
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        String sorted = new String(chars);
        
        groups.computeIfAbsent(sorted, k -> new ArrayList<>()).add(str);
    }
    
    return new ArrayList<>(groups.values());
}

Trade-offs: This approach has O(n * m log m) time complexity where n is the number of strings and m is the average string length. It's simpler to implement but less efficient than the character frequency approach for large strings.

2. Prime Product Approach Assign prime numbers to each letter (a=2, b=3, c=5, etc.) and compute the product of primes for each string. Anagrams will have identical products.

public List<List<String>> groupAnagrams(String[] strs) {
    int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
    Map<Long, List<String>> groups = new HashMap<>();
    
    for (String str : strs) {
        long product = 1;
        for (char c : str.toCharArray()) {
            product *= primes[c - 'a'];
        }
        groups.computeIfAbsent(product, k -> new ArrayList<>()).add(str);
    }
    
    return new ArrayList<>(groups.values());
}

Trade-offs: This approach has O(n * m) time complexity but risks integer overflow for very long strings. It's elegant but not robust for all inputs.

3. Trie-Based Approach Build a trie structure where each node represents a character and paths represent strings. Group anagrams by traversing the trie in a way that considers character frequencies.

Trade-offs: This approach is more complex to implement and has higher space overhead. It's not typically preferred for this problem due to its complexity.

The primary solution using character frequency maps is preferred because it's intuitive, efficient, and handles all edge cases robustly without overflow or complexity concerns.

10. Test Cases

import java.util.*;

public class GroupAnagramsTestCases {
    public static void main(String[] args) {
        // Test case 1: Basic example
        String[] input1 = {"eat", "tea", "tan", "ate", "nat", "bat"};
        // Expected: [["eat","tea","ate"], ["tan","nat"], ["bat"]]
        
        // Test case 2: Empty array
        String[] input2 = {};
        // Expected: []
        
        // Test case 3: Single element
        String[] input3 = {"abc"};
        // Expected: [["abc"]]
        
        // Test case 4: All anagrams
        String[] input4 = {"abc", "bca", "cab", "acb"};
        // Expected: [["abc","bca","cab","acb"]]
        
        // Test case 5: Mixed with empty string
        String[] input5 = {"", "b", ""};
        // Expected: [["",""], ["b"]]
        
        // Test case 6: Case sensitivity
        String[] input6 = {"Abc", "bCa", "CBA"};
        // Expected: [["Abc"], ["bCa"], ["CBA"]]
        
        // Test case 7: Duplicates in input
        String[] input7 = {"eat", "tea", "eat", "ate"};
        // Expected: [["eat","tea","eat","ate"]]
    }
}

Sample test cases include:

• Basic functionality with mixed anagrams
• Edge case of empty input array
• Single element arrays
• All strings that are anagrams of each other
• Empty string handling
• Case sensitivity considerations
• Duplicate strings in input

The key test cases verify that anagram grouping works correctly for various scenarios including edge conditions and boundary values.

11. Final Summary

The core idea is to group anagrams by sorting each string's characters and using the sorted version as a hash key. This approach works because anagrams will always produce identical sorted strings, allowing us to efficiently bucket them together in linear time.

The solution is efficient because it leverages a hash map for O(1) average lookup and insertion operations, while the sorting step is bounded by the maximum string length. The approach is optimal for the static grouping problem, with O(n×m log m) time complexity where n is the number of strings and m is the maximum string length, which matches the theoretical lower bound for this problem.

What makes this solution particularly strong is its simplicity and robustness - it handles all edge cases naturally, works with any character set, and scales linearly with input size while maintaining clean separation of concerns between the grouping logic and the sorting operation.