Stop 21 · Data Structures & AlgorithmsTopics · 6/17

HashMap

In short

If an interviewer says "can you do better than O(n²)?", the answer is often a HashMap. It trades a little memory for instant lookups.

A key-value data structure offering average O(1) lookup, insert and delete — arguably the single most useful tool for optimizing brute-force solutions to O(n).

The purple blob drops a letter straight into the right pigeonhole on a wall of cubbies.

Think of it like this

Post office pigeonholes

The sorter doesn't search every box for Pune letters. The PIN code tells him which pigeonhole to use, so he drops it in directly. A hash function turns your key into a slot number the same way.

Watch it happen

Two Sum: target 9, one pass

1/3At 2, we need 9 - 2 = 7. The map is empty, so store 2 → index 0.

The big ideas

What you need to know

Key in, slot out

A hash function turns a key into a bucket number, so get, set and delete are O(1) on average.

Collisions happen

Two keys can land in the same bucket. The map handles it, but too many collisions slow lookups down.

Use Map, not plain objects

Map keeps any key type, keeps insertion order and has .size. Objects turn keys into strings.

Spot the pattern

"Have I seen this before?", counting, grouping and caching are all HashMap jobs.

See it in code

Walk through the code

1function twoSum(nums: number[], target: number): [number, number] | null {2  const seen = new Map<number, number>(); // value -> index3 4  for (let i = 0; i < nums.length; i++) {5    const need = target - nums[i];6    if (seen.has(need)) return [seen.get(need)!, i];7    seen.set(nums[i], i);8  }9  return null;10}11 12console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]

1/3The map remembers each value we've passed and where it was.

Brute force checks every pair, O(n²). The map version looks at each number once, O(n), using O(n) extra memory.

Save yourself the pain

Common mistakes

Oops

Using an object as a map with numeric or object keys.

Do this instead

Object keys become strings, so {} and {} collide as "[object Object]". Use Map for anything but simple string keys.

Oops

Saying HashMap lookups are always O(1).

Do this instead

Say "O(1) on average". In the worst case, with many collisions, it can degrade.

Your mission

HashMap drills

~35 min

Quick check

Your nested loop checks every pair of numbers. What usually brings it from O(n²) to O(n)?

Go deeper

1Solve two-sum using a hash map and compare it to the O(n²) brute-force approach.
2Practice using a hash map to count frequencies (anagrams, duplicates).
3Learn how hash maps achieve near-constant-time lookups under the hood (hashing + buckets).