49. Group AnagramsMedium

Group Anagrams

MediumArrayHash TableStringSorting·AmazonGoogleMicrosoft

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, 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⁴
0 ≤ strs[i].length ≤ 100
strs[i] consists of lowercase English letters

Hints

Hint 1What makes two strings anagrams of each other?▼

Two strings are anagrams if and only if they contain the exact same characters with the same frequencies. Any transformation that captures this uniquely can serve as a group key.

Hint 2What key uniquely identifies a group of anagrams?▼

Sorting a string always produces the same result for all its anagrams — "eat", "tea", and "ate" all sort to "aet". Use the sorted string as the hash map key. This takes O(k log k) per string where k is the string length.

Hint 3Build the groups using a hash map.▼

Create a defaultdict(list). For each string, compute its sorted key and append the original string to map[key]. After processing all strings, return list(map.values()). Total: O(m · k log k) time, O(m · k) space, where m = number of strings, k = max string length.

Brute Force Approach

O(m² · k log k) Time

🔄

Pairwise Comparison

Time O(m² · k log k)Space O(m)

The naive approach: for every string, compare it against every other string by sorting both and checking equality. Group matched strings together.

1For each string s, scan all other strings and sort both to check if they are anagrams.
2Maintain a visited set to avoid adding the same string to multiple groups.
3This is O(m²) pairs × O(k log k) sort per pair — very slow for large inputs.

def groupAnagrams(strs):
    groups, used = [], [False] * len(strs)
    for i in range(len(strs)):
        if used[i]: continue
        group = [strs[i]]
        for j in range(i + 1, len(strs)):
            if sorted(strs[i]) == sorted(strs[j]):
                group.append(strs[j]); used[j] = True
        groups.append(group)
    return groups

Optimal Approach — Categorize by Sorted String

O(m · k log k) Time

🪣

Hash Map Bucketing

Time O(m · k log k)Space O(m · k)

Two strings are anagrams if and only if their sorted strings are equal. We can iterate over the strings, sort each one to form a guaranteed unique key, and append it to our dictionary.

1Initialize a Hash Map mapping strings to lists defaultdict(list).
2For each string across the list, compute a sorted copy.
3Use the sorted copy as the key and append the original string to the map's value.

*Note: For absolute optimal performance O(m · k), you can count the 26 characters explicitly to act as the tuple key instead of sorting. The logic is structurally identical!

Strings Array strs

Hash Map (Sorted Key → List of Anagrams)

READYPress ▶ or step forward to begin.

✓

—

Strings

Executing Code

def groupAnagrams(strs):

    res = defaultdict(list)

    for s in strs:

        key = "".join(sorted(s))

        res[key].append(s)

    return list(res.values())

Time Complexity Analysis

Building keysO(m · k log k)For each of the m strings, we sort it — sorting a string of length k costs O(k log k). Done once per string.

Hash map opsO(m · k)Each insert and lookup compares a key of length k. Across all m strings this is O(m · k) — dominated by the sort step.

TotalO(m · k log k)Where m = number of strings and k = maximum string length. Space is O(m · k) to store all characters in the map.

Can we do better? Yes — replace the sort with a 26-character frequency count array as the key. Counting 26 letters is O(k) without the log factor, giving a true O(m · k) solution with identical logic structure.

Discussion

…

Loading comments…

LeetMotion