1Understand
The idea
A dict or set answers "have I seen this?" in O(1) on average, which is what turns most O(n²) brute forces into O(n). Use d.get(k, default) instead of checking first, iterate with .items(), and remember that only immutable values (numbers, strings, tuples) can be keys.
Intuition
A dict answers "what do I know about this key?" in expected O(1). A set answers "have I seen this?" the same way. That single upgrade turns many nested-loop scans into one pass.
Use d.get(k, default) or if k in d instead of bare d[k] when the key might be missing. Iterate with .items() when you need both key and value. Keys must be immutable: numbers, strings, tuples of immutables, never a list.
Sets also give cheap union, intersection and difference when comparing collections.
What you will be able to do
- Read and update dictionaries safely
- Use sets for O(1) membership
- Know which values are hashable
2See it
Walkthrough
Seen set / dict in one pass
nums = [3, 1, 3], ask "have I seen this?" in O(1) average.
1 / 4
seen
- ∅ empty
Empty set. At index 0, value 3 is new.
Average O(1) lookup/insert; worst-case hashing is rare in interviews. Space is O(u) for u distinct keys. Prefer a set when you only need membership; use a dict when you must store an index, count or partner value.
Read the walkthrough as text
First duplicate. Given nums = [2, 5, 1, 2, 3], return the first value that repeats when scanned left to right.
- Start with an empty set
seen. - At
2: not inseen→ add it. - At
5, then1: same. - At the second
2: already inseen→ return2.
In code:
seen = set()for x in nums:if x in seen:return xseen.add(x)
Using a list for seen would make every in scan O(n) and the whole algorithm O(n²).
3Recognise it
Kinds of problems (5)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Lookup with get and in
Example. Increment a counter or read an optional key.
How. d.get(k, default) avoids KeyError; `k in d` tests membership before d[k].
Counting by hand
Example. Frequency of each character in a string.
How. count[ch] = count.get(ch, 0) + 1 in one pass over the input.
Iterating items
Example. Print or aggregate every key-value pair.
How. for k, v in d.items(), not range(len(d)); keys() and values() when you only need one side.
Set membership and deduplication
Example. Have we seen this value before?
How. Put items in a set; `x in seen` is average O(1) vs scanning a list.
Union, intersection and difference
Example. Users in both cohorts, or in A but not B.
How. a | b, a & b, a - b (and |=, &=) express Venn operations in one line.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
KeyError on missing keys
Why it happens. d[key] is the fast path when you expect every key to exist.
How it fails. count[x] += 1 on first sighting raises KeyError before the increment runs.
Fix. count[x] = count.get(x, 0) + 1, or check `x in count` before updating.
Membership tests on lists instead of sets
Why it happens. A list can hold the same values as a set with simpler syntax.
How it fails. seen = []; for each step `if x in seen` scans the whole list, O(n²) on large inputs.
Fix. Use a set for membership, or a dict when you need an associated value (index, count).
Using a list as a key or set element
Why it happens. Anything collectable feels valid as a set element or dict key.
How it fails. set([1, 2]) or {(1, 2): "ok"} vs using [1, 2] as a key → TypeError: unhashable type.
Fix. Keys and set elements must be immutable, use tuple(lst) or a canonical string key.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.