Hashing: Maps & Sets
Trade memory for time. How hash tables turn O(n) scans into O(1) lookups, and the counting/grouping patterns they unlock.
Most brute-force solutions are slow for one reason: they search. “Have I seen this value before?” answered by scanning the array is O(n), and doing it inside a loop is where O(n²) comes from. A hash table answers that same question in O(1), and that single upgrade collapses a huge family of problems from quadratic to linear.
The trade is memory for time. You keep a side structure — a dict (map) or a set — and consult it as you go. Learning to reach for it reflexively is one of the highest-leverage habits in all of DSA.
The mental model
A hash table stores keys in an array of “buckets.” A hash function turns a key into a bucket index, so instead of looking through every slot, you compute where the key would be and go straight there. Two keys landing in the same bucket is a collision, resolved by chaining or probing — but amortized, the lookup, insert, and delete are all O(1).
Two Python types cover almost everything:
set— membership. “Have I seenx?” Order-free, duplicate-free.dict— association. Map a key to a count, an index, a list, anything.
seen = set()
seen.add(5)
3 in seen # False, O(1)
count = {}
count["a"] = count.get("a", 0) + 1 # the counting idiomhash("bee") = sum of char codes = 300 mod 5 = 0Pattern recognition
Variations you will meet
Worked problems
Try each yourself before revealing the solution. Notice how every one of them is really “replace a search with a lookup.”
Two Sum
Given an array of integers and a target, return the indices of the two numbers that add up to the target. Exactly one valid pair exists, and you may not reuse the same element.
Approach. The brute force checks every pair — O(n²). Instead, as you scan, ask: “for the current number x, have I already seen its complement target - x?” A map from value to index answers that in O(1). Check before inserting so you never pair an element with itself.
Show solution
def two_sum(nums, target):
seen = {} # value -> index
for i, x in enumerate(nums):
need = target - x
if need in seen:
return [seen[need], i]
seen[x] = i
return []Complexity. O(n) time, O(n) space — one pass, one map. This “store what you have, look up what you need” move is the single most common hashing pattern in interviews.
Group Anagrams
Given a list of words, group together the ones that are anagrams of each other (same letters, any order). Return the groups in any order.
Approach. Two words are anagrams exactly when they share a canonical form. Sorting a word’s letters produces a key that all its anagrams also produce, so bucket words into a map from that key to the list of words that match.
Show solution
from collections import defaultdict
def group_anagrams(words):
groups = defaultdict(list)
for w in words:
key = tuple(sorted(w)) # canonical form; tuple is hashable
groups[key].append(w)
return list(groups.values())Complexity. O(n · k log k) for n words of length up to k, from sorting each word. If letters are limited to lowercase, a 26-length count tuple as the key drops it to O(n · k). The lesson: turn “are these equivalent?” into “do they produce the same key?”
Longest Consecutive Sequence
Given an unsorted array, find the length of the longest run of consecutive integers (e.g. [100, 4, 200, 1, 3, 2] → 1,2,3,4 → length 4). Do it in O(n) — no sorting.
Approach. Put every number in a set for O(1) membership. A number x can only be the start of a run if x - 1 is not in the set — so only start counting from those, then walk x+1, x+2, … while they exist. Each number is visited at most twice, so the whole thing is linear despite the nested-looking loop.
Show solution
def longest_consecutive(nums):
s = set(nums)
best = 0
for x in s:
if x - 1 in s: # not a run start; skip
continue
length = 1
while x + length in s: # walk the run upward
length += 1
best = max(best, length)
return bestComplexity. O(n) time, O(n) space. The x - 1 in s guard is what keeps it linear — without it you would re-walk the same run from every element. Skipping non-starts is a pattern worth remembering.
When not to reach for it
Hashing costs memory and destroys order. If the input is already sorted, two pointers or binary search often solve the same problem in O(1) extra space — no map needed. And if you need keys kept in order (range queries, “next larger key”), a hash map cannot help; that is what balanced trees and heaps are for, which are coming up next.