LeetCode 49 — Group Anagrams

What does it solve?

Given an array of strings strs, group all anagrams together. An anagram contains exactly the same characters — just in a different order. Return all groups in any order.

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

Sorted-key approach

// Anagrams share the same sorted string
map = {}
for s in strs:
key = sort(s) // e.g. "eat" → "aet"
map[key].append(s)

return map.values()

💡 Key insight: Two strings are anagrams if and only if their sorted character sequences are identical. "eat", "tea", and "ate" all sort to "aet". By using this sorted string as a canonical key in a hash map, we bucket all anagrams together in a single O(n·k·log k) pass — no pairwise comparisons needed.

Complexity

Time

O(n·k·log k)

n = number of strings, k = max string length. Sorting each string costs O(k log k).

Space

O(n·k)

Hash map stores all n strings with their keys, each up to length k.

Examples & edge cases

Live animation — Sorted-Key Hash Map

Current string (sorting) Sorted key New group created Added to existing group

⏸ Waiting to start

Input strings — each card shows its assigned group colour after processing

Sorting current string → generating map key

Pick a string to start...

Hash Map { sorted_key → [words] } empty

Map is empty — entries appear as strings are processed

Result groups

No groups yet...

Step — of —

Processing

—

current string

Key

—

sorted form

Groups

in hash map

Processed

of — strings

Select an example and press Play to begin.

✓ Grouped!

Speed Medium

Step-by-step table

Step	String	Sorted Key	Action	Map state (keys)

C++ implementation

group_anagrams.cpp

#include <bits/stdc++.h>
using namespace std;

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    // key = sorted string, value = list of original strings
    unordered_map<string, vector<string>> mp;

    for (const string& s : strs) {
        string key = s;
        sort(key.begin(), key.end());  // "eat" → "aet"
        mp[key].push_back(s);          // bucket by sorted key
    }

    vector<vector<string>> result;
    for (auto& [key, group] : mp)
        result.push_back(group);

    return result;
}

int main() {
    vector<string> strs = {"eat","tea","tan","ate","nat","bat"};
    auto res = groupAnagrams(strs);
    // Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
    for (auto& g : res) {
        for (auto& w : g) cout << w << " ";
        cout << "\n";
    }
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars