Hashing & Maps Master Recap — All Patterns & Templates
Sanjeev SharmaAdvertisement
Hashing & Maps — Master Recap
Problems 161–205 | 45 posts | Easy × 10, Medium × 30, Hard × 5
The 7 Core Patterns
| # | Pattern | Trigger | Example |
|---|---|---|---|
| 1 | Complement Map | "two elements sum to X" | Two Sum, 4Sum II |
| 2 | Frequency Counter | "count occurrences / anagram" | Valid Anagram, Group Anagrams |
| 3 | Prefix + Map | "subarray sum = k" | Subarray Sum=K, Divisible by P |
| 4 | Two-Way Map | "encode / decode / isomorphic" | Isomorphic Strings, TinyURL |
| 5 | LRU Cache | "evict least recently used" | LRU Cache |
| 6 | LFU Cache | "evict least frequently used" | LFU Cache |
| 7 | Bucket by Frequency | "top K / sort by freq" | Top K Frequent, All O'one |
Pattern Templates
1. Complement Map
seen = {}
for i, x in enumerate(nums):
if target - x in seen:
return [seen[target-x], i]
seen[x] = i
2. Frequency Counter
from collections import Counter
freq = Counter(arr)
# Validate: all freq values unique
len(set(freq.values())) == len(freq)
3. Prefix Sum + Map
from collections import defaultdict
prefix_count = defaultdict(int)
prefix_count[0] = 1
cur = 0
for x in nums:
cur += x
ans += prefix_count[cur - k]
prefix_count[cur] += 1
4. Prefix Mod + Map
# For divisibility problems
prefix_count = {0: -1} # or {0: 1}
cur_mod = 0
for i, x in enumerate(nums):
cur_mod = (cur_mod + x) % k
need = (cur_mod - target) % k
if need in prefix_count:
ans = max(ans, i - prefix_count[need])
if cur_mod not in prefix_count:
prefix_count[cur_mod] = i
5. LRU Cache
from collections import OrderedDict
class LRUCache:
def __init__(self, cap): self.cap = cap; self.cache = OrderedDict()
def get(self, key):
if key not in self.cache: return -1
self.cache.move_to_end(key); return self.cache[key]
def put(self, key, val):
if key in self.cache: self.cache.move_to_end(key)
self.cache[key] = val
if len(self.cache) > self.cap: self.cache.popitem(last=False)
6. LFU Cache (Three Maps)
# key_val, key_freq, freq_keys (OrderedDict), min_freq
# On access: move key to freq+1 bucket; update min_freq if old bucket empty
7. Bitmask Prefix XOR
# For "at most one odd frequency" problems
cnt = defaultdict(int); cnt[0] = 1; mask = 0
for c in s:
mask ^= 1 << (ord(c)-ord('a'))
ans += cnt[mask] # all even
for i in range(26): ans += cnt[mask ^ (1<<i)] # one odd
cnt[mask] += 1
Big O Reference
| Problem | Time | Space | Pattern |
|---|---|---|---|
| Two Sum | O(n) | O(n) | Complement Map |
| Group Anagrams | O(nk) | O(nk) | Frequency Map |
| LRU Cache | O(1) | O(cap) | OrderedDict |
| LFU Cache | O(1) | O(cap) | 3 Maps + min_freq |
| Subarray Sum=K | O(n) | O(n) | Prefix + Map |
| Longest Consecutive | O(n) | O(n) | HashSet |
| 4Sum II | O(n²) | O(n²) | Meet in Middle |
| Palindrome Pairs | O(nk²) | O(nk) | HashMap + Split |
| All O'one | O(1) | O(n) | DLL Buckets |
Problem Index by Pattern
Complement Map
- 01 Two Sum · 02 Valid Anagram (variant) · 26 Count Bad Pairs · 38 Count Good Meals · 40 4Sum II
Frequency Counter
- 02 Valid Anagram · 03 Ransom Note · 08 Find Common Characters · 09 Jewels & Stones · 12 Top K Frequent · 18 Find All Anagrams · 22 Wonderful Substrings (bitmask) · 35 Most Common Word
Prefix + Map
- 14 Subarray Sum=K · 15 Continuous Subarray Sum · 27 Make Sum Divisible by P · 37 Subarray Sum Div K
Two-Way Map
- 04 Isomorphic Strings · 05 Word Pattern · 29 Encode/Decode TinyURL · 30 Fraction to Decimal
LRU/LFU Cache Design
- 13 LRU Cache · 41 LFU Cache · 42 All O'one · 43 Design Twitter
Bucket / Sorted Map
- 12 Top K Frequent · 17 Insert Delete GetRandom · 19 Random Pick Weight · 20 Brick Wall · 36 Hand of Straights
Tree / Graph + Hash
- 24 Two Sum IV BST · 31 Find Duplicate Subtrees
MAANG Interview Priority
Must-Know (appear in 80%+ of top-company screens):
- Two Sum (complement map fundamentals)
- LRU Cache (design + DLL+HashMap)
- Group Anagrams (frequency map)
- Subarray Sum = K (prefix + map)
- Longest Consecutive Sequence (HashSet)
- Top K Frequent Elements (heap/bucket)
High Value (system design rounds):
- LFU Cache, All O'one, Design Twitter, Time-Based KV Store
Pattern Recognizers:
- Wonderful Substrings (bitmask XOR), Palindrome Pairs (split + reverse map), 4Sum II (meet in middle)
Common Mistakes
- Negative modulo: always use
((x % k) + k) % k - LRU eviction direction:
popitem(last=False)= evict oldest (front), not newest - LFU min_freq update: only increment if the evicted bucket matches
min_freq - Isomorphic vs anagram: isomorphic needs bijection, anagram just needs same chars
- OrderedDict move_to_end: call on both get AND put (even for existing keys)
Next Section → Stack & Queue (problems 206–250)
Advertisement
