Group Anagrams — Sort Key HashMap O(n*k log k) [Google, Meta, Amazon]
Sanjeev SharmaAdvertisement
Problem Statement
Given an array of strings, group the anagrams together.
Input: ["eat","tea","tan","ate","nat","bat"] → [["bat"],["nat","tan"],["ate","eat","tea"]]
- Intuition
- C++ Solution
- Java Solution
- Python Solution
- JavaScript Solution
- Complexity: O(nk log k) time, O(nk) space
Intuition
Anagrams have the same sorted form. Use sorted string as the HashMap key.
Optimization: Instead of sorting, use a 26-char frequency tuple as key → O(n*k) total.
C++ Solution
class Solution {
public:
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 Solution
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> mp = new HashMap<>();
for (String s : strs) {
char[] ca = s.toCharArray(); Arrays.sort(ca);
mp.computeIfAbsent(new String(ca), k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(mp.values());
}
}
Python Solution
from collections import defaultdict
def groupAnagrams(strs):
mp = defaultdict(list)
for s in strs:
mp[tuple(sorted(s))].append(s)
return list(mp.values())
JavaScript Solution
function groupAnagrams(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()];
}
Complexity: O(nk log k) time, O(nk) space
Advertisement
