Hash maps & sets — your O(1) superpower

Here's the most common Big-O upgrade in real Python code. Once you can spot it, you'll find it everywhere.

The smell:

for x in items:
    if x in cache:   # cache is a list
        ...

That 'in cache' looks innocent. It's hiding an O(n) scan. The whole loop is O(n*m) where m is the size of cache.

The fix is one line — make cache a set. 'x in set' is O(1) average. The whole loop drops to O(n+m).

For n = m = 10000, that's 10^8 operations versus 2*10^4. Four orders of magnitude. From 'unusable' to 'instant'.

The same principle applies to dict-based lookups. 'd[k]' and 'k in d' are O(1) average. If you find yourself searching a list for a matching key inside a loop, you almost always want a dict instead, mapping that key to whatever value you needed.

Why 'average' matters. Hash tables CAN degrade to O(n) when the hash function is bad and many keys collide. Python's dict and set use well-engineered hash functions for built-in types — strings, ints, tuples — so collisions are rare in practice. For your own classes (overriding __hash__), the burden is on you to write a good hash function. Tuple-of-fields is usually safe.

The broader pattern — trade memory for hash lookups. Sets and dicts cost O(n) memory; they save O(n) time per lookup. If your alternative is repeated linear searches, the trade is almost always worth it.

Watch for the smell. 'in list' inside a loop. 'list.index' inside a loop. 'manually search a list of dicts'. All variants of the same anti-pattern. All have a one-line fix.

Learn to see the pattern. Half of the optimisations you'll ever make in Python are this one move applied repeatedly.

Every data-handling project I've ever worked on has 'group these items by some key' as a frequent operation. The Python stdlib has the perfect tool for it — collections.defaultdict — and most beginners reinvent the wheel.

The naive group-by:

buckets = {}
for item in items:
    key = compute_key(item)
    if key not in buckets:
        buckets[key] = []
    buckets[key].append(item)

Four lines, two state checks, easy to typo. The defaultdict version:

from collections import defaultdict

buckets = defaultdict(list)
for item in items:
    buckets[compute_key(item)].append(item)

Two lines. The defaultdict auto-creates an empty list the first time a key is accessed. Subsequent accesses use the existing list. Net effect — the same group-by, half the code, no state-check bugs.

The variants are where it gets really useful.

defaultdict(int) is a counter. defaultdict[key] += 1 works on every key, even unseen ones. Equivalent to collections.Counter for counting purposes, slightly more flexible if you want to mix counting with other operations on the same dict.

defaultdict(set) gives unique-per-key. Useful for inverted indices — for each tag, the set of documents with that tag.

Nested defaultdicts. defaultdict(lambda: defaultdict(int)) gives you a 2D counter — a count for each (row, col) pair. Combine for matrices, co-occurrence stats, transition counts in HMMs.

When you see 'manually-built dict-of-lists' in code, reach for defaultdict(list). The migration is one line — change the dict creation. The code becomes cleaner and slightly faster.

Bonus — collections.Counter for direct counting. Counter(items) returns {item: count}. .most_common(k) gives the top k by count. Saves you from rolling your own.

The two-sum problem: given an UNSORTED array and a target, return indices of two numbers that sum to the target. (Variant of yesterday's sorted version.)

With no sorted-ness to exploit, we can't use opposite-end two-pointers. But hash maps give us an O(n) solution anyway.

The trick — as you walk the array, keep a dict mapping each value seen so far to its index. For each new element x, check if (target - x) is already in the dict. If yes, you've found the pair — the previously-seen value at some earlier index, plus the current x at the current index.

Look at the snippet. seen is the dict. We iterate with enumerate. need = target - x is the value we'd need to pair with x. If need is in seen, return (seen[need], i). Otherwise add x to seen with its index.

One pass. O(n) time. O(n) space.

Why this is the canonical 'use a hash map' interview answer — it makes the trade-off explicit. Brute force is O(n²) with O(1) space. Hash map is O(n) with O(n) space. The hash map trades memory for time, dropping a Big-O class.

The variants build on this base.

Three-sum — find triples summing to a target. Sort first, then for each i, run two-sum on the rest. O(n²).

Four-sum — find quadruples. Two nested loops over indices, two-pointer for the inner pair. O(n³).

Subarray sum equals K — different problem, similar shape. Use a prefix sum and a hash map. For each prefix sum p, check if (p - K) has been seen. If yes, the subarray between has sum K.

The pattern repeats — when the brute force has nested loops over the array, ask if a hash map can replace one of them with O(1) lookup. Usually yes.

If you've never used Python's set operators, your collection-comparison code is longer than it needs to be.

Four operators. Each one a single character. Each one an O(min(|a|, |b|))-ish operation under the hood.

a & b — intersection. Items in BOTH a and b.

a | b — union. Items in EITHER a or b.

a - b — difference. Items in a but not in b.

a ^ b — symmetric difference. Items in exactly one of the two, not both.

Replaces all of these manual loops:

common = [x for x in a if x in b]   # a & b is shorter and faster
all_items = list(set(a) | set(b))   # a | b
only_in_a = [x for x in a if x not in b]   # a - b

The operators run in C inside CPython, where the manual list comp is interpreted Python bytecode. Order-of-magnitude speed difference for any non-trivial size.

Where this comes up in real ML/data work:

Tag overlap. tags_a & tags_b gives shared tags between two items.

Feature presence. set(features_required) - set(features_in_data) gives features that are missing.

Deduplication across sources. set(source_a) | set(source_b) merges and dedupes in one step.

Label diffing. set(predictions) ^ set(ground_truth) shows where they disagree.

A small gotcha — sets are unordered. If order matters, sort the result or use a different structure. Most of the time order doesn't matter for these operations.

The operators also have method-form equivalents (a.intersection(b), a.union(b), etc) that take any iterable. Use the operators for set-set; use the methods if your right side is a list, tuple, or generator.

Learn the operators once. They show up in clean code constantly.

End of Day 19. Hash maps and sets are the structures that compound your skill the fastest. Master them and most leetcode-medium array problems become routine.

What we covered.

Morning, the canonical Big-O upgrade. 'In list' inside a loop is a smell; replace with 'in set'. Drops from O(n*m) to O(n+m). Four orders of magnitude on real-sized inputs. Spot the pattern; the fix is one line.

Midday, defaultdict for group-by patterns. Four daily uses — list (group-by), int (counter), set (unique-per-key), nested (matrices/co-occurrence). Replaces manual 'if key not in dict' boilerplate everywhere.

Afternoon, two-sum solved in O(n) with a hash map. The canonical 'trade memory for time' answer in interviews. The same pattern (running map of seen values) generalises to subarray-sum-equals-K, longest-subarray-with-property, and other one-pass problems.

Evening, Python's set operators. & | - ^. Each one a one-character replacement for a manual loop, running in C. Use them every time you're comparing collections.

A week-three midpoint check. We've covered Big-O, arrays, strings, linked lists, hash maps. The fundamental data structures and the Big-O upgrades they enable. Tomorrow we add stacks and queues; the day after, sliding window in depth.

Tomorrow, Day 20, stacks and queues. The structures behind undo/redo, function calls, BFS, async event loops, parser flows. Small concepts; outsized reach. Plus the most important Python perf gotcha — using list.pop(0) as a queue is O(n), not O(1). Use collections.deque instead.

See you in the morning.