Group Anagrams [Medium] — Sorted Key HashMap

Problem Statement

Given an array of strings, group the anagrams together.

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

Intuition

Two words are anagrams iff their sorted forms are equal. Use sorted word as HashMap key → list of words.

Optimized: Use char-count tuple as key (avoids O(k log k) sort).

Solutions

C++

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

Java

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

JavaScript

var groupAnagrams = function(strs) {
    const mp=new Map();
    for(const s of strs){
        const key=[...s].sort().join('');
        if(!mp.has(key))mp.set(key,[]);
        mp.get(key).push(s);
    }
    return [...mp.values()];
};

Python

from collections import defaultdict

def groupAnagrams(strs: list[str]) -> list[list[str]]:
    mp = defaultdict(list)
    for s in strs:
        mp[tuple(sorted(s))].append(s)
    return list(mp.values())

# O(n*k) with count key:
def groupAnagrams_fast(strs):
    mp = defaultdict(list)
    for s in strs:
        key = [0]*26
        for c in s: key[ord(c)-97] += 1
        mp[tuple(key)].append(s)
    return list(mp.values())

Complexity

Time: O(n×k log k) sort key; O(n×k) count key
Space: O(n×k)