Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Notes › DSA

Hashing (HashMap and HashSet)

A hash table stores keys so that insert, delete and lookup take O(1) on average. It is the single most useful idea for speeding up brute-force solutions.

How it works

  1. A hash function turns a key into a number: h("cat") → 98765.
  2. That number picks a bucket: index = h(key) % capacity.
  3. The key (and its value) is stored in that bucket.

Two different keys can land in the same bucket — a collision. Two common fixes:

When the table gets too full (the load factor passes a limit, ~0.75 in Java), it rehashes into a bigger array — an O(n) step that happens rarely, so inserts stay O(1) amortised.

Operation Average Worst case
Insert / delete / find O(1) O(n) (every key in one bucket)

C++ containers

Container Ordered? Lookup Notes
unordered_map<K,V> no O(1) avg hash table
unordered_set<K> no O(1) avg keys only
map<K,V> yes (sorted keys) O(log n) red-black tree
set<K> yes O(log n) sorted, unique keys
unordered_map<string, int> freq;
for (string w : words) freq[w]++;          // missing keys start at 0
if (freq.count("apple")) cout << freq["apple"];
for (auto& [word, c] : freq) cout << word << " " << c << "\n";

unordered_set<int> seen;
seen.insert(5);
bool has = seen.count(5);                    // 1 or 0

freq[x] creates the key if it is missing. To only check, use count or find.

Java: HashMap, HashSet, TreeMap. Python: dict, set, collections.Counter.

Pattern 1: "have I seen this before?" — Two Sum

vector<int> twoSum(vector<int>& a, int target) {
    unordered_map<int, int> idx;             // value → index
    for (int i = 0; i < a.size(); i++) {
        int need = target - a[i];
        if (idx.count(need)) return {idx[need], i};
        idx[a[i]] = i;
    }
    return {};
}

Brute force is O(n²); the map makes it O(n).

Pattern 2: counting frequencies

Anagrams, first non-repeating character, majority element, top-K frequent elements.

bool isAnagram(string s, string t) {
    if (s.size() != t.size()) return false;
    int cnt[26] = {0};                       // fixed alphabet: an array beats a map
    for (char c : s) cnt[c - 'a']++;
    for (char c : t) if (--cnt[c - 'a'] < 0) return false;
    return true;
}

Pattern 3: prefix sum + hash map

Count subarrays with sum = k: if prefix[j] - prefix[i] = k, then the subarray (i, j] sums to k. Store how many times each prefix sum has appeared.

int subarraySum(vector<int>& a, int k) {
    unordered_map<int, int> seen{{0, 1}};
    int sum = 0, count = 0;
    for (int x : a) {
        sum += x;
        count += seen[sum - k];
        seen[sum]++;
    }
    return count;
}

Works with negative numbers, unlike the sliding window.

Pattern 4: grouping by a key

Group anagrams: key = the sorted word (or the 26-letter count) → map<key, vector<string>>.

Pattern 5: longest consecutive sequence

Put all numbers in a set; start counting only from numbers whose x - 1 is not in the set → O(n).

Classic problems

Problem Idea
Two sum value → index map
Valid anagram / group anagrams frequency / sorted key
Contains duplicate set
Subarray sum equals K prefix sum + map
Longest consecutive sequence set
Top K frequent elements count + heap or bucket sort
Longest substring without repeating characters map + sliding window

Practise them in the Hashing & Two Pointers section.

Interview one-liners

More DSA notes