Solving Problems with Hash Maps
A hash map — Python’s dict, or a set when you only need membership — turns “search for this” into “look this up directly,” trading a small amount of memory for average O(1) access instead of an O(n) scan. Once that instinct clicks, a huge swath of interview and real-world problems — duplicate detection, frequency counting, grouping, complement search, subarray sums — collapse from O(n^2) brute force down to a single O(n) pass. This lesson assumes you already know how hash tables work under the hood (chaining, amortized O(1) operations) from earlier hashing lessons; here the focus is recognizing the shapes of problems a hash map solves and building the reflex to reach for one.
Overview: How Hash Maps Turn Search Into Lookup
Nearly every “hash map problem” is a variation on the same idea: as you scan the input once, you remember something about what you’ve already seen in a structure that answers “have I seen X?” or “how many times have I seen X?” in O(1) average time. Without a hash map, answering that question means re-scanning everything seen so far, which turns an O(n) pass into an O(n^2) algorithm. With a hash map, the lookup is instant, so the whole algorithm stays O(n).
Picture a simpler version of a classic interview problem: given a list of numbers, find two that add up to a target. Brute force checks every pair with two nested loops — for each number, scan the rest of the list for its complement. That is O(n^2) time. A hash map flips the question around: instead of asking “does some later number equal target - num?”, you ask “have I already seen target - num?” as you walk through the list once, storing each number (and its index) in a dict as you go. The moment you meet a number whose complement is already a key in the dict, you’re done. That single change — precomputing “have I seen this” instead of searching for it — is the core hash map pattern, and it recurs in a few shapes:
- Existence / frequency: “have I seen this value before?” (duplicates) or “how many times?” (counting) — solved with a
setor a frequencydict/Counter. - Complement lookup: “does
target - currentexist among values already processed?” — the Two Sum pattern. - Grouping by a derived key: transform each item into a canonical key (like a sorted string) and bucket items that share a key — the Group Anagrams pattern, usually built with
collections.defaultdict(list). - Prefix aggregate lookup: track a running total and look up how many times a needed earlier total has occurred — the Subarray Sum pattern.
All four rely on the same guarantee: Python’s dict and set give average O(1) insertion, lookup, and deletion, because a key’s hash value maps almost directly to a storage slot instead of requiring a scan. The “average” qualifier matters — pathological hash collisions can degrade a single operation to O(n) in the worst case — but for built-in types with well-distributed keys (ints, strings, tuples of hashable values), O(1) average is the practical reality you should design around.
Time and Space Complexity
The complexity of a hash map problem usually comes from multiplying “how many items do I process” by “how much work per item,” and the whole point of using a hash map is to make the per-item work O(1) average instead of O(n).
| Operation | Average case | Worst case | Why |
|---|---|---|---|
dict/set insert or update |
O(1) | O(n) | the key’s hash maps directly to a bucket; worst case is many keys colliding into one bucket, which is rare with Python’s hashing on typical keys |
dict/set lookup (in, []) |
O(1) | O(n) | same reasoning as insert — no scan needed unless there’s a collision chain |
list membership (in) |
O(n) | O(n) | no hashing — every element is compared in turn, which is why swapping a list for a set is the single biggest lever in these problems |
| Two Sum (hash map pass) | O(n) time, O(n) space | O(n) time, O(n) space | one pass over n elements, O(1) average work per element; the map holds up to n entries |
| Group Anagrams | O(n * k log k) time, O(n * k) space | same | n words, each sorted in O(k log k) where k is word length, to build its bucket key |
| Subarray Sum Equals K | O(n) time, O(n) space | O(n) time, O(n) space | one pass computing running sums, O(1) average lookup/update of a prefix-sum count map with at most n distinct sums |
Examples
Example 1: Two Sum (Complement Lookup)
Given a list of numbers and a target, return the indices of two numbers that add up to the target. Assume exactly one solution exists. Build a dict of value → index as you scan; before adding the current number, check whether its complement is already a key.
def two_sum(nums: list[int], target: int) -> list[int]:
seen: dict[int, int] = {}
for index, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], index]
seen[num] = index
return []
def main() -> None:
nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target))
main()
Output:
[0, 1]Trace: at index 0, num is 2 and its complement (9 – 2 = 7) is not yet a key in seen, so 2 is recorded as seen[2] = 0. At index 1, num is 7 and its complement is 9 – 7 = 2, which is in seen (mapped to index 0), so the function immediately returns [0, 1] without ever looking at 11 or 15.
Example 2: Group Anagrams (Grouping by Derived Key)
Given a list of words, group the ones that are anagrams of each other. Two words are anagrams if they contain exactly the same letters in possibly different order — so sorting their letters produces an identical string. That sorted string becomes the hash map key.
from collections import defaultdict
def group_anagrams(words: list[str]) -> list[list[str]]:
groups: dict[str, list[str]] = defaultdict(list)
for word in words:
key = "".join(sorted(word))
groups[key].append(word)
return list(groups.values())
def main() -> None:
words = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams(words))
main()
Output:
[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]Trace: sorting the letters of "eat", "tea", and "ate" all produce "aet", so all three land in the same bucket under that key. "tan" and "nat" both sort to "ant" and share a bucket. "bat" sorts to "abt", a key nothing else matches, so it forms its own group. Because Python dicts preserve insertion order, the groups come out in the order their key was first seen: "aet" (from "eat"), then "ant" (from "tan"), then "abt" (from "bat").
Example 3: Subarray Sum Equals K (Prefix Sum Lookup)
Given a list of integers (which may include negatives) and a target k, count how many contiguous subarrays sum to exactly k. Checking every subarray directly is O(n^2). Instead, track the running sum as you scan, and remember, in a hash map, how many times each running sum value has occurred. A subarray ending at the current index sums to k exactly when an earlier running sum equals current running sum - k, so at every step you look up that value’s count and add it to the answer. Seed the map with {0: 1} before the loop, representing the “empty prefix,” so subarrays that start at index 0 are counted correctly.
from collections import defaultdict
def subarray_sum_equals_k(nums: list[int], k: int) -> int:
prefix_counts: dict[int, int] = defaultdict(int)
prefix_counts[0] = 1
running_sum = 0
count = 0
for num in nums:
running_sum += num
count += prefix_counts[running_sum - k]
prefix_counts[running_sum] += 1
return count
def main() -> None:
nums = [1, 2, 3, -3, 1, 1]
k = 3
print(subarray_sum_equals_k(nums, k))
main()
Output:
4Trace: with nums = [1, 2, 3, -3, 1, 1] and k = 3, the running sum after each element is 1, 3, 6, 3, 4, 5. Every time the running sum minus k matches a previously-seen running sum, that’s a subarray summing to 3: [1, 2] (running sum 3, minus k = 0, which was seeded), [1, 2, 3, -3] (running sum 3 again, minus k = 0), [2, 3, -3, 1] (running sum 4, minus k = 1, seen earlier), and [3] alone (running sum 6, minus k = 3, seen earlier). That totals 4 matching subarrays.
How It Works Step by Step
Follow the Two Sum algorithm by hand on nums = [3, 2, 4] with target = 6:
| Step | index | num | complement (target – num) | complement in seen? | action |
|---|---|---|---|---|---|
| 1 | 0 | 3 | 3 | no (seen is empty) |
store seen[3] = 0 |
| 2 | 1 | 2 | 4 | no (seen only has key 3) |
store seen[2] = 1 |
| 3 | 2 | 4 | 2 | yes — seen[2] = 1 |
return [1, 2] |
Notice the algorithm never looks back at earlier elements by scanning — every “have I seen this” question is answered by an O(1) average dict lookup. That’s exactly why a single pass suffices: the hash map does the remembering, so the loop never needs a nested loop or a second pass.
Common Mistakes
Mistake 1: Checking membership against a list instead of a set
It’s easy to reach for a plain list as your “seen” structure. The logic below is correct, but every in check re-scans the whole list, so the algorithm is secretly O(n^2) instead of O(n) — it will time out on large inputs even though it looks like a single loop.
def has_duplicate_slow(nums: list[int]) -> bool:
seen = []
for num in nums:
if num in seen:
return True
seen.append(num)
return False
The fix is purely a data-structure swap: use a set, whose in check is O(1) average instead of O(n), so the whole function drops to O(n) overall.
def has_duplicate_fast(nums: list[int]) -> bool:
seen: set[int] = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return False
Mistake 2: Inserting into the map before checking for the complement
In the Two Sum pattern, the order of “check” versus “insert” matters. If you insert the current number into seen before checking for its complement, a number can match against itself in the same iteration — wrong whenever the target is exactly double the current value.
def two_sum_bug(nums: list[int], target: int) -> list[int]:
seen: dict[int, int] = {}
for index, num in enumerate(nums):
seen[num] = index
complement = target - num
if complement in seen:
return [seen[complement], index]
return []
nums = [3, 3]
target = 6
print(two_sum_bug(nums, target))
Output:
[0, 0]With nums = [3, 3] and target = 6, the correct answer is [0, 1] (the two different 3s), but the buggy version inserts seen[3] = 0 before checking, so when it computes the complement (also 3), it finds itself and returns [0, 0]. The fix is the order shown in Example 1 above: check whether the complement is already in seen before writing the current number into the map.
Mistake 3: Forgetting to seed the prefix-sum map
In the Subarray Sum Equals K pattern, forgetting to seed prefix_counts[0] = 1 silently undercounts every subarray that starts at index 0, because there’s no recorded “empty prefix” to match against.
from collections import defaultdict
def subarray_sum_equals_k_bug(nums: list[int], k: int) -> int:
prefix_counts: dict[int, int] = defaultdict(int)
running_sum = 0
count = 0
for num in nums:
running_sum += num
count += prefix_counts[running_sum - k]
prefix_counts[running_sum] += 1
return count
nums = [1, 2]
k = 3
print(subarray_sum_equals_k_bug(nums, k))
Output:
0The subarray [1, 2] sums to exactly 3, so the correct answer is 1 — but the buggy version never seeds a count for sum 0, so when the running sum reaches 3 and looks up prefix_counts[3 - 3], it finds nothing. The fix is the seed line shown in Example 3 above: prefix_counts[0] = 1 before the loop starts.
Best Practices
- Reach for a hash map whenever a problem needs “have I seen this?” or “how many times?” answered repeatedly — it turns an O(n) linear scan into an O(1) average lookup.
- Use
collections.Counterfor frequency counting instead of hand-rolleddictincrement logic; it’s built for exactly that and reads clearly. - Use
collections.defaultdictwhen grouping or accumulating so you don’t need explicit “is this key already present” checks before appending or incrementing. - For complement-lookup problems (Two Sum and its variants), check the map for the complement before inserting the current element, unless the problem explicitly allows an element to pair with itself.
- Only hashable values can be dict keys or set members; convert lists to tuples (or use
frozenset) if you need a collection as a key. - For prefix-sum-style subarray problems, always seed the map with the identity value (
{0: 1}) so subarrays starting at index 0 aren’t undercounted. - Remember hash map operations are O(1) average, not guaranteed — this is a modeling detail worth knowing, but in practice Python’s hashing is well-distributed enough that you should default to a hash map whenever the pattern fits.
Practice Exercises
1. Contains Duplicate. Given a list of integers nums, return True if any value appears at least twice and False if every element is distinct. Hint: a single pass with a set solves this in O(n) time and O(n) space.
2. Longest Consecutive Sequence. Given an unsorted list of integers (which may contain duplicates), return the length of the longest run of consecutive integers. For example, nums = [100, 4, 200, 1, 3, 2] has the run [1, 2, 3, 4], so the expected output is 4. Hint: put every number in a set, then only start counting a run from numbers whose predecessor (num - 1) is not in the set — that keeps the whole algorithm O(n) even though there’s a loop inside a loop.
3. First Unique Character. Given a string s, return the index of the first character that does not repeat anywhere else in the string, or -1 if none exists. For example, s = "swiss" should return 1 (the 'w'). Hint: build frequency counts with collections.Counter in one pass, then scan the string a second time for the first character whose count is 1.
Summary
- Hash maps convert “search for X” into “look up X,” turning O(n) or O(n^2) scans into O(1) average lookups and O(n) overall passes.
- Four recurring patterns cover most hash map problems: existence/frequency (
set/Counter), complement lookup (Two Sum), grouping by derived key (Group Anagrams), and prefix aggregate lookup (Subarray Sum Equals K). dictandsetgive O(1) average time for insert, lookup, and delete; worst case degrades to O(n) under heavy hash collisions, which is rare with Python’s built-in hashing on typical keys.- Two Sum and Subarray Sum Equals K both run in O(n) time and O(n) space with a single pass over the input.
- Group Anagrams runs in O(n * k log k) time, where n is the number of words and k is the max word length, because each word must be sorted to build its bucket key.
- Always seed prefix-sum hash maps with the identity value (sum 0 mapped to count 1) so subarrays starting at index 0 aren’t undercounted.
- When a problem forbids matching an element with itself, check the map for a match before inserting the current element into it.
