What it is
A hash map turns "have I seen this before, and what did I learn when I did" into a single O(1) average lookup instead of a re-scan. What goes in the map varies by problem: a value's index, a running prefix sum's occurrence count, a canonical form of a string, or a linked structure's original-to-copy mapping. The data itself can be an array, string, or graph — the map is the accelerator sitting alongside it, not the primary structure, except in problems where the map (plus a companion list) is the whole design, such as a cache.
When it applies
- You need to test set membership or count occurrences while walking a sequence once, and re-scanning on every step would be too slow.
- You are counting or grouping items by some derived key (a letter tally, a prefix-sum value, a canonical string) rather than by their raw value.
- You are deep-copying a structure with internal cross-references (a linked list's random pointer, a graph's edges) and need to translate "the old reference" into "the new one" without creating duplicates.
- It does not apply when the thing you need is order, not membership — a strictly contiguous window's shrinking/growing behavior is a sliding-window problem even though it often keeps a map alongside it, and a range of index-based sums is better served by prefix sums directly than by re-deriving them through a map every time.
Tells in the problem
- "Return the indices of the two/pair of elements that..." — you need a fast "have I seen the complement" check.
- "Group the following into buckets where members share some property" — the property is your map key.
- "Design a class with O(1) (or O(1) average)
get/put" — a hash map paired with an ordering structure (a linked list, a count) is the expected shape. - "...whose elements sum to exactly k" or "...is a multiple of k" over a subarray — the map holds prefix-sum values or remainders, not raw elements.
- A structure with pointers that can point anywhere in itself, including forward or into a cycle, that you must copy — the map is old-node-to-new-node.
The classic mistake
The recurring bug is checking membership after inserting the current element instead of before, or inserting into a count map without a starting seed that represents "nothing consumed yet." Both look like off-by-one errors: a two-sum implementation that matches an element with itself, or a prefix-sum counter that silently drops every subarray beginning at index 0 because the map never held a zero-sum baseline. It happens because the map update and the map lookup feel like one step when you're moving fast, and the order between them is exactly what makes the difference between correct and subtly wrong. Catch it by tracing the smallest possible input by hand — a two-element array, or a single element equal to the target — before trusting the loop on larger cases.
Questions to start with
- Two Sum — the cleanest version of "check before you insert," with no other structure involved.
- Valid Anagram — a tally map instead of a membership map, plus the early-exit-on-negative-count idea.
- Group Anagrams — the map key becomes a derived value (a letter-count tuple) rather than the raw input.
- Subarray Sum Equals K — the map holds prefix-sum counts, and the
{0: 1}seed is the whole difficulty. - LRU Cache — the map is one half of a two-structure design, paired with a doubly linked list for ordering.