What is a Hash Map Pattern?
A hash map stores a value under a key so that the value can usually be found in constant time. Algorithm problems use that lookup to remember useful facts from earlier input.
You need key-value pairs, arrays, and a basic loop. The short version is: store the exact fact a future item will ask for.
The Core Idea: Remember the Complement
In LC 1: Two Sum, the numbers are [2,7,11,15] and the target is 9.
When we read 2, we need a future 7.
When we later read 7, the required complement 2 is already in the map.
Why does this beat checking every pair? The map replaces a scan through all earlier values with one lookup.
It is like a coat-check desk. The ticket number takes you directly to one stored coat instead of making you inspect every coat in the room.
How Two Sum Uses the Map
The Rule You Keep True
Before processing index i, the map describes only the values from indexes before i.
That rule prevents the current element from matching itself.
The stored fact changes by problem:
- Two Sum stores a value and its index.
- Contains Duplicate stores whether a value has appeared.
- Group Anagrams maps a letter signature to all words with that signature.
- Longest Consecutive Sequence stores membership so sequence starts can be recognized.
Group Anagrams is the one that usually trips us up. The hard part is not the map. It is choosing a key that is identical for every anagram and different for unrelated words.
Picking the Right Shape
From Rule to Code
- Decide which future question must be answered quickly.
- Choose a key and state exactly what its stored value means.
- For each input item, compute and check the needed key.
- Return or update the result when the key is found.
- Store the current fact only after any check that must use earlier items.
Each item performs a constant number of average-time map operations, so the scan is usually O(n) time with O(n) extra space.
When to use it
- •You need to find a previously seen value or fact quickly.
- •The problem asks about duplicates, frequencies, complements, or grouping by a key.
- •An **O(n²)** comparison can become a single pass by remembering earlier work.
- •The answer depends on membership rather than sorted order.
How to identify it
- •The prompt asks whether a value has appeared before.
- •A current value determines another value that must already exist, such as `target - value`.
- •Items can be grouped by a stable signature such as sorted letters.
- •Fast key lookup is more useful than maintaining input order.
Key insights
- →A hash map stores a direct relationship from a key to the fact needed later.
- →Two Sum stores earlier values so the current complement can be checked immediately.
- →The order of check and insert matters when the same element cannot be used twice.
- →Frequency maps turn repeated scanning into one count per value.
- →A good key contains exactly the information that makes two items belong to the same group.
Common mistakes
- 01Storing the current value before checking its complement and accidentally pairing an element with itself.
- 02Using an object key that converts different values to the same string unexpectedly.
- 03Forgetting whether the map stores an index, count, boolean, or full item.
- 04Using a hash map when sorted order or range order is required later.
- 05Assuming worst-case or language-specific map behavior without knowing the runtime guarantees.