Group Anagrams

Problem

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input: strs = [""]
Output: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]

Constraints:

1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] consists of lowercase English letters.

Solution

Approach: Hash Map with Sorted Key

The key insight is that anagrams, when sorted, produce the same string. For example, “eat”, “tea”, and “ate” all become “aet” when sorted. We can use this sorted string as a key in a hash map, where the value is a list of all strings that produce that sorted key.

Implementation

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = {}

        for s in strs:
            # Sort the string to use as key
            key = ''.join(sorted(s))

            if key not in anagrams:
                anagrams[key] = []

            anagrams[key].append(s)

        return list(anagrams.values())

Alternative (Using defaultdict):

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = defaultdict(list)

        for s in strs:
            key = ''.join(sorted(s))
            anagrams[key].append(s)

        return list(anagrams.values())

Alternative (Character Count as Key):

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = defaultdict(list)

        for s in strs:
            # Use character count as key (26 letters)
            count = [0] * 26
            for c in s:
                count[ord(c) - ord('a')] += 1

            # Convert list to tuple (lists can't be dict keys)
            key = tuple(count)
            anagrams[key].append(s)

        return list(anagrams.values())

Complexity Analysis

Time Complexity: O(n × k log k), where n is the number of strings and k is the maximum length of a string. We iterate through all strings (O(n)) and sort each one (O(k log k)). The character count approach is O(n × k) since counting is linear.
Space Complexity: O(n × k) to store all strings in the hash map.

Key Insights

Sorted String as Key: Anagrams share the same sorted representation, making it a perfect hash map key for grouping.
defaultdict Convenience: Using defaultdict(list) eliminates the need to check if a key exists before appending, making the code cleaner.
Character Count Alternative: For very long strings, using a character frequency array as the key can be more efficient than sorting (O(k) vs O(k log k) per string).
Tuple for Hash Key: Lists can’t be used as dictionary keys in Python, so we convert the character count array to a tuple.
One Pass Solution: We only need to iterate through the array once, building the groups as we go. The grouping happens naturally through the hash map structure.