Hash Map / Set
When to use it: Trade memory for O(1) lookups: count, deduplicate, or remember what you have already seen.
Signals in the problem
- "Find a pair / duplicate / complement"
- "Group items that are equivalent" (anagrams, same key)
- A brute force that compares every pair
Core idea
Walk the input once and store what you have seen in a hash map or set, keyed by whatever you will need to look up later (the value, its complement, a sorted signature, a count). Each lookup is O(1) on average, so a pairwise O(n²) check becomes O(n).
Template (Python)
seen = {}
for i, x in enumerate(nums):
if target - x in seen:
return [seen[target - x], i]
seen[x] = i - Complexity
- O(n) time, O(n) extra space.
- Common mistake
- Inserting before checking. In Two Sum, look up target - x first and insert x after, or an element can pair with itself.
Practice problems (17)
- Two Sum easy
- Valid Anagram easy
- Group Anagrams medium
- Longest Consecutive Sequence medium
- Contains Duplicate easy
- Isomorphic Strings easy
- Majority Element easy
- Intersection of Two Arrays easy
- Ransom Note easy
- Word Pattern easy
- Custom Sort String medium
- H-Index medium
5 more, and progress tracking, on Blind 75, LeetCode 150, DSA Sheet (filter by “Hash Map / Set”).