Chapter 2 · Intermediate · Prereq: Chapter 1

Hashing — Hash Maps & Hash Sets

Hash Maps & Hash Sets · Collision Handling · Frequency Counting · Grouping — the single most powerful technique for reducing O(n²) solutions to O(n).

11 Sections 13 Practice Problems Intermediate ← Back to Roadmap

Section 1 — What Is Hashing?

Hashing is the process of converting a key of any type into a fixed-size integer (the hash code) and using that integer as an index into an array (the hash table). This gives us O(1) average-case insertion, deletion, and lookup — regardless of how many elements are stored.

Why Hashing Matters This is the single most powerful technique for reducing O(n) or O(n²) solutions to O(n). Almost every medium-hard problem that does not involve ordering or hierarchy has a hash-based optimal solution.

1.1 — Hash Function & Collision Handling

A hash function maps keys to indices. Two keys can hash to the same index — a collision. C++ resolves collisions via chaining (linked list at each index) in unordered_map.

Chaining: Each bucket holds a linked list. Average O(1); worst case O(n) if all keys collide.
Load factor: When table is ≥ 75% full, it rehashes to a larger table. O(n) but amortized O(1).
In C++: unordered_map uses open addressing with std::hash internally.

1.2 — C++ API

// unordered_map — key-value store
unordered_map<string, int> freq;
freq["hello"]++;                   // insert or increment
freq.count("world");               // 0 or 1 — check existence
freq.find("hello");                // returns iterator
freq.erase("hello");               // remove key

// unordered_set — existence only
unordered_set<int> seen;
seen.insert(42);
seen.count(42);  // 1 if exists, 0 if not

// Default int value in map is 0
unordered_map<int,int> cnt;
cnt[key]++;  // OK — default-initialises to 0 then increments

All ops averageO(1) SpaceO(n) Worst caseO(n)

Section 2 — Pattern: Existence Check

Use unordered_set when you just want to know if a value has been seen. O(1) average per lookup.

// Pangram check — has the sentence all 26 letters?
unordered_set<char> letters(sentence.begin(), sentence.end());
return letters.size() == 26;

// Has any duplicate?
unordered_set<int> seen;
for (int x : nums) {
    if (seen.count(x)) return true; // duplicate found
    seen.insert(x);
}
return false;

Section 3 — Pattern: Frequency Count

Use unordered_map<T, int> to count how many times each element appears. Foundation for anagram, top-K, most-frequent problems.

// Frequency count for any iterable
unordered_map<int,int> freq;
for (int x : arr) freq[x]++;

// Is Anagram — same char frequencies?
unordered_map<char,int> cnt;
for (char c : s) cnt[c]++;
for (char c : t) {
    if (--cnt[c] < 0) return false;
}
return true;

// Top K frequent elements — combine freq map + heap
unordered_map<int,int> freq;
for (int x : nums) freq[x]++;
priority_queue<pair<int,int>, vector<pair<int,int>>,
    // min-heap by frequency
    greater<pair<int,int>>> pq;
for (auto& [val, cnt] : freq) {
    pq.push({cnt, val});
    if (pq.size() > k) pq.pop();
}

Section 4 — Pattern: Two-Sum Lookup

For each element x, check if its complement (target - x) exists in the hash map. One-pass O(n).

General Two-Sum Pattern Store what you have seen so far. For each new element, ask: "Is its complement already here?" This converts O(n²) nested search into O(n) with one hash table lookup.

// Classical two-sum — return indices
unordered_map<int,int> seen; // val → 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;
}
// Counting elements (x+1 exists for all x in set)
unordered_set<int> s(arr.begin(), arr.end());
int count = 0;
for (int x : arr) if (s.count(x+1)) count++;
return count;

Section 5 — Pattern: Grouping

Map a grouping key to a list of all elements sharing that key. Classic example: group anagrams by their sorted form.

// Group Anagrams — map sorted key → strings
unordered_map<string, vector<string>> groups;
for (string& s : strs) {
    string key = s;
    sort(key.begin(), key.end());
    groups[key].push_back(s);
}
vector<vector<string>> result;
for (auto& [key, group] : groups) result.push_back(group);
return result;

Section 6 — Pattern: Sliding Window + HashMap

Maintain a frequency map of elements in the current window. Expand right, shrink left when constraint violated.

// Longest substring with at most k distinct characters
unordered_map<char,int> freq;
int left = 0, ans = 0;
for (int right = 0; right < s.size(); right++) {
    freq[s[right]]++;
    while (freq.size() > k) {               // shrink
        if (--freq[s[left]] == 0) freq.erase(s[left]);
        left++;
    }
    ans = max(ans, right - left + 1);
}

Section 7 — Pattern: Prefix Sum + HashMap

Store cumulative prefix sums and their frequencies. For each prefix sum curr, the count of subarrays summing to target ending at this index = freq[curr - target].

// Count subarrays with sum == k
unordered_map<int,int> freq; freq[0] = 1;
int curr = 0, ans = 0;
for (int x : nums) {
    curr += x;
    ans += freq[curr - k];  // subarrays ending here summing to k
    freq[curr]++;
}
// Count subarrays with equal number of 0s and 1s
// Transform: 0 → -1. Then counts subarrays summing to 0.
unordered_map<int,int> freq; freq[0] = 1;
int curr = 0, ans = 0;
for (int x : nums) {
    curr += (x == 1 ? 1 : -1);
    ans += freq[curr];
    freq[curr]++;
}

Practice Problems

#	Problem	Pattern	Diff
1	1832. Check if the Sentence Is Pangram	Existence check (set)	Easy
2	268. Missing Number	Existence check (set)	Easy
3	1426. Counting Elements	Two-sum lookup (x+1)	Easy
4	1. Two Sum	Two-sum lookup	Easy
5	383. Ransom Note	Frequency count	Easy
6	771. Jewels and Stones	Existence check (set)	Easy
7	2225. Find Players With Zero or One Losses	Frequency count (map)	Medium
8	1133. Largest Unique Number	Frequency count (unique = 1)	Easy
9	1189. Maximum Number of Balloons	Frequency ratio	Easy
10	49. Group Anagrams	Grouping (sorted key)	Medium
11	347. Top K Frequent Elements	Frequency count + heap	Medium
12	560. Subarray Sum Equals K	Prefix sum + HashMap	Medium
13	146. LRU Cache	HashMap + Doubly Linked List	Medium