Arrays & Hashing

Every algorithm topic in this track starts the same way: what's the tool, why does it work, and how do you recognize when a problem is asking for it? Arrays and hash maps are the foundation — almost every other topic either builds directly on them or exists because they're not enough on their own (a tree is what you reach for when a hash map's lack of order becomes the problem).

What a hash map actually is

A hash map takes a key, runs it through a hash function that produces a number, and uses that number to pick a bucket to store the value in. Looking a key back up means hashing it again and going straight to that bucket — no scanning required. That's the entire trick behind O(1) average lookup and insert: you're trading the O(n) cost of "check every element" for the O(1) cost of "compute where it must be."

unordered_map vs map vs a plain vector

Three tools that can all technically "look things up" — the decision between them is a real skill, not a coin flip:

• unordered_map — a hash table. Use it when you need fast key lookup and don't care about order. O(1) average, O(n) worst case.
• map — a balanced tree. Keys stay sorted; you get ordered iteration and range queries (lower_bound, upper_bound) for free. O(log n) always — no bad-hash worst case to worry about.
• A plain vector with a linear scan — for small n (roughly under a few dozen elements), this can genuinely beat a hash map. Hashing has real constant-factor overhead, and a small array scan is extremely cache-friendly. This is the non-obvious one: reaching for a hash map reflexively, even when n is tiny, is itself a kind of inefficiency.

// Need the best (min/max) key constantly, or a sorted range? -> map
std::map<int64_t, int> ordered;

// Just need "does this key exist" / "what's its value" fast? -> unordered_map
std::unordered_map<std::string, int> counts;

// A handful of items, or one-off lookups? A vector scan is fine, and simpler.
std::vector<std::pair<std::string, int>> small_list;

Common mistakes

// MISTAKE 1: operator[] as a "does this exist" check
if (counts[key] > 0) { /* ... */ }
// operator[] on a map/unordered_map DEFAULT-INSERTS the key if it's missing.
// This "check" just silently created an entry with value 0. Use .find() or
// .count() for a real existence check instead:
if (counts.find(key) != counts.end()) { /* ... */ }

// MISTAKE 2: mutating a container while iterating it
for (auto it = m.begin(); it != m.end(); ++it)
    if (should_remove(*it)) m.erase(it); // it is now invalid -- UB on ++it
// FIX: erase() returns the next valid iterator
for (auto it = m.begin(); it != m.end(); )
    it = should_remove(*it) ? m.erase(it) : std::next(it);

// MISTAKE 3: assuming unordered_map preserves insertion order. It doesn't --
// iteration order is unspecified and can even change between runs.

// MISTAKE 4: hashing your own struct without telling it how
// std::unordered_map<Order, int> won't compile -- Order has no default hash.
// You'd need to specialize std::hash<Order> or pass a custom hasher.

Pattern recognition — how you actually know to reach for this

This is the skill that matters more than any single problem: recognizing the shape of what a problem is asking for.

• "Have I seen this before?" → a hash set. One membership check per element, O(n) total instead of O(n²) re-scanning.
• "Count how many times each thing appears" → a hash map from value to count.
• "Find a pair/complement that satisfies some condition" → a hash map from value to index (or position), so the complement lookup is O(1) instead of a nested loop. This is Two Sum's entire shape.
• "Group things that share some derived property" → a hash map from that derived key to a list of members. This is Group Anagrams' shape: the derived key is each string's sorted form.
• "How many contiguous ranges satisfy some sum/count condition" → a running prefix value plus a hash map counting how often each prefix value has occurred. This is Subarray Sum Equals K's shape.

Worked example: word frequency, the slow way and the fast way

// O(n^2): for each word, re-scan the whole list counting matches
for (auto& word : words) {
    int count = 0;
    for (auto& other : words) if (other == word) count++;
    // ... use count, but you just redid work for every duplicate
}

// O(n): one pass, the map remembers what you've already counted
std::unordered_map<std::string, int> counts;
for (auto& word : words) counts[word]++;
// counts[word]++ is safe here (not a lookup-only check) -- a missing key
// default-inserts as 0, then immediately becomes 1. That's the ONE place
// operator[]'s auto-insert behavior is exactly what you want.

Notice the fast version isn't more complicated — it's a different shape of thinking about the same problem. That shift is what the exercises below are actually testing.