level 1 · Foundations
Sets
A hash map that threw away the values — and answers 'seen this before?' instantly.
what is it
Start here
A set is a hash map that kept the keys and threw the values away. That is genuinely the whole definition.
What you get for that is the answer to the single most-asked question in programming: **have I seen this before?** — in one step, instead of a scan.
Watch what it does to a classic. 'Does this list contain a duplicate?' The obvious answer compares every pair: O(n²). With a set, you walk the list once, asking 'seen it?' at each step — and each of those questions is O(1). The whole thing collapses to O(n). Same problem, and an entire complexity class cheaper.
What a set will *not* do for you is just as important. It has no order — don't ask it what came first. It stores nothing alongside a key — if you need to remember a value too, you wanted a hash map. And it costs memory: you're trading space for speed, which is the oldest trade in the book.
real-life analogy
Picture it
The bouncer doesn't scan a list of everyone who's already inside. They glance at your hand: stamp, or no stamp. One look, no searching, however many thousands of people are in there. The stamp is a set membership test.
interactive visualization
Watch it run
Walk the list once, asking 'seen it?' each time. The 22 comes back.
key % 5 → bucket
- 0
- empty
- 1
- empty
- 2
- empty
- 3
- empty
- 4
- empty
A set holds each value at most once, and answers 'have I seen this?' instantly. It's a hash map that kept the keys and threw the values away.
step 01/13
- checking
- collision · chained
- placed · found
space · play ← → · step
| 1 | // A Set is a hash map that threw away the values |
| 2 | // and kept only the keys. |
| 3 | const seen = new Set(); |
| 4 | |
| 5 | function hasDuplicate(a) { |
| 6 | for (const v of a) { |
| 7 | if (seen.has(v)) return true; // O(1) — one hash, one look |
| 8 | seen.add(v); // O(1) |
| 9 | } |
| 10 | return false; |
| 11 | } |
| 12 | |
| 13 | // The nested-loop version is O(n²). This is O(n). |
variables right now
Nothing in play yet — press play.
the dry run · every step, in words
13 stepscomplexity
What it costs
- best case
- O(1)
- average
- O(1)
- worst case
- O(n)
- extra memory
- O(n)
add, has and delete are all O(1) on average — one hash, one jump. The worst case is O(n) if every key collides into one bucket, exactly as with a hash map. You are paying O(n) memory to turn an O(n²) scan into an O(n) one.
- O(1) · this one
- O(log n)
- O(n)
- O(n log n)
- O(n²)
common mistakes
Common traps
Expecting a set to remember insertion order.
It scatters keys by hash, not by when they arrived. If order matters, you need a list alongside it — or an ordered/linked set.
Using a set when you need to store a value with the key.
That's a hash map. A set only records that a key exists. 'Have I seen it?' — set. 'What was it worth?' — map.
Putting mutable objects in a set and then changing them.
The hash was computed when it went in. Change the object and its hash changes — so the set can no longer find it, even though it's sitting right there.
quiz
Check yourself
Three questions. Get them all right to finish the lesson.
+55 XP01What is a set, really?
02How does a set turn 'does this list have a duplicate?' from O(n²) into O(n)?
03What does a set NOT give you?
practice
Solve it on LeetCode
You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.