Group Anagrams

mediumArrays & Hashing34 stepsJava · Python · C++

Group words that are anagrams of each other. Sorting a word's letters gives a key that all its anagrams share, so a map from sorted key to list of words collects the groups in one pass.

▶ Watch the animated trace

Traced input: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] → [["eat", "tea", "ate"], ["bat"], ["tan", "nat"]]. Original problem: neetcode.io/problems/anagram-groups

Complexity

BestO(n·k log k)

AverageO(n·k log k)

WorstO(n·k log k)

SpaceO(n·k)

n words of length up to k. A 26-count key makes it O(n·k).

Key idea

Anagrams become identical after sorting their letters: "eat", "tea", "ate" → "aet".
Use that sorted string as a HashMap key; the value is the list of words in that group.
computeIfAbsent creates the list the first time a key appears.

Common mistakes

Using char[] directly as the key: arrays use identity hashing, so nothing groups.
Building the count-key as "1112" without separators can collide; use '#' between counts.
Assuming the output order matters; any order is accepted.

Solution

Java

List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> groups = new HashMap<>();
    for (int i = 0; i < strs.length; i++) {
        char[] c = strs[i].toCharArray();
        Arrays.sort(c);
        String key = new String(c);
        groups.computeIfAbsent(key, k -> new ArrayList<>()).add(strs[i]);
    }
    return new ArrayList<>(groups.values());
}

Python

def groupAnagrams(strs: List[str]) -> List[List[str]]:
    groups = defaultdict(list)
    for s in strs:
        key = "".join(sorted(s))
        groups[key].append(s)
    return list(groups.values())

C++

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> groups;
    for (const string& s : strs) {
        string key = s;
        sort(key.begin(), key.end());
        groups[key].push_back(s);
    }
    vector<vector<string>> res;
    for (auto& [key, words] : groups) res.push_back(words);
    return res;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
One empty string The empty string sorts to "" and forms its own group.	`strs = [""]`	`[[""]]`
Single word One group with one word.	`strs = ["a"]`	`[["a"]]`
No anagrams at all Every word gets its own key.	`strs = ["abc", "def"]`	`[["abc"], ["def"]]`
Duplicate words Duplicates are kept; they land in the same group.	`strs = ["ab", "ba", "ab"]`	`[["ab", "ba", "ab"]]`