Hashing
The hashing pattern replaces a search loop with a hash map or set lookup, cutting many O(n²) solutions to O(n). When to use it, with a template.
The hashing pattern trades memory for speed. Instead of searching the input again for every item, you record what you have seen in a hash map or hash set and answer each later question with a single lookup.
The idea
Many brute-force solutions have this shape: for each item, loop over the other items looking for something. That inner loop makes the solution O(n²).
A hash table answers "is this value here?" in O(1) on average. If the inner loop is only asking that question, it can be replaced by a lookup, and the whole solution becomes O(n).
When to use it
Look for these signals in the problem:
- "Does any value appear twice?" or "is this a duplicate?"
- "Find two items that together make a target."
- "How many times does each item appear?"
- "Group the items that share a property."
- The input is not sorted and you are not allowed, or do not want, to sort it.
The three common forms
1. Seen set. Record each value; a repeat is found the moment you meet it again.
function hasRepeat(items) {
const seen = new Set();
for (const item of items) {
if (seen.has(item)) return true;
seen.add(item);
}
return false;
}2. Complement lookup. For each item, work out what its partner would have to be, and check whether that partner has already appeared.
function findPair(numbers, target) {
const seen = new Set();
for (const value of numbers) {
if (seen.has(target - value)) return [target - value, value];
seen.add(value);
}
return null;
}3. Frequency count. Count occurrences in a map, then read the answer from the counts.
function mostCommon(items) {
const counts = new Map();
let best = null;
for (const item of items) {
const count = (counts.get(item) ?? 0) + 1;
counts.set(item, count);
if (best === null || count > counts.get(best)) best = item;
}
return best;
}Walkthrough
findPair([1, 4, 6, 9], 10):
| Value | Partner needed | Seen already? | Set afterwards |
|---|---|---|---|
| 1 | 9 | No | 1 |
| 4 | 6 | No | 1, 4 |
| 6 | 4 | Yes: return [4, 6] |
Three steps instead of the six comparisons a nested loop would make, and the gap widens quickly: for a thousand values it is a thousand lookups against roughly half a million comparisons.
Three more forms
4. Index map. When the answer is a position, not a value, store each value's index as you go. This is what Two Sum needs.
5. Grouping. Work out a key for each item so that items which belong together get the same key, then collect them under it.
function groupByLength(words) {
const groups = new Map();
for (const word of words) {
const key = word.length;
if (!groups.has(key)) groups.set(key, []);
groups.get(key).push(word);
}
return groups;
}The whole skill is in choosing the key. Group Anagrams uses a word's sorted letters, so every anagram of a word produces the same key.
6. Running totals. Store the running total at each position. A stretch of the input adds up to a target exactly when two running totals differ by that target, which turns "find a subarray" into a lookup. This is the prefix sums pattern, used in Subarray Sum Equals K.
What to store
| The question | Use | Store |
|---|---|---|
| Is this value present? | Set |
The values |
| Where did this value appear? | Map |
Value → index |
| How many times? | Map |
Value → count |
| Which items belong together? | Map |
Key → list of items |
| Where did I last see it? | Map |
Value → most recent index |
Why check before adding
In the first two forms the lookup comes before the insert. That order matters: it stops an item from matching itself. With a target of 10 and a single 5 in the input, adding 5 first and then looking for 10 - 5 would wrongly report a pair.
Complexity
- Time: O(n). One pass, with a constant-time lookup and insert per item on average.
- Space: O(n). In the worst case every item ends up in the table.
That extra memory is the price. If the input is already sorted, two pointers often gets the same O(n) time with O(1) space.
Hashing or another pattern
| Situation | Better choice | Why |
|---|---|---|
| Unsorted input, find a pair or a repeat | Hashing | O(n) without sorting |
| Input already sorted | Two pointers | Same time, O(1) space |
| The original positions are needed | Hashing | Sorting would lose them |
| A run of neighbouring items | Sliding window, often with a map inside it | The window keeps the range; the map tracks its contents |
| Memory is tight | Sort first, or two pointers | Hashing always costs O(n) space |
Common mistakes
- Using an array as the "seen" list.
array.includesis a loop, so the solution is back to O(n²). Use aSetorMap. - Storing the wrong thing. If the answer needs positions, store the index as the map's value. If it needs counts, store the count.
- Using objects or arrays as keys and expecting equal contents to match. They are compared by identity. Convert them to a string key first.
- Forgetting that a map can be empty for a key.
map.get(key) + 1givesNaNthe first time. Use(map.get(key) ?? 0) + 1. - Looping over the map to find something. Searching a map by value is O(n). If you need to look up in both directions, keep two maps.
Practise
- Contains Duplicate (easy): the seen set.
- Two Sum (easy): the index map and the complement lookup.
- Group Anagrams (medium): grouping by a key.
- First Missing Positive (hard): using the array itself as the table.
Practice problems
| Problem | Difficulty | Time | Space | Read |
|---|---|---|---|---|
| Contains Duplicate | easy | O(n) | O(n) | Quick read: 3 min |
| Two Sum | easy | O(n) | O(n) | Quick read: 3 min |
| Group Anagrams | medium | O(n·k) | O(n·k) | Medium read: 6 min |
| First Missing Positive | hard | O(n) | O(1) | Medium read: 7 min |