Hash Map

O(n)

Use a hash map for O(1) lookup to track seen elements, frequencies, or complement values during array traversal.

Time: O(n)Space: O(n)

When to Use

  • Finding pairs/triplets with target sum
  • Counting frequency of elements
  • Checking for duplicates or anagrams
  • Storing indices for later lookup

Pattern Variants

Complement Lookup

Store complement values (target - current) to find pairs in single pass.

Use for: Two Sum, pair with target sum

Frequency Counter

Count occurrences of each element for comparison or finding duplicates.

Use for: Valid Anagram, first unique character, majority element

Index Storage

Store indices of elements for later reference or constraint checking.

Use for: Contains Duplicate II, finding subarrays with constraints

Interactive Visualization

Code
1function twoSum(nums, target) {
2  const map = new Map()
3 
4  for (let i = 0; i < nums.length; i++) {
5    const complement = target - nums[i]
6 
7    if (map.has(complement)) {
8      return [map.get(complement), i]
9    }
10 
11    map.set(nums[i], i)
12  }
13  return []
14}
Input Array
20
71
112
153
0
empty
1
empty
2
empty
3
empty
4
empty
5
empty
6
empty
7
empty
Output
Input: [2, 7, 11, 15]
Target: 9
Step 1/11Find two numbers that add up to target 9. We use a hash map to store numbers we've seen.
1 / 11
Key Insight:Store each number with its index. For each new number, check if its complement (target - num) was already stored. One pass = O(n) time.

Practice this Pattern

Go to Two Sum

Two Sum

Find two numbers that add up to target using hash map

Go to Valid Anagram

Valid Anagram

Check if two strings are anagrams using character frequency

Go to Group Anagrams

Group Anagrams

Group strings that are anagrams of each other

Go to Implement Trie (Prefix Tree)

Implement Trie (Prefix Tree)

Build insert/search/startsWith on a trie of characters

Go to Design Add and Search Words Data Structure

Design Add and Search Words Data Structure

Support addWord and search with wildcard dot matching

Go to Replace Words

Replace Words

Replace words in a sentence by the shortest dictionary root

Go to Search Suggestions System

Search Suggestions System

Return up to 3 lexicographically sorted suggestions while typing each prefix

Go to Stream of Characters

Stream of Characters

Implement a stream checker that detects any suffix matching inserted words

Go to Word Search II

Word Search II

Find all words in a board using trie-guided DFS

Go to Short Encoding of Words

Short Encoding of Words

Minimize encoded length by merging shared suffixes in a trie

Go to Magic Dictionary

Magic Dictionary

Implement buildDict + search allowing one character mismatch

Go to Longest Word in Dictionary

Longest Word in Dictionary

Find the longest word that can be built one character at a time

Go to Top K Frequent Elements

Top K Frequent Elements

Find the k most frequent elements using bucket sort