Hashing
The single most common way an O(n²) brute force becomes O(n).
What a hash map actually does
A hash function turns a key into a number, and that number picks a
"bucket" in an underlying array. Look-up doesn't search — it computes
the bucket from the key and jumps straight there. That's why
Map/Set/object lookups are O(1) average case:
the cost of hashing the key doesn't grow with how many other keys are
already stored.
Map/Set vs plain objects
| Map / Set | Plain object | |
|---|---|---|
| Key types | anything (objects, NaN, etc.) | strings/symbols only — numbers get coerced |
| Size | .size, O(1) | Object.keys(o).length, O(n) |
| Iteration order | insertion order, guaranteed | mostly insertion order, but integer-like keys sort first |
| Accidental prototype keys | impossible | "toString" in {} is true |
In interviews, default to Map/Set unless
there's a specific reason not to — it sidesteps a whole category of
"wait, why is this key already there" bugs.
The pattern: trade space for time
Almost every "hashing" interview question is the same trade: spend O(n) space to remember what you've already seen, so a second O(n) pass (or even the same pass) can answer "have I seen this before?" in O(1) instead of O(n).
// Two Sum — brute force: O(n²) time, O(1) space
function twoSumSlow(nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) return [i, j];
}
}
}
// Two Sum — hashed: O(n) time, O(n) space
function twoSumFast(nums, target) {
const seen = new Map(); // value → index
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i];
if (seen.has(need)) return [seen.get(need), i];
seen.set(nums[i], i);
}
}Watch the map build up, step by step
nums = [2, 7, 11, 15], target = 9 — trace every iteration:
| i | nums[i] | need = target − nums[i] | seen.has(need)? | action |
|---|---|---|---|---|
| 0 | 2 | 7 | no — map is empty | store {2 → 0} |
| 1 | 7 | 2 | yes — seen.get(2) = 0 | return [0, 1] ✓ |
Notice the map is only ever looked up for the value we still need, and only ever written for values we've already passed. That single pass does the work a nested loop would need two passes (and O(n²) time) to do.
Frequency counting — the other 80% of hashing questions
function frequency(arr) {
const counts = new Map();
for (const x of arr) {
counts.set(x, (counts.get(x) || 0) + 1);
}
return counts;
}
// anagram check: same characters, same counts
function isAnagram(a, b) {
if (a.length !== b.length) return false;
const counts = new Map();
for (const c of a) counts.set(c, (counts.get(c) || 0) + 1);
for (const c of b) {
if (!counts.get(c)) return false;
counts.set(c, counts.get(c) - 1);
}
return true;
}Grouping — building a Map of arrays
// group anagrams: same sorted letters → same bucket
function groupAnagrams(words) {
const groups = new Map();
for (const word of words) {
const key = [...word].sort().join("");
if (!groups.has(key)) groups.set(key, []);
groups.get(key).push(word);
}
return [...groups.values()];
}When hashing is the wrong tool
- You need order — a hash map doesn't sort. If the question wants sorted output or range queries, you likely want a sorted structure (or a heap) instead.
- You need the closest match, not an exact one — hashing only answers "is this exact key present." Nearest-value questions want binary search on a sorted structure.
- Memory is the actual constraint — if the problem explicitly asks for O(1) space, a hash map is disqualified by definition.
Opens in the editor — write it, run it, and check it against real tests.