#️⃣ Hashing (Hashmaps & Sets)
Hash maps offer O(1) average insert, lookup, and delete. Sets track existence; maps track frequency or mapping.
Core Patterns
| Pattern |
Tool |
Example |
| Existence check |
unordered_set |
Duplicates, anagram detection |
| Frequency count |
unordered_map<T,int> |
Count chars, top-k elements |
| Two-sum lookup |
unordered_map<T,int> |
Find pair that sums to target |
| Grouping |
unordered_map<key, vector> |
Group anagrams by sorted key |
| Prefix sum + map |
unordered_map<int,int> |
Count subarrays with target sum |
Templates
// Frequency count
unordered_map<int, int> freq;
for (int x : arr) freq[x]++;
// Two-sum lookup
unordered_map<int, int> seen; // value → index
for (int i = 0; i < nums.size(); i++) {
if (seen.count(target - nums[i]))
return {seen[target - nums[i]], i};
seen[nums[i]] = i;
}
// Group anagrams
unordered_map<string, vector<string>> groups;
for (string& s : strs) {
string key = s; sort(key.begin(), key.end());
groups[key].push_back(s);
}
Complexity
| Operation |
Average |
Worst |
| Insert / Lookup / Delete |
O(1) |
O(n) |
| Space |
O(n) |
O(n) |