DSA warm-up: dict & set idioms

A surprising share of interview problems — and of slow code in real projects — comes down to one move: replace a scan with a lookup. Python makes it almost invisible, because x in thing is the same three characters whether thing is a list or a set, while one of them is a full scan and the other is a hash. That one-character change is the whole warm-up, and it is worth seeing the cost counted.

set membershipdict lookup complementary searchO(n²) → O(n)

The same three characters, two different algorithms

Below, m membership tests are run against a container of n items — half of the queries are present, half are not. Both versions are executed and every element comparison is counted, including what it costs to build the set in the first place:

`x in list` versus `x in set`

items in the container n — the haystack

lookups performed m — how many times you ask

Two details make this sharper than the usual "sets are faster" advice. First, look at where the crossover actually is. Building the set costs a full pass, so for exactly one lookup the list wins — by about 1.8× at n = 100,000. Break-even arrives at roughly the second lookup, and after that the gap grows without limit, because the list repeats the whole scan every time and the set does not. Second, the misses are what hurt — a hit stops early, on average halfway, while a miss on a list must compare against all n before it can say no. Code that mostly finds nothing is where this bites hardest, and code that mostly finds nothing is what a filter is.

seen = set(previous_ids)            # one pass, once
new = [r for r in rows if r.id not in seen]

# the same idea with a value attached: dict instead of set
by_id = {r.id: r for r in rows}     # one pass, once
row = by_id.get(wanted)             # .get returns None instead of raising

Two-sum, and the shape it teaches

The canonical version of the same move. Given a list of numbers and a target, find two that add to it. The obvious solution tries every pair; the idiomatic one walks the list once, asking a dict "have I already seen the number that would complete this one?" Both are run below and every operation is counted:

Every pair, or one pass with a dict?

list length n

where the answer is

The "no answer" case is the one to remember, because it is the honest comparison: with a solution present the brute force can get lucky and stop early, but when there is nothing to find it must examine every pair, every time. That is the difference between an algorithm that is usually fine and one that is fine.

def two_sum(nums, target):
    seen = {}                       # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:      # have I already passed the complement?
            return seen[target - x], i
        seen[x] = i
    return None

Three variations of the same trick worth recognising, because most dict/set problems are one of them:

Complement search — two-sum above. You are looking for a partner, so remember what you have seen and ask for the partner directly instead of searching for it.
Grouping — defaultdict(list) keyed by whatever makes two things "the same". Anagrams group by "".join(sorted(word)); duplicate files group by content hash. The key is the definition of sameness, which is the actual design decision.
Frequency — Counter, then a comparison of counters. "Is this a permutation of that?" is Counter(a) == Counter(b), which reads as the question rather than as an algorithm.

And the cost of admission: dict and set keys must be hashable, which means immutable. A list cannot be a key; a tuple can. That is the same rule as the frozen dataclass in dataclasses, and the reason is identical — an object whose hash could change after it went into a bucket is an object you can never find again.

⚠️ Traps & honesty: the counts are element comparisons and hash operations from running both versions here — a real CPython dict lookup is one hash plus a probe, which this models as a constant of 1, and constants matter at small n · sets and dicts trade memory for speed: a set of n items is substantially larger than a list of the same items, which matters when n is large and lookups are few · hash collisions degrade lookups toward O(n) in the worst case, which is a real attack surface for web input, not just a theoretical footnote · membership on a sorted list can use bisect for O(log n) without the memory cost · none of this matters for n in the dozens, and reaching for a set there is about clarity, not speed.

Takeaways: x in list is a scan, x in set is a hash — the same three characters and a completely different cost, with break-even at about the second lookup · misses are the expensive case for a list, and filtering is mostly misses · two-sum's dict version replaces "search for a partner" with "remember what I have seen and ask for the partner", turning O(n²) into O(n) · most dict/set problems are complement search, grouping by a key that defines sameness, or frequency comparison · keys must be hashable, therefore immutable — tuple yes, list no. Next: the Phase 0 boss challenge puts these together.