LC Patterns — Hash Map / Hash Set

unordered_map<int,int> d;          // key → value (average O(1))
++d[k];                            // operator[] default-inits 0 — counting in one line
d.count(k);                        // membership test (0 or 1)
auto it = d.find(k);               // lookup; it == d.end() means absent
unordered_set<int> seen;           // membership only, no values
int cnt[26] = {0};                 // for lowercase letters, a plain array beats a map
for (char c : s) ++cnt[c - 'a'];   // frequency count
string key = w;                    // anagram key = a sorted copy of the word
sort(key.begin(), key.end());

Facts to have loaded

unordered_map keys need a hash + operator==. int and string work out of the box; pair/tuple have no default hash — encode them into one value (e.g. r*1000 + c or a joined string) or fall back to std::map (ordered, O(log n)). O(1) is the average — worst case O(n) with bad collisions; say "expected O(1)" once. unordered_map has no order at all — for "first unique," rescan the original string. Anagram test: equal 26-count arrays, or sort both copies. Reach for unordered_set whenever you'd only ever store true. Use reserve() to cut rehash cost when the size is known.

What it is: The simplest deal: walk the data once, keep a set/map of what you've seen, and for each new element ask one O(1) question about the past — "has this exact thing appeared?" or "has my partner appeared?" (the partner being whatever makes the pair work, like target − x).

Intuition: the brute force scans backward for every element — O(n²). But that backward scan asks a question with a precomputable answer. So precompute it: store each element as you pass. Two Sum (1): partner is target − x, looked up before storing x. Contains Duplicate (217): question is "seen exactly this value?" 219 adds "…within the last k positions?" — so the stored value becomes the last index each value appeared, and you compare distances.

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int,int> seen;                 // value → index
    for (int i = 0; i < (int)nums.size(); ++i) {
        auto it = seen.find(target - nums[i]);   // ask for the partner FIRST
        if (it != seen.end()) return {it->second, i};
        seen[nums[i]] = i;                       // then store yourself
    }
    return {};
}

What it is: Count how many times each thing appears, then answer questions off the counts: can these letters build that word? which character appears exactly once first? sort characters by how common they are. One counting pass (a size-26 array or an unordered_map), then a second pass over the counts.

Intuition: many string/array questions aren't about order — only about supply. Ransom note (383) asks whether the magazine's supply covers the note's demand: count both, compare. First unique (387): a char is unique iff its total count is 1 — count first, then re-walk. Sort by frequency (451): count, then rebuild most-common-first. Second-level move: count the counts (LC 1207 asks if all frequencies are distinct → drop them in an unordered_set and check its size).

bool canConstruct(string note, string mag) {
    int cnt[26] = {0};
    for (char c : mag)  ++cnt[c - 'a'];              // supply
    for (char c : note) if (--cnt[c - 'a'] < 0)      // spend; demand beat supply?
        return false;
    return true;
}

string frequencySort(string s) {
    unordered_map<char,int> cnt;
    for (char c : s) ++cnt[c];
    vector<pair<int,char>> v;                          // (count, char)
    for (auto& [ch, c] : cnt) v.push_back({c, ch});
    sort(v.rbegin(), v.rend());                      // most common first
    string out;
    for (auto& [c, ch] : v) out += string(c, ch);
    return out;
}

What it is: Count how many pairs satisfy a relation — sum divisible by 60, difference exactly k, equal values. Like Pattern 1, but instead of stopping at the first partner you add the number of partners seen so far to a running answer, then register yourself. Every pair is counted exactly once, no index juggling.

Intuition: for each element, the number of pairs it closes is exactly "how many earlier elements were my partner" — a count the map already has. The order — count first, then add yourself — guarantees each pair is counted once (as "later meets earlier") and never self-paired. Difference k (2006): partners of x are earlier x−k and x+k — look both up. Good pairs (1512): partner is an earlier equal x.

int numPairsDivisibleBy60(vector<int>& time) {
    long long ans = 0;               // n² pairs can overflow int → use long long
    int count[60] = {0};             // remainder → how many seen
    for (int t : time) {
        int r = t % 60;
        ans += count[(60 - r) % 60]; // add partners seen so far, FIRST
        ++count[r];                  // then register yourself
    }
    return ans;
}

What it is: Things belong together when they share a hidden signature — anagrams share letters, matrix rows can equal columns, a Sudoku digit "collides" in the same row/column/box. Design a canonical key — one standardized form that all group members map to and nothing else does — and let the map do the grouping.

Intuition: grouping is pairwise comparison in disguise — O(n²) if you compare everything with everything. A canonical key makes comparison free: two things share a group iff their keys are equal. Anagrams (49): sorted letters. Equal row-column pairs (2352): key = the row joined into a string (a vector has no default hash). Valid Sudoku (36): the same pattern used for collision-detection instead of collection.

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> groups;
    for (auto& w : strs) {
        string key = w;
        sort(key.begin(), key.end());        // canonical key = sorted letters
        groups[key].push_back(w);
    }
    vector<vector<string>> out;
    for (auto& [k, v] : groups) out.push_back(move(v));
    return out;
}

What it is: Check that two sequences match up one-to-one: every 'a' in s maps to the same letter in t, and no two different letters map to the same target. One map is not enough — you need both directions (or a trick that implies the second).

Intuition: a single map s→t catches "one letter mapping to two things" but misses "two letters mapping to the same thing." Isomorphic (205) and word pattern (290 — same problem with words) both need the backward map: check and update both every step. Find-and-replace pattern (890): normalize both to a "first-occurrence fingerprint" ("abb" → [0,1,1], "mee" → [0,1,1]) and compare — normalizing to a canonical form quietly is the two-way check, connecting back to Pattern 4.

bool isIsomorphic(string s, string t) {
    unordered_map<char,char> s2t, t2s;
    for (int i = 0; i < (int)s.size(); ++i) {
        char a = s[i], b = t[i];
        if (s2t.count(a) && s2t[a] != b) return false;   // conflict forward
        if (t2s.count(b) && t2s[b] != a) return false;   // conflict backward
        s2t[a] = b; t2s[b] = a;
    }
    return true;
}

What it is: Count or find subarrays with a sum property — sum exactly k, equal 0s and 1s, sum divisible by k. A subarray sum is a difference of two running totals (sum(i..j) = prefix[j] − prefix[i−1]), so "find a subarray summing to k" becomes "find two running totals that differ by k" — Pattern 1's complement lookup, applied to prefix sums.

Intuition: at position j you want earlier positions i where prefix[j] − prefix[i] = k, i.e. earlier totals equal to prefix[j] − k — a map from total → count answers that in O(1) (560). Equal 0s/1s (525): recode 0 as −1, so it becomes "sum = 0," and for the longest such subarray store the first index of each total. Divisible by k (974): two prefixes work iff same remainder mod k → key = remainder. Seed the empty prefix: {0:1} for counting, {0:-1} for first-index.

int subarraySum(vector<int>& nums, int k) {          // 560 — count
    unordered_map<long long,int> count{{0, 1}};      // seed the empty prefix
    long long total = 0; int ans = 0;
    for (int x : nums) {
        total += x;
        auto it = count.find(total - k);            // lookup BEFORE insert
        if (it != count.end()) ans += it->second;
        ++count[total];
    }
    return ans;
}

int findMaxLength(vector<int>& nums) {               // 525 — longest, store first index
    unordered_map<long long,int> first{{0, -1}};
    long long total = 0; int best = 0;
    for (int i = 0; i < (int)nums.size(); ++i) {
        total += nums[i] ? 1 : -1;
        auto it = first.find(total);
        if (it != first.end()) best = max(best, i - it->second);
        else first[total] = i;                      // never overwrite — earliest wins
    }
    return best;
}

What it is: The "have I seen it?" set applied to bigger things than single values: whole positions in a process (to detect a loop), stretches of consecutive numbers (to walk chains), or chunks of a string (to spot repeats). The set answers "am I revisiting?" — each problem differs in what a "state" is.

Intuition: 128: a number x is a start iff x−1 is missing — only then walk forward. The "only start at starts" gate makes it O(n) despite the loop, and the O(n) proof is the sentence interviewers wait for. 202: store every total seen; a revisit means a loop. 187 (repeated DNA): slide a length-10 window, store each chunk; a chunk already present is a repeat (report each once).

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> s(nums.begin(), nums.end());
    int best = 0;
    for (int x : s) {
        if (s.count(x - 1)) continue;      // not a start — skip (keeps it O(n))
        int y = x;
        while (s.count(y + 1)) ++y;        // walk the run
        best = max(best, y - x + 1);
    }
    return best;
}

What it is: When values are (or can be brought) into 1..n and the array has length n, the array itself is the hash map: value v ↔ index v−1, and "I've seen v" is recorded by marking that slot (negating it, or swapping v into it). O(1) extra space — the trick behind every "find the missing/duplicate in O(n) time, O(1) space."

Intuition: a hash map from {1..n} to anything is just an array of size n — and you already have one. Marking by negation (448, 442): flip nums[v−1] negative; still-positive at the end means that number never appeared (448); already-negative means seen twice (442). Marking by swapping into place (41): repeatedly swap each value into its home slot ("cyclic sort"), then the first misplaced slot reveals the answer.

vector<int> findDuplicates(vector<int>& nums) {        // 442
    vector<int> res;
    for (int x : nums) {
        int i = abs(x) - 1;                          // abs() mandatory — value may already be flipped
        if (nums[i] < 0) res.push_back(i + 1);       // already marked → duplicate
        else nums[i] = -nums[i];
    }
    return res;
}

int firstMissingPositive(vector<int>& nums) {         // 41
    int n = nums.size();
    for (int i = 0; i < n; ++i)
        while (nums[i] >= 1 && nums[i] <= n && nums[nums[i]-1] != nums[i])
            swap(nums[i], nums[nums[i]-1]);          // guard stops infinite swap
    for (int i = 0; i < n; ++i)
        if (nums[i] != i + 1) return i + 1;
    return n + 1;
}

What it is: "Design a class with O(1) operations" — the answer is almost always a hash map plus one other structure for what the map can't do: an array for random access (380), sorted lists for time queries (981), heaps/lists for feeds (355), a doubly linked list for recency (146). The map's role is always the same — jump straight to the right spot in the other structure.

Intuition: each structure is missing something. A map alone can't return a uniform random element (380) — but map + array can: the array holds elements (random index = random element), the map holds each value's position. Time-based KV (981): map key → append-only list of (timestamp, value); timestamps arrive increasing, so each list is sorted for free, and get is a binary search for "rightmost time ≤ t." Twitter (355): map user → tweets, user → followees; the feed merges recent tweets. LRU (146) = map + doubly linked list.

class RandomizedSet {
    vector<int> vals;                    // elements, tightly packed
    unordered_map<int,int> pos;          // value → its index in vals (the invariant)
public:
    bool insert(int v) {
        if (pos.count(v)) return false;
        pos[v] = vals.size(); vals.push_back(v); return true;
    }
    bool remove(int v) {
        auto it = pos.find(v);
        if (it == pos.end()) return false;
        int i = it->second, last = vals.back();
        vals[i] = last; pos[last] = i;   // move last into the hole, fix its pos
        vals.pop_back(); pos.erase(it);  // shrink
        return true;
    }
    int getRandom() { return vals[rand() % vals.size()]; }  // uniform over current set
};