Hash Maps
- Identify the inner-loop search pattern in O(n²) solutions and replace it with an O(1) hash map lookup to drop to linear time
- Decide between one-pass and two-pass complement lookup based on whether valid matches can appear after the current element
- Pair prefix sums with hash maps to count subarrays with a target sum, the approach that works when negative values make sliding window unreliable
- Choose the right hash map key for grouping problems so that equivalent elements collide: sorted characters, canonical forms, computed signatures
A hash map stores key-value pairs and retrieves any value in O(1) average time, no matter how large the data set. This turns brute force solutions that search for matches in O(n) per element into single-pass O(n) algorithms. But choosing the wrong key, storing the wrong value, or missing an initialization like {0: 1} produces code that looks correct but silently fails on edge cases.
What Is a Hash Map?
In most brute force solutions, the bottleneck is a repeated search: for each element, scan the rest of the array looking for a match. A hash map eliminates that scan. It stores data so that any lookup takes O(1) average time, turning an O(n) inner search into a single operation. That is why hash maps appear across so many interview patterns.
Linear Search · O(n)
Find "alice" in this array. No structure, no shortcuts. Must check each slot.
Hash Lookup · O(1)
What if we could compute WHERE to look instead of searching?
- The hash function converts a key to a number
- Modulo maps that number to an array index
- Arrays give O(1) access by index
If you can express what you need as a key, the hash function computes its position directly instead of scanning.
In Python, dict is the hash map. For counting, Counter is a specialized dict that defaults missing keys to 0. For maps where missing keys should auto-initialize, defaultdict avoids the repeated if key not in dict check.
What Hash Maps Actually Do
Start with the brute force: for each of n elements, scan all other elements to find a match. That is n iterations times O(n) work each, giving O(n²). What if the inner search cost O(1) instead of O(n)? Total work drops to n times O(1), which is O(n). A hash map provides exactly that O(1) inner lookup. Every hash map optimization follows the same three steps. Identify the repeated search, precompute its answer into a map, replace the search with a lookup.
x in list (O(n) in Python), using .index(), or re-scanning a substring. Whenever you see O(n²) runtime, ask: where is the repeated search? That search is your hash map target.How a Hash Map Replaces the Inner Loop
Two Sum is the cleanest place to see the four hash map decisions: what value to search for, what to use as the key, what to store as the value, and whether to check before or after storing. The same four decisions apply to every hash map transformation.
Two Sum: Four Design Decisions
Problem: Find two indices where nums[i] + nums[j] == target.
Decision 1: What am I searching for?
The inner loop checks every other element to see if it equals target - nums[i]. We are searching for a complement.
Decision 2: What is the key?
We need to look up whether a specific value exists. The key is the value itself. When we encounter 7 and need to know if 3 is in the map, we look up 3 as the key.
Decision 3: What is the value?
The problem asks for indices, not just whether a match exists. So the map stores value to index. A set would tell us "yes, 3 exists" but not where it is.
Decision 4: Check before or after storing?
If we store first, an element could match itself. Check first, then store, so each element only matches elements that came before it. One pass suffices because if (a, b) is a valid pair, whichever you reach second will find the other already in the map.
The Same Decisions, Different Problems
Subarray Sum Equals K: The same four decisions apply, but Decision 1 is harder because the "search" is hidden inside prefix sums. You are not searching for an element in the array. You are searching for a previous prefix sum that, when subtracted from the current prefix sum, equals k. We cover this in the deep dive section below.
Group Anagrams: This uses a different shape of the same idea. Instead of searching for a complement, you compute a canonical form (sorted characters) and group items by it. Decision 2, choosing the right key, is the hard part. The key must be identical for items that belong together and different for items that do not.
Two Sum · target = 6
For each element, check if its complement exists. O(n) nested loops become O(n).
A set can answer "does this value exist?" in constant time, which seems like enough. But Two Sum does not just ask whether two numbers sum to the target. It asks for the indices of those two numbers. A set discards positional information entirely.
Consider nums = [3, 3] with target = 6. A set gives {3}. You know 3 exists, but you cannot distinguish the first 3 from the second 3. You have no way to produce the answer [0, 1] because the set does not remember where each value appeared.
A hash map stores value to index. When you encounter the second 3 at index 1, you look up the complement (6 minus 3 = 3) and find it at index 0 in the map. The map gives you both the existence check and the positional information in a single lookup.
The general rule: when a problem asks "which elements" or "at what positions," you need a map. When it only asks "does something exist," a set is sufficient and communicates intent more clearly.
Complement Lookup Across Problems
Many problems are variations of Two Sum. The only difference is how the complement is computed.
| Problem | What You Have | Complement Formula |
|---|---|---|
| Two Sum | Current num | target - num |
| Subarray Sum = K | Current prefix sum | current_sum - k |
| 4Sum II | Two nums from A,B | -(a+b) in map of c+d |
| Count pairs diff = k | Current num | num + k or num - k |
| Continuous Subarray Sum | current_sum % k | Same remainder seen before |
When a Hash Map Is a Good Fit
Six problem signals point toward a hash map solution. Recognizing the signal early narrows the design space before you start coding.
- Repeated lookup. The brute force has an inner loop that searches for something on every iteration. A hash map stores the answers so each search costs O(1) instead of O(n).
- Complement search. You can compute exactly what the matching element must be. Instead of checking every pair, compute the complement and look it up directly.
- Frequency counting. The answer depends on how many times elements appear. Build a count map in one pass, then query it.
- Grouping by canonical key. Equivalent items share a computable property. The hash map groups them by that property in a single pass.
- Prefix sum memory. Subarray sum problems with possible negative values cannot use sliding window. A hash map stores prefix sums so that complement lookup finds subarrays with a target sum in O(1).
- Auxiliary state inside another pattern. Sliding window uses a frequency map for window contents. DFS and BFS use a visited map for metadata. DP uses a hash map for memoization. In each case, the hash map provides O(1) state queries that the outer pattern depends on.
Hash Map Templates
Five templates cover the vast majority of hash map interview problems.
Complement Lookup
One-pass check-then-store. For each element, compute what would complete it, check if that exists, then store the current element for future lookups. Check-then-store ordering prevents an element from matching itself. One pass suffices because if (a, b) is a valid pair, whichever you reach second will find the other already in the map.
When to use: Finding pairs with a specific relationship (sum, difference, product).
Common variations:
- • Two Sum (complement = target - num)
- • Pair with difference k (complement = num + k or num - k)
- • 4Sum II: precompute all sums a+b from two arrays into a count map, then for each c+d pair check if -(c+d) exists. Splits O(n⁴) into two O(n²) passes.
Frequency Counting
Build a count map in one pass, then query it. Two separate phases (count everything, then query) work because you cannot answer frequency questions until you have seen all the data.
When to use: Any problem asking about frequencies, majorities, top-k, or comparing character distributions.
Find Majority Element
7 elements. Majority = appears more than 3 times. One pass with a frequency map.
Common variations:
- • Majority Element (count > n/2)
- • Top K Frequent: use freq.most_common(k), or build a bucket array where index = frequency and scan from the highest bucket down. The bucket approach avoids sorting and runs in O(n).
- • Valid Anagram (Counter(s) == Counter(t))
Grouping by Key
Compute a canonical key for each item, then group items with the same key. defaultdict(list) handles first-time keys automatically, avoiding the if-key-not-in-dict boilerplate.
When to use: Grouping equivalent items: anagrams, isomorphic strings, items sharing a computed property.
Common variations:
- • Group Anagrams: key = tuple(sorted(s)). Sorting "eat" and "tea" both produce ('a','e','t'), so they land in the same bucket. An alternative key is a 26-element character count tuple, which runs in O(m) per string instead of O(m log m).
- • Isomorphic Strings: "egg" and "add" are isomorphic because each character in one maps to exactly one character in the other (e maps to a, g maps to d). Key = tuple of first-occurrence positions. "egg" produces (0, 1, 1), "add" produces (0, 1, 1). Two strings are isomorphic when their position patterns match.
- • Group Shifted Strings: "abc" and "bcd" differ by a constant shift of 1. Key = tuple of differences between consecutive characters mod 26. "abc" produces (1, 1), "bcd" produces (1, 1). Mod 26 handles wraparound, so "xyz" and "yza" also group together.
Prefix Sum + Hash Map
Running prefix sum with complement lookup. The {0: 1} initialization accounts for subarrays starting at index 0, where the prefix sum itself equals k.
When to use: Count or find contiguous subarrays with a target sum, or sum divisible by k.
Common variations:
- • Subarray Sum Equals K (complement = current_sum - k)
- • Continuous Subarray Sum: key = current_sum % k. Two prefix sums with the same remainder mod k means the subarray between them sums to a multiple of k. Store the first index for each remainder to check the length >= 2 requirement.
- • Contiguous Array: treat 0 as -1, then the problem becomes "find longest subarray with sum 0." Store the first index where each prefix sum appears. The longest subarray is the maximum gap between matching prefix sums.
Sliding Window State
Frequency map tracking window contents. Increment on entry, decrement on exit, delete zero-count keys to keep len(freq) equal to the number of distinct elements in the window. Most validity checks depend on that count being accurate.
When to use: Sliding window problems where you need to track distinct elements, character frequencies, or window validity.
Common variations:
- • Longest Substring with K Distinct Characters
- • Minimum Window Substring: maintain two frequency maps. One for the required characters (need), one for the current window (have). Shrink from the left once all required characters are covered, tracking the smallest valid window seen so far.
- • Longest Substring Without Repeating Characters
Group Anagrams: Key Design
Problem: Given an array of strings, group anagrams together. Return a list of groups.
What makes "eat" and "tea" the same thing in this problem is that they contain the same characters. What makes "eat" and "bat" different is that they do not. The exact property is the multiset of characters. The challenge is expressing that property as a single hashable value Python can use as a dictionary key. The raw string does not work because "eat" and "tea" are different strings. The string's length does not work because "eat" and "bat" both have length 3 but are not anagrams.
Group Anagrams
Anagrams share the same sorted characters. Sort each string to get a canonical key.
The Discovery Process
Given: ["eat", "tea", "tan", "ate", "nat", "bat"]
Step 1: What makes "eat" and "tea" equivalent? Same characters. "tan" and "nat" also share the same characters. "bat" is alone.
Step 2: How do I capture "same characters" as an identical, hashable value?
- Can't use the string itself (different order)
- Can't use length (too broad, "bat" also has length 3)
- Sorted characters: "eat" sorts to "aet", "tea" sorts to "aet". Identical.
Step 3: Key = tuple(sorted(s)). Why tuple? Lists aren't hashable.
key = tuple(sorted(s)): Sorting removes the arbitrary character ordering that makes "eat" different from "tea" while preserving the exact character identity that makes "eat" different from "bat." After sorting, all anagrams of "eat" become "aet." The tuple wrapper is required because Python lists are not hashable and cannot serve as dictionary keys. Without this: using the raw string as key puts "eat," "tea," and "ate" into three separate groups, and using a list instead of tuple crashes at runtime.
groups = defaultdict(list): A defaultdict with list as the factory function creates an empty list automatically when a new key is first accessed. Without it, you would need to check whether the key already exists before appending, or use setdefault on every iteration. The defaultdict removes that boilerplate and makes the intent clear: we are grouping items.
groups[key].append(s): The original string is appended, not the sorted key. The key is the grouping mechanism. The values stored in each group are the original inputs, because that is what the problem asks you to return. Storing the sorted key instead would lose the original strings entirely.
Why It Works
A good key satisfies two requirements: same result for items that belong together, and different results for items that don't. Sorting removes the arbitrary character ordering while preserving the exact character set.
Alternative key: Character count as tuple. O(n) instead of O(n log n) but more complex. For interviews, sorted is fine.
String length seems like a reasonable grouping property at first glance. Anagrams do have the same length, so grouping by length puts all anagrams into the same bucket. But "eat" and "bat" both have length 3 and are not anagrams. Length groups too broadly. It is a necessary condition for anagram equivalence but not a sufficient one, so unrelated strings end up in the same group.
The opposite mistake is grouping by first character. This splits "eat" and "ate" into different groups even though they are anagrams, because their first characters differ. First character groups too narrowly in one dimension and misses the property that actually defines anagram equivalence.
The right key captures exactly the property that makes items equivalent and nothing more. For anagrams, that property is the multiset of characters. Sorted characters express this precisely: same output for all anagrams of a word, different output for any non anagram. No spurious collisions, no spurious splits.
Subarray Sum Equals K: Prefix Sum
Problem: Given an array of integers and a target k, count the number of contiguous subarrays that sum to exactly k.
Your first instinct might be sliding window. Sliding window relies on monotonicity: adding an element always increases the window sum. When the array contains negative numbers, that assumption breaks, so sliding window cannot solve this problem in general.
Prefix sums provide the path forward. If prefix[j] minus prefix[i] equals k, the subarray between positions i and j sums to k. Rearranging gives prefix[i] = prefix[j] minus k. This is a complement lookup with the same structure as Two Sum, but the "elements" are prefix sums and the "target" is k.
Subarray Sum = 5
Start with {0: 1}. When prefix_sum equals 5, the complement is 0. This seed catches subarrays starting from index 0.
Prefix Sums as Complements
If prefix[j] - prefix[i] = k, then the subarray [i+1...j] has sum k. Rearranging: prefix[i] = prefix[j] - k. This is a complement lookup on prefix sums.
prefix_count = {0: 1}: This represents the "empty prefix," a prefix sum of zero that exists once before any element is processed. When the running sum equals k, the complement is zero. If zero is not already in the map, the algorithm misses every subarray that starts at index 0 and sums to k. Without this: on [1, 2, 3] with k = 3, the subarray [1, 2] starting at index 0 has a running sum of 3 and a complement of 0, so the lookup fails and that subarray is never counted.
complement = current_sum - k: This is Two Sum applied to prefix sums. You are asking: "is there an earlier position where the running sum was exactly current_sum minus k?" If so, the subarray between that earlier position and the current position sums to k. The algebra is prefix[j] minus prefix[i] equals k, rearranged to prefix[i] equals prefix[j] minus k.
count += prefix_count.get(complement, 0): Multiple earlier positions can have the same prefix sum, and each one defines a different subarray ending at the current position with sum k. You must count all of them, not just check whether one exists. Without this: on [1, -1, 1, -1, 1] with k = 0, multiple prefix sums collide, and checking only existence misses valid subarrays.
prefix_count[current_sum] = ...: Store the current prefix sum after checking, not before. Same principle as Two Sum. If you store first, you could find the current prefix sum as its own complement when k equals zero. The store after check ordering prevents a position from pairing with itself.
Sliding window works by expanding the right boundary to include more elements and contracting the left boundary to exclude them. The key assumption is monotonicity: adding an element always increases the window sum, and removing one always decreases it. When that holds, you can stop expanding once the sum exceeds k and start shrinking instead. The window converges on the right answer.
Negative numbers destroy this assumption. Adding the next element might decrease the sum. Shrinking from the left might increase or decrease it depending on the sign of the removed element. The window loses its monotonic behavior, and you can no longer make any guarantees about when to expand or contract.
Consider nums = [1, -1, 1, 1, 1] with k = 3. After processing the first two elements, the sum is 0. A sliding window would keep expanding, never knowing whether to shrink. The subarray [1, 1, 1] starting at index 2 is the answer, but the window has no way to discover that shrinking past the -1 is the right move.
The prefix sum approach does not depend on monotonicity at all. It depends on complement lookup, which works regardless of the signs in the array. That is why prefix sum plus hash map is the correct tool whenever the array can contain negatives or zeros. The rule: if all elements are guaranteed positive, sliding window works for subarray sum problems. If negatives are possible, use prefix sum plus hash map.
LRU Cache: Hash Map + Linked List
Problem: Design a data structure that supports get(key) and put(key, value) in O(1), evicting the least recently used item when capacity is exceeded.
This problem requires two operations in constant time: looking up a value by key, and evicting the least recently used item. A hash map gives O(1) lookup by key but cannot tell you which entry was accessed least recently without scanning every entry. A linked list can maintain access order directly but cannot find a node by key without walking the list from head to tail.
Even when you already hold a reference to a node in a singly linked list, removing that node is O(n) because you need access to the predecessor, which requires walking from the head. A doubly linked list solves this by storing a prev pointer at every node.
Two Structures, One Goal
Neither data structure alone gives O(1) for both operations. A hash map gives O(1) lookup by key but can't track recency order. A linked list gives O(1) removal/insertion at known positions but can't find nodes by key. Combining them: the hash map stores key to node pointer, and the doubly linked list maintains recency order.
Worked Example
Capacity = 2:
| Operation | Cache State (MRU to LRU) | Return |
|---|---|---|
| put(1, "A") | [1:A] | - |
| put(2, "B") | [2:B, 1:A] | - |
| get(1) | [1:A, 2:B] (1 moved to front) | "A" |
| put(3, "C") | [3:C, 1:A] (2 evicted) | - |
| get(2) | [3:C, 1:A] (2 not found) | -1 |
self.cache = {}: The hash map stores key to node pointers, not key to value. Storing the actual node reference lets you jump directly to any node in the linked list for O(1) removal. If you stored only the value, finding the node to move would require walking the list, costing O(n).
self.head = Node(); self.tail = Node(): These are dummy sentinel nodes that never hold real data. Their purpose is to eliminate edge cases. With dummies, every real node always has valid prev and next pointers, so _remove and _add_front work uniformly. Without this: you need "if self.head is None" checks in every method, which is tedious and error prone in a live interview.
self._remove(node); self._add_front(node): Accessing a key makes it the most recently used. The node must move from wherever it currently sits in the list to the front. The hash map reference to the node stays valid because the same node object is reused, only its position in the list changes.
del self.cache[lru.key]: Eviction must happen in both structures, not just one. The node stores its own key as an attribute specifically to make this deletion possible. Without the key stored on the node, you would need a reverse lookup from value to key, requiring either another hash map or an O(n) scan. Without this: the dict grows unbounded, stale entries return wrong values, and capacity tracking breaks.
Why Dummy Head and Tail?
Dummy nodes eliminate edge cases. Without them, adding to an empty list or removing the last node requires special handling. With dummies, every real node always has a valid prev and next, so _remove and _add_front work uniformly.
Why Doubly Linked, Not Singly?
Removing a node from the list means rewiring its predecessor's next pointer to skip over it. That requires access to the predecessor. In a singly linked list, the only way to reach a node's predecessor is to walk from the head, which costs O(n) even when you already hold a direct reference to the node itself. A doubly linked list solves this by storing a prev pointer at every node, so removal becomes four pointer reassignments regardless of where the node sits. The hash map gives you O(1) access to the node. The doubly linked list gives you O(1) removal of that node. Neither structure provides both on its own, and that is the entire reason LRU Cache requires the combination.
The first tempting approach is a hash map with timestamps. Record the access time for each key, and when the cache is full, scan the entire map to find the entry with the oldest timestamp. Lookup is O(1) but eviction requires scanning every entry to find the minimum timestamp. That scan costs O(n), which violates the O(1) requirement.
The second tempting approach is an ordered list or deque. Insert at the front when a key is accessed, evict from the back. This maintains recency order, but finding a key by value requires walking the list from head to tail. That search costs O(n), making get() linear.
The third approach that actually works in Python is OrderedDict, which is a hash map combined with a doubly linked list internally. It gives O(1) for both operations. But interviewers asking this question want you to implement the underlying mechanism, not call a library. They want to see that you understand why the combination is necessary and how the pointer manipulation works.
O(1) random access by key requires a hash based structure, and O(1) order maintenance requires linked list pointers. No single structure provides both, so the combination is the only way to satisfy both requirements.
Longest Consecutive Sequence
Problem: Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Must run in O(n) time.
Sorting and scanning for consecutive runs gives O(n log n), but the problem requires O(n). A hash set gives O(1) existence checks without requiring sorted order. The naive approach of starting a while loop from every number is O(n squared) because overlapping sequences cause redundant counting. The key is a guard condition that skips numbers that are not the beginning of a sequence, so that each while loop only fires for sequence starts.
Sequence Start Detection
Put all numbers in a set for O(1) lookup. For each number, only start counting a sequence if num - 1 is not in the set, meaning this number is the beginning of a sequence. Then count upward.
num_set = set(nums): A set, not a map, because no associated data is needed. The only operation is "is num + 1 in the set?" which is a pure existence check. Using a set instead of a map communicates intent more clearly and is marginally more memory efficient since it does not store values.
if num - 1 not in num_set: This single line is what makes the algorithm O(n) instead of O(n squared). It ensures that the while loop only runs for numbers that are the start of a sequence. If num minus 1 exists in the set, then num is somewhere in the middle or end of a sequence that will be counted when its starting element is processed. Without this: every number triggers its own while loop, and the total work becomes 1 + 2 + ... + n = O(n squared).
while num + length in num_set: Each number in the entire array is visited by exactly one while loop: the one that starts from its sequence's beginning. A number in the middle of a sequence is never the start of a while loop (because its predecessor exists in the set), and it is counted once by the while loop that started from the sequence head. This one to one correspondence is why the total work is O(n).
best = max(best, length): Track the global maximum across all sequences found. Since each sequence is counted exactly once from its start, this comparison fires once per sequence, not once per element.
Why It's O(n)
The while loop only runs for sequence starts. Each number belongs to exactly one sequence and is counted exactly once by the while loop. The outer for loop skips non-starts in O(1). Total work: O(n).
Sorting the array and scanning for consecutive runs gives a correct solution in O(n log n). For many interviews, this is acceptable. But the problem explicitly asks for O(n), and comparison-based sorting cannot achieve that.
The subtler mistake is using a hash set but starting a while loop from every number. You put all numbers in a set, then for each number, expand upward. This produces correct results, but without the sequence start guard, every number triggers its own while loop. Overlapping sequences cause the same numbers to be visited multiple times, and the total work becomes O(n squared).
The sequence start check (num minus 1 not in the set) guarantees that each number is visited by the while loop exactly once, because only the first element of each sequence triggers the loop. It is the mechanism that makes the algorithm linear, not just an optimization.
Two-Pass vs One-Pass
One-Pass Complement Lookup
One-pass works because finding both elements isn't necessary. When processing the second element of a valid pair, the first element is already in the map.
Processing left to right: when reaching element b, element a (if it exists) was already seen and stored. The lookup succeeds, and the pair is found.
For any valid pair, one element comes before the other. When processing the second, the first is already available. Looking into the "future" is never required.
Problems Requiring Two Passes
One-pass breaks when information about unprocessed elements is required.
Example: "Find two elements with the smallest absolute difference."
When processing element a, whether the closest element comes before or after is unknown. The optimal match might be at the end of the array.
If the answer could depend on any other element (not just ones forming a specific relationship like sum = target), two passes (or sorting) is likely required.
When Two-Pass is Required
Two-pass is required when the answer depends on information you can only know after seeing the entire input. First Unique Character illustrates this directly: when you see 'a' at index 0, you have no idea if 'a' appears again later.
Hash Maps Inside Other Patterns
Hash maps provide the O(1) state lookup that makes other patterns efficient. Sliding window uses them to track window contents. DFS/BFS uses them to store visited metadata. DP uses them for memoization. In each case, the hash map turns what would be O(n) state queries into O(1) operations.
Hash Map + Sliding Window
Sliding window maintains a "current window" that expands and contracts. The question is: how do you track what's in the window efficiently?
For "longest substring with k distinct characters," the window slides through the string. At each position, the algorithm needs to know: how many distinct characters are currently in the window? Without a hash map, this requires scanning the entire window, which is O(n) per step and O(n²) total. With a frequency map tracking character counts, checking distinct count is O(1).
The hash map tracks window state. When a character enters, increment its count. When it leaves, decrement. When count hits zero, remove from the map. The map's size is the distinct count, always O(1) to check.
Hash Map + DFS/BFS
Basic graph traversal uses a "visited" set. But many problems need more than just "have I been here?" Clone Graph needs to map original nodes to their copies. Word Ladder needs to track distance from start. Course Schedule needs to track processing state (unvisited, in-progress, done).
When the visited check needs to return more than true/false, upgrade from a set to a map. The key is the node (or state), the value is whatever metadata the algorithm needs.
Notice the critical line: cloned[n] = copy happens before recursing. This handles cycles. If the recursion returns to this node, the clone already exists and gets returned instead of creating duplicates.
Hash Map + Dynamic Programming
Memoization is a hash map pattern at its core. The recursive function's arguments define a state. The hash map caches results for states already computed, preventing redundant work.
Without memoization, recursive solutions re-solve overlapping subproblems exponentially. The hash map collapses exponential time to polynomial by ensuring each state is computed at most once.
Memoization follows three steps: check cache, compute if missing, store before returning. Python's @lru_cache decorator automates this, but understanding the underlying hash map mechanism is valuable for interviews.
Choosing the Right Key
A good key satisfies two requirements: it produces the same result for items that belong together, and different results for items that don't. Violating the first splits groups incorrectly. Violating the second merges unrelated items.
Consider a key based only on string length: "eat" and "bat" both have length 3, so they'd be grouped together incorrectly. The key is too broad. A key based on the first character: "eat" and "ate" would be split despite being anagrams. The key is too narrow. The right key captures exactly the property that defines equivalence.
Anagrams: Sorted Canonical Form
Two strings are anagrams if they contain the same characters. Sorting removes arbitrary ordering: "eat" and "tea" both become "aet". Key: tuple(sorted(s)). Alternative: character count tuple for O(n) instead of O(n log n).
Isomorphic Strings: Position Pattern
"egg" and "add" are isomorphic (e maps to a, g maps to d). The equivalence property is the pattern of first occurrences. "egg" has pattern (0, 1, 1): first char is new (0), second is new (1), third matches second (1). "add" has the same pattern (0, 1, 1).
Shifted Strings: Difference Pattern
"abc" and "bcd" are shifted (each character +1). The equivalence property is the differences between consecutive characters. "abc" has differences (1, 1). "bcd" also has differences (1, 1). "acf" has differences (2, 3), a different group.
Hash Map Recognition Checklist
This checklist summarizes the five hash map problem shapes. Use it after you have seen the patterns in action above. Three diagnostic questions identify whether a problem needs a hash map and which template to use:
- What am I repeatedly searching for? This identifies the key.
- What information do I need when I find a match? This determines the value.
- Is the search happening once per element (single pass) or over subarrays (prefix sum)? This picks the template.
1. Complement Lookup
Can you compute what the matching element must be?
Signal phrases: "find two numbers that sum to," "pair with difference k," "find the matching element."
For each element, you can compute what its partner must be. Instead of searching all other elements for that partner (O(n) per element), store elements as you go and check in O(1). Two Sum is the canonical example, but 4Sum II, pair-with-difference, and continuous subarray sum all use the same structure.
2. Frequency Counting
Does the answer depend on how many times something appears?
Signal phrases: "most frequent," "appears more than k times," "valid anagram," "majority element."
Count everything once in O(n), then answer questions about those counts in O(1). The map stores element to count. Problems like Majority Element, Top K Frequent, and Valid Anagram all follow the same two-phase structure: build the frequency map, then query it.
3. Grouping by Key
Do equivalent items share a computable property?
Signal phrases: "group all X that share property Y," "anagrams," "equivalent strings."
Compute a canonical key from each item that's identical for equivalent items. The map stores key to list of items. The entire challenge is designing the right key: it must be the same for items that belong together and different for items that don't.
4. Seen Before / Deduplication
Does the answer depend on whether something appeared earlier?
Signal phrases: "contains duplicate," "first repeating element," "within distance k."
The answer depends on whether something appeared earlier. Use a set when you only need existence ("have I seen this?"). Upgrade to a map when you need associated data like the index or count of the previous occurrence.
5. Prefix Sum + Hash Map
Are you looking for a contiguous subarray with a target sum?
Signal phrases: "subarray with sum k," "count subarrays," "contiguous subarray divisible by."
If prefix[j] - prefix[i] = k, then the subarray between i and j sums to k. This is a complement lookup on prefix sums. The map stores prefix_sum to count of times that sum has been seen.
The key is what gets looked up. The value is what gets returned when the key is found. The most common mistake is storing the wrong value type.
| Value Type | When to Use | Example |
|---|---|---|
| index (first) | Need earliest occurrence | First Unique Character |
| index (last) | Need most recent occurrence | Contains Nearby Duplicate |
| count | Need frequency | Majority Element, Valid Anagram |
| list of indices | Need all occurrences | (rare) |
| node reference | Need O(1) access to linked structure | LRU Cache, Clone Graph |
| running total | Need aggregate computation | Prefix sum count |
Before writing code: "When a match is found, what question needs answering?" That answer is the value.
| If you see... | Think... | Key | Value | Template |
|---|---|---|---|---|
| "Find pair that sums to target" | Complement lookup | element value | index | Complement Lookup |
| "Most frequent / count of X" | Frequency counting | element | count | Frequency Counter |
| "Group items by shared property" | Canonical key design | canonical form | list of items | Grouping by Key |
| "Have I seen this before?" | Set or map for existence | element | index or boolean | Seen Before |
| "Subarray with sum / divisible by" | Prefix sum + complement | prefix sum | count or first index | Prefix Sum + Hash Map |
Common Pitfalls
Bug 1: KeyError on Missing Keys
The trap: Accessing a key that doesn't exist throws KeyError. The first time any value is seen, it's not in the dict yet.
Fix: Use .get() with a default, or defaultdict:
Rule: Never assume a key exists. Always use .get(key, default) or defaultdict.
Bug 2: Modifying Dict While Iterating
The trap: Python dicts cannot change size while being iterated. Deleting or adding keys during a loop raises RuntimeError.
Fix: Collect keys first, then delete:
Bug 3: Store Before Check in Two Sum
The trap: Storing before checking means the current element is already in the map. If target = 6 and num = 3, the complement is also 3. You'll match the element with itself, returning [i, i].
Fix: Check first, then store:
Rule: In lookup problems, always check for the complement before adding the current element.
Bug 4: Missing Base Case in Prefix Sum
The trap: When total == k, the complement is total - k = 0. Without {0: 1} in the map, subarrays starting at index 0 are missed.
On [1, 2, 3] with k = 3, this misses [1, 2] (sum 3 starting at index 0) and [3] (element 3 alone).
Fix: Initialize with the base case:
Rule: Prefix sum problems need {0: 1} to count subarrays that start at index 0.
Bug 5: Not Deleting Zero-Count Keys
The trap: len(freq) counts all keys, including those with count 0. Characters that left the window still appear as keys, so distinct count is wrong.
Fix: Delete keys when their count reaches 0:
Rule: When using dict size to track distinct elements, delete keys at count 0.
Complexity Analysis
| Operation | Average | Worst | When Worst Happens |
|---|---|---|---|
| Insert | O(1) | O(n) | All keys hash to same bucket |
| Lookup | O(1) | O(n) | Many collisions |
| Delete | O(1) | O(n) | Many collisions |
| Space | O(n) | O(n) | Always linear in stored elements |
O(1) amortized. Worst case is O(n) if all keys collide, but Python's dict uses a well-optimized hash table that avoids this in practice.
Practice Problems
Hash map problems cluster into lookup, frequency counting, grouping, and prefix sum patterns. The skill is recognizing which pattern applies and what to use as the key.
Foundational
| Problem | Difficulty | Approach |
|---|---|---|
| Two Sum | Easy | Complement lookup: for each element, compute target minus num and check the map. Check before storing to prevent self-matching. The map stores value to index because the problem asks for positions, not just existence. O(n) time, O(n) space. |
| Valid Anagram | Easy | Count character frequencies for the first string, then decrement for the second. If all counts reach zero, they are anagrams. You can also sort both strings and compare, but that costs O(n log n) instead of O(n). Strings of different length are never anagrams, so check that first. |
| Contains Duplicate | Easy | Add each element to a set as you iterate. If the element is already present, return true immediately. A set gives O(1) lookup, making this O(n) time with O(n) space. You can also sort and check adjacent elements for O(n log n) time with O(1) space. |
| First Unique Character | Easy | Two passes. First pass counts character frequencies, second pass finds the first character with count 1. You need two passes because you cannot know a character is unique until you have scanned the entire string. O(n) time, O(1) space since the alphabet is fixed at 26 letters. |
Frequency Counting
| Problem | Difficulty | Approach |
|---|---|---|
| Majority Element | Easy | A hash map counting frequencies works in O(n) time and O(n) space. Boyer-Moore voting gets O(1) space by maintaining a candidate and a count. Increment for matches, decrement for mismatches. When count hits zero, switch to the current element as the new candidate. The majority element always survives because it appears more than n/2 times, so it can never be fully canceled. |
| Top K Frequent Elements | Medium | Count frequencies with a hash map, then extract the top k. Three approaches: sort by frequency for O(n log n), use a min-heap of size k for O(n log k), or bucket sort by frequency for O(n). Bucket sort works here because the maximum possible frequency is n. Create n+1 buckets indexed by count and collect elements starting from the highest bucket downward. |
| Sort Characters By Frequency | Medium | Count character frequencies, then rebuild the string with characters ordered by count from highest to lowest. The bucket sort approach groups characters by their frequency and iterates from the top bucket down, giving O(n) time. Any ordering among characters with equal frequency is valid, so ties do not matter. |
Grouping
| Problem | Difficulty | Approach |
|---|---|---|
| Group Anagrams | Medium | The key must produce the same value for all anagrams and different values for non-anagrams. Sorted characters work: tuple(sorted(s)) maps all anagrams to an identical tuple. A character count tuple is O(n) per string instead of O(n log n) for sorting. Use defaultdict(list) to collect groups. |
| Isomorphic Strings | Easy | Two strings are isomorphic if there is a consistent bidirectional mapping between their characters. Track two maps: one from s chars to t chars, one from t chars to s chars. If a mapping conflict appears in either direction, return false. You can also encode both strings as position-of-first-occurrence patterns and compare directly. "egg" and "add" both produce (0, 1, 1). |
Prefix Sum + Hash Map
| Problem | Difficulty | Approach |
|---|---|---|
| Subarray Sum Equals K | Medium | Prefix sum complement lookup. Store prefix sum counts (not just existence) because multiple earlier positions can produce the same prefix sum, and each one defines a different valid subarray. Initialize with {0: 1} so subarrays starting at index 0 are counted. Check then store ordering prevents a position from pairing with itself. |
| Continuous Subarray Sum | Medium | Subarray sum divisible by k means two prefix sums share the same remainder mod k. Store each remainder's first index (not count) because you need the earliest occurrence to maximize subarray length. The subarray must have length at least 2, so check that current index minus stored index is greater than 1. Initialize with {0: -1}. |
| Contiguous Array | Medium | Treat 0 as -1. Equal counts of 0s and 1s means the transformed subarray sums to zero. Store each running sum's first occurrence index. When the same sum appears again, the subarray between those positions has equal 0s and 1s. Track the maximum length across all repeated sums. Initialize with {0: -1} so subarrays starting at index 0 are caught. |
Advanced
| Problem | Difficulty | Approach |
|---|---|---|
| LRU Cache | Medium | Hash map stores key to node pointer for O(1) lookup. Doubly linked list maintains recency order for O(1) reordering and eviction. Sentinel head and tail nodes eliminate edge cases so every real node always has valid prev and next pointers. When evicting, remove from both structures. The node stores its own key so the hash map entry can be deleted during eviction. |
| Longest Consecutive Sequence | Medium | Put all numbers in a set. Only start counting from sequence beginnings where num minus 1 is not in the set. This guard makes the algorithm O(n) despite the nested while loop, because each number is visited by exactly one while loop across the entire outer iteration. |
| 4Sum II | Medium | Split four arrays into two groups. Compute all A[i]+B[j] sums and store their counts in a map. For each C[k]+D[l] pair, look up the negation in the map. This turns O(n^4) brute force into O(n^2) time and O(n^2) space. The map stores sum to count because multiple (i,j) pairs can produce the same sum. |
Reference Templates
Use when you can compute what the matching element must be.
Use when the answer depends on how many times elements appear.
Use when equivalent items share a computable canonical form.
Use when counting subarrays with a target sum, especially with negative values.
Use when a sliding window needs to track distinct elements or character frequencies.
Pattern Recap
Replacing the inner loop
Complement lookup stores seen values so each element's partner can be found in O(1) instead of scanning the rest of the array. One pass works because for any valid pair, whichever element you reach second will find the first already stored.
Check-then-store ordering prevents an element from matching itself when the complement equals the element's own value.
Counting and querying
Frequency counting builds a complete count map before answering questions about the distribution. Two phases are necessary because frequency questions cannot be answered until all data has been seen.
One-pass counting works only when the query does not depend on unprocessed elements. First Unique Character requires two passes because uniqueness depends on the full count.
Grouping by equivalence
A canonical key maps equivalent items to the same bucket. The key must capture exactly the equivalence property and nothing more.
A key that is too broad merges unrelated items (string length for anagrams). A key that is too narrow splits equivalent items (first character for anagrams).
Prefix sum complement lookup
Subarray sum becomes subtraction of two prefix sums. The hash map finds matching earlier prefix sums in O(1), turning subarray sum problems into the same complement structure as Two Sum.
The {0: 1} base case is required for subarrays starting at index 0. Omitting it is the most common prefix sum bug.
Tracking window state
A frequency map summarizes the current window. Increment on entry, decrement on exit, delete at zero to keep the map's size equal to the true distinct element count.
Forgetting to delete zero-count keys corrupts the distinct element count and breaks validity checks that depend on len(freq).
If the problem does not fit one of these five forms, the hash map is likely serving as auxiliary state inside another pattern (sliding window, DFS/BFS, dynamic programming) rather than being the primary technique.
Rebuilding the Pattern
When a hash map problem feels unclear, start by identifying the repeated search. The brute force almost always has an inner loop or a nested scan that checks the same kind of question on every iteration. That repeated question is the hash map target: store the answers so the question costs O(1) instead of O(n).
The next decision is what to store as the key and what to store as the value. The key is what gets looked up. The value is what gets returned when the lookup succeeds. If the problem asks for indices, store indices. If it asks for counts, store counts. If it only asks whether something exists, a set may be sufficient and communicates that intent more clearly than a map.
If the problem involves subarray sums, the repeated search is over prefix sums, not raw array values. The complement is current_sum minus k. The {0: 1} base case accounts for subarrays that start at index 0. If the problem says "count subarrays," the map must store how many times each prefix sum has appeared, not just whether it has appeared.
The pattern is recoverable from three decisions: what repeated search to eliminate, what to store as key and value, and whether the lookup is over individual elements or prefix sums. Once those decisions are clear, the code follows the same check-then-store structure regardless of which specific problem you are solving.
Check Your Understanding
Use these questions to check whether you can reason through the pattern without looking at the template.
Take Assessment
12 questions covering all hash map patterns.
Practice this pattern
Apply the guide to complete interview problems with explanations and code.
Learn Hash Maps in a guided sequence
The Interview Course connects this pattern to its prerequisites, worked lessons, and progressively harder problems.