You're in a coding interview. The problem asks you to find two numbers that sum to a target. You know you need a hash map... but then what?
Do you store the number as the key or the index? Do you check for the complement before or after adding to the map? What if there are duplicates?
This is the gap between knowing about hash maps and mastering the hash map pattern.
Hash maps are one of the most powerful tools in algorithm design. They transform O(n²) brute-force solutions into O(n) elegance by trading space for time. But the pattern isn't just "use a dictionary"—it's a family of techniques with distinct recognition signals, templates, and pitfalls.
This guide is the pillar article for everything hash map:
If you internalize this, hash maps stop being a guess and become a reliable O(1) lookup weapon you can deploy confidently in any interview.
At a high level, the hash map pattern is a way to achieve O(1) lookups by trading space for time. Instead of searching through data linearly or sorting it first, you preprocess information into a hash map for instant access.
The fundamental trade-off:
Think of it as building an index:
Array: [7, 2, 5, 8, 1, 3]
Without hash map (brute force):
To find if 5 exists: scan all elements → O(n)
With hash map:
Build: {7: 0, 2: 1, 5: 2, 8: 3, 1: 4, 3: 5}
To find if 5 exists: map.has(5) → O(1)Imagine you're looking for a book in a library:
The catalog takes up space, but it makes finding books instant.
Hash map problems test:
It's also a great discriminator: many candidates know "use a dict", but far fewer can articulate why this key/value pair is optimal and debug it under pressure.
At an intuitive level, the hash map pattern does three things:
Every hash map solution makes a conscious trade-off:
Time saved: O(n) → O(1) per lookup
Space cost: O(1) → O(n) for the mapThis trade-off is worth it when:
The key is what you'll look up. Good keys are:
Examples:
The value is what you need when you find the key. Common choices:
Many hash map problems boil down to:
"Have I seen this before? If yes, do something with the previous occurrence."
Examples:
This mental model helps you recognize hash map opportunities instantly.
You don't want to recognize hash maps halfway through a brute-force attempt. Here's a checklist and language cues to spot them immediately.
Use hash map if:
If any of these are true, consider a hash map first.
Strong hash map signals:
Examples:
Quick decision tree:
Do you need associated values (not just presence)?
├─ Yes → Use hash map
└─ No → Use hash set
Do you need O(1) lookup by arbitrary keys?
├─ Yes → Use hash map/set
└─ No → Use array (if indexed access is enough)Don't use hash maps when:
For deeper analysis, see When NOT to Use Hash Maps.
Hash map isn't one pattern—it's six distinct techniques that solve different types of problems. Understanding which pattern to use is the key to mastering hash maps.
Definition: Count how many times each element appears.
When to use:
Key/Value design:
Example:
# Count character frequencies
freq = {}
for char in s:
freq[char] = freq.get(char, 0) + 1See: Frequency Counter Pattern
Definition: Store the position(s) where each element appears.
When to use:
Key/Value design:
Example:
# Store last seen index
index_map = {}
for i, num in enumerate(nums):
index_map[num] = iDefinition: For each element, check if its complement exists.
When to use:
Key/Value design:
Example:
# Two Sum
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = iSee: Two Sum Pattern
Definition: Group elements by a computed property.
When to use:
Key/Value design:
Example:
# Group anagrams
groups = {}
for word in words:
key = ''.join(sorted(word))
if key not in groups:
groups[key] = []
groups[key].append(word)See: Grouping Pattern
Definition: Track whether you've seen an element before.
When to use:
Key/Value design:
Example:
# Contains duplicate
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return FalseNote: Often a set is sufficient (don't need values).
Definition: Store prefix sums to find subarrays with target sum.
When to use:
Key/Value design:
Example:
# Subarray sum equals k
count = 0
prefix_sum = 0
sum_count = {0: 1} # Critical: handle subarrays from index 0
for num in nums:
prefix_sum += num
if prefix_sum - k in sum_count:
count += sum_count[prefix_sum - k]
sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1For interview performance, you want one mental template per pattern and language.
from collections import Counter
# Approach 1: Using Counter (recommended)
freq = Counter(nums)
# freq[x] gives count of x
# Approach 2: Manual dict
freq = {}
for num in nums:
freq[num] = freq.get(num, 0) + 1
# Approach 3: defaultdict
from collections import defaultdict
freq = defaultdict(int)
for num in nums:
freq[num] += 1# Store last index
index_map = {}
for i, num in enumerate(nums):
index_map[num] = i
# Store all indices
from collections import defaultdict
index_map = defaultdict(list)
for i, num in enumerate(nums):
index_map[num].append(i)def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []from collections import defaultdict
groups = defaultdict(list)
for item in items:
key = compute_key(item) # e.g., sorted(item)
groups[key].append(item)# Use set (more efficient than dict)
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return Falsedef subarray_sum(nums, k):
count = 0
prefix_sum = 0
sum_count = {0: 1}
for num in nums:
prefix_sum += num
if prefix_sum - k in sum_count:
count += sum_count[prefix_sum - k]
sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1
return count// Using HashMap
Map<Integer, Integer> freq = new HashMap<>();
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (seen.containsKey(complement)) {
return new int[] {seen.get(complement), i};
}
seen.put(nums[i], i);
}
return new int[] {};
}Map<String, List<String>> groups = new HashMap<>();
for (String word : words) {
char[] chars = word.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
groups.putIfAbsent(key, new ArrayList<>());
groups.get(key).add(word);
}// Using Map
const freq = new Map();
for (const num of nums) {
freq.set(num, (freq.get(num) || 0) + 1);
}
// Using object (for simple keys)
const freq = {};
for (const num of nums) {
freq[num] = (freq[num] || 0) + 1;
}function twoSum(nums, target) {
const seen = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (seen.has(complement)) {
return [seen.get(complement), i];
}
seen.set(nums[i], i);
}
return [];
}const groups = new Map();
for (const word of words) {
const key = word.split('').sort().join('');
if (!groups.has(key)) {
groups.set(key, []);
}
groups.get(key).push(word);
}Let's walk through three canonical hash map problems with diagrams and pitfalls.
Problem: Given an array of integers nums and an integer target, return indices of the two numbers that add up to target.
This is the poster child for complement search:
For nums = [2, 7, 11, 15], target = 9:
Step i num complement seen action
----- - --- ---------- ------------- ----------------------------
0 0 2 9-2=7 {} 7 not in seen, add {2: 0}
1 1 7 9-7=2 {2: 0} 2 in seen! return [0, 1]def twoSum(nums: List[int], target: int) -> List[int]:
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []Key points:
Common pitfalls:
For more on this pattern, see Two Sum Pattern.
Problem: Given an array of strings strs, group the anagrams together.
This is a classic grouping pattern:
Anagrams have the same characters, just rearranged. If we sort each word, anagrams become identical:
Use the sorted string as the grouping key.
from collections import defaultdict
def groupAnagrams(strs: List[str]) -> List[List[str]]:
groups = defaultdict(list)
for word in strs:
# Sorted string is the key
key = ''.join(sorted(word))
groups[key].append(word)
return list(groups.values())Example trace:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"]
Step 1: "eat" → key="aet" → groups = {"aet": ["eat"]}
Step 2: "tea" → key="aet" → groups = {"aet": ["eat", "tea"]}
Step 3: "tan" → key="ant" → groups = {"aet": ["eat", "tea"], "ant": ["tan"]}
Step 4: "ate" → key="aet" → groups = {"aet": ["eat", "tea", "ate"], "ant": ["tan"]}
Step 5: "nat" → key="ant" → groups = {"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"]}
Step 6: "bat" → key="abt" → groups = {"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"]}
Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]Key points:
Alternative approaches:
For deep dive, see Group Anagrams Deep Dive.
Problem: Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals k.
This is a prefix sum + hash map pattern:
Brute force: Check all subarrays → O(n²)
Key insight: If prefix[j] - prefix[i] = k, then subarray from i+1 to j has sum k.
Rearrange: prefix[i] = prefix[j] - k
So for each position j, check if prefix[j] - k exists in our map.
def subarraySum(nums: List[int], k: int) -> int:
count = 0
prefix_sum = 0
sum_count = {0: 1} # Critical: handle subarrays starting from index 0
for num in nums:
prefix_sum += num
# Check if (prefix_sum - k) exists
if prefix_sum - k in sum_count:
count += sum_count[prefix_sum - k]
# Add current prefix sum to map
sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1
return countExample trace:
nums = [1, 2, 3], k = 3
Step num prefix check sum_count count
----- --- ------ -------------- ------------------------- -----
init - 0 - {0: 1} 0
0 1 1 1-3=-2 (no) {0: 1, 1: 1} 0
1 2 3 3-3=0 (yes!) {0: 1, 1: 1, 3: 1} 1
2 3 6 6-3=3 (yes!) {0: 1, 1: 1, 3: 1, 6: 1} 2
Found 2 subarrays: [1,2] and [3]Key points:
{0: 1} to handle subarrays starting from index 0Common mistakes:
{0: 1} initializationFor debugging guide, see Subarray Sum Mistakes.
Once you're comfortable with basic patterns, you'll see richer variations.
Sometimes you need to group by multiple properties:
# Group by (row, column sum)
groups = {}
for item in items:
key = (item.row, item.col_sum)
if key not in groups:
groups[key] = []
groups[key].append(item)Python: Tuples are hashable (immutable)
Java: Create composite key class with proper hashCode() and equals()
JavaScript: Use string concatenation or Map with array keys (careful!)
For complex keys, you need proper hash functions:
Java:
class Point {
int x, y;
@Override
public int hashCode() {
return Objects.hash(x, y);
}
@Override
public boolean equals(Object obj) {
if (!(obj instanceof Point)) return false;
Point p = (Point) obj;
return x == p.x && y == p.y;
}
}
Map<Point, Integer> map = new HashMap<>();Python:
# Use tuple or frozen dataclass
from dataclasses import dataclass
@dataclass(frozen=True)
class Point:
x: int
y: int
map = {Point(1, 2): "value"}When you need insertion order:
Python: dict (ordered since Python 3.7) or OrderedDict
Java: LinkedHashMap
JavaScript: Map (maintains insertion order)
Quick rule:
# Contains Duplicate - set is enough
def containsDuplicate(nums):
return len(nums) != len(set(nums))
# Two Sum - need indices, use map
def twoSum(nums, target):
seen = {} # map, not set
for i, num in enumerate(nums):
if target - num in seen:
return [seen[target - num], i]
seen[num] = iFor detailed comparison, see Hash Map vs Hash Set.
If your hash map solution fails, use this checklist:
❓ Is your key unique enough?
❓ Is your key immutable?
❓ Is your value what you actually need?
❓ Are you checking before accessing?
# Wrong - may crash
value = map[key]
# Right
if key in map:
value = map[key]
# Or use .get() with default
value = map.get(key, default)❓ Are you updating the map at the right time?
# Two Sum - check BEFORE adding
if complement in seen:
return [seen[complement], i]
seen[num] = i # Add after checking
# Subarray Sum - check BEFORE adding
if prefix_sum - k in sum_count:
count += sum_count[prefix_sum - k]
sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1❓ How are you handling duplicates?
See Handling Duplicates.
❓ Did you test these?
❓ Is the hash map too large?
See Memory Optimization.
Hash map operations:
| Operation | Average | Worst Case | Notes |
|---|---|---|---|
| Insert | O(1) | O(n) | Worst case: all keys collide |
| Lookup | O(1) | O(n) | Worst case: all keys collide |
| Delete | O(1) | O(n) | Worst case: all keys collide |
In practice: Modern hash maps (Python dict, Java HashMap, JS Map) have excellent average-case performance. Worst case is extremely rare with good hash functions.
What is a collision?
When two different keys produce the same hash code.
How it's handled:
Impact on complexity:
In interviews: You can assume O(1) unless specifically asked about collisions.
Without hash map:
Time: O(n²) (nested loops)
Space: O(1)
With hash map:
Time: O(n) (single pass)
Space: O(n) (store all elements)
Trade-off: Spend O(n) space to save O(n²) → O(n) timeWhen it's worth it:
When it's not worth it:
❌ Wrong:
# Two Sum - storing value as value (can't look up by value!)
seen = {}
for i, num in enumerate(nums):
seen[i] = num # Wrong: key should be num, value should be i✅ Correct:
seen = {}
for i, num in enumerate(nums):
seen[num] = i # Right: key is num (what we search), value is index (what we need)❌ Wrong:
# Two Sum - adding before checking fails when target = 2 * num
seen[num] = i
if target - num in seen:
return [seen[target - num], i]✅ Correct:
# Check before adding
if target - num in seen:
return [seen[target - num], i]
seen[num] = i❌ Wrong:
# May crash if key doesn't exist
count = freq[char]✅ Correct:
# Use .get() with default
count = freq.get(char, 0)
# Or check first
if char in freq:
count = freq[char]❌ Wrong:
# Lists are not hashable in Python
key = [1, 2, 3]
map[key] = "value" # TypeError!✅ Correct:
# Use tuple (immutable)
key = (1, 2, 3)
map[key] = "value"For comprehensive debugging, see Common Hash Map Mistakes.
Hash maps are powerful, but not always optimal.
Problem: Iterate through keys in sorted order
Why hash map fails: Hash maps don't maintain order (or maintain insertion order, not sorted order)
Use instead: TreeMap (Java), sorted dict (Python sortedcontainers), or sort the keys
Problem: "Find all elements between x and y"
Why hash map fails: No efficient way to query ranges
Use instead: Balanced BST, segment tree, or sorted array with binary search
Problem: O(n) space is too much
Why hash map fails: Requires extra space
Use instead: In-place algorithms, two pointers, bit manipulation
Problem: Array has 5 elements
Why hash map fails: Overhead of hash map isn't worth it
Use instead: Simple array scan (O(n) is fine for small n)
Problem: Check if element exists
Why hash map is overkill: Don't need key-value pairs
Use instead: Hash set (more memory efficient)
For detailed analysis, see When NOT to Use Hash Maps.
Start here to build pattern recognition:
Build fluency with variations:
Master edge cases and optimizations:
The hash map pattern is a fundamental tool that transforms O(n²) brute force into O(n) elegance by trading space for time.
Key principles:
The mental model:
"Have I seen this before? If yes, what do I need to know about it?"
When to use hash maps:
When NOT to use hash maps:
Next steps:
Master these patterns, and hash maps stop being a guess and become a reliable weapon in your interview arsenal.
LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.
Also compatible with Edge, Brave, and Opera
Add to Chrome for free