Hash Map Pattern

Why this pattern matters for LeetCode

Hash Map problems disguise themselves as array problems. The real ask is: look up something from earlier in the input. Without a hash map, you write nested loops — for each element, scan everything before it. That is O(n²) and times out on large inputs. The hash map fixes this by letting you store what you have seen and look it up in constant time. You pay a little extra space to avoid a lot of wasted time.

What the Hash Map pattern is

A hash map stores key-value pairs and retrieves any value by key in O(1) average time. The core idea is simple: instead of scanning the array every time you need to find something, store what you've already seen so you can check it instantly. In the Two Sum pattern, you store each number and its index as you go. When you see a new number, you check whether its complement is already in the map before adding the current number. One pass, done.

Reach for Hash Map when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use Hash Map

• ✓Finding pairs or complements in an unsorted array (Two Sum style)
• ✓Counting how often each value appears
• ✓Grouping elements by a shared property (Group Anagrams)
• ✓Looking up whether you have seen something before, and retrieving data about it
• ✓Replacing an O(n) inner loop with a single O(1) lookup

When NOT to use Hash Map

• ✕You only need to check existence, not store any extra data — a Set is simpler
• ✕You only need to count occurrences — a plain object or Frequency Map is more readable
• ✕The input is already sorted and you need pairs — Two Pointers may be O(1) space instead
• ✕The key space is a small integer range — an array can act as a direct-address table

Better alternative: In those cases, a Set, Frequency Map, or Two Pointers may be simpler and use less space.

JavaScript code template

Two Sum core pattern — O(n) time, O(n) space

const map = new Map();

for (let i = 0; i < nums.length; i++) {
  const complement = target - nums[i];

  if (map.has(complement)) {
    return [map.get(complement), i];
  }

  // Check FIRST, then store — avoids matching an element with itself
  map.set(nums[i], i);
}

return [];

For each number, compute what value would pair with it to reach the target. Check the map for that complement first. If it's there, you're done. If not, store the current number so a future element can find it. The 'check before store' order is critical — it prevents a single element from matching itself.

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Identify what you want to store as the key (the number itself) and the value (its index).
2. 2Start the loop. For each element, figure out what you'd need to have already seen.
3. 3Check the map for that needed value before doing anything else.
4. 4If found, you have your answer — return or record it.
5. 5If not found, store the current element in the map so future iterations can find it.
6. 6Continue until the loop ends or the answer is found.

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

• Two Sum

  The classic hash map problem — store each number's index and find its complement in one pass.

  Free→
• Group Anagrams

  Group strings by their sorted character key stored in a hash map.

  Premium→
• Top K Frequent Elements

  Count frequencies with a map, then find the top k.

  Premium→
• Longest Consecutive Sequence

  Use a hash set to check sequence membership in O(1) instead of sorting.

  Premium→

Coming soon

• Subarray Sum Equals K

  Store prefix sums in a map and check for the target difference at each step.

  Coming soon

Common mistakes beginners make

• ✕Storing the value before checking — this makes an element match itself, which is the classic Two Sum off-by-one bug.
• ✕Using a plain object {} when keys could be non-strings or negative numbers. Use Map() for safety.
• ✕Reaching for a Set when you need to store extra data per key (like an index or count) — Set only stores existence.
• ✕Writing a nested loop instead — if you're scanning the whole array for each element, you've missed the hash map optimization.
• ✕Forgetting that Map.get() can return undefined — always handle the case where the key doesn't exist before using the value.

Hash Map vs Set vs Frequency Map

Choose the right tool for the job.

Time and space complexity

You visit each element once (O(n)) and each map lookup or insert is O(1) average. You store at most n entries in the map, so space is O(n). In the rare worst case where every key hashes to the same bucket, lookup degrades to O(n) — but this doesn't happen with standard inputs.

Frequently asked questions

How do I know when to reach for a hash map?

Ask: 'Do I need to look up something I've already seen, while also storing data about it?' If yes, use a hash map. If you only need to check existence (not retrieve data), a Set is enough. If you only need counts, a plain object works fine.

Why does Two Sum use a hash map instead of sorting and using two pointers?

Both work, but they have different tradeoffs. Sorting + two pointers is O(n log n) time and O(1) extra space but destroys the original indexes. Hash map is O(n) time and O(n) space and preserves indexes. Since Two Sum asks for indexes, the hash map approach is cleaner and faster.

What's the difference between a hash map and a Set?

A Set only stores keys — it tells you 'have I seen this value before?' A Map stores key-value pairs — it tells you 'have I seen this value, and what data did I record about it?' Use a Map when you need to retrieve something (an index, a count, an object) alongside the key.

Is hash map lookup really O(1)?

On average, yes. A hash function converts the key to an array index in constant time, and the lookup is one array access. In the worst case (all keys collide to the same bucket), it degrades to O(n). For LeetCode problems, assume O(1) average — it's the intended complexity.