The Seen-Set: Spotting Repeats in One Pass
A concert gate scans ticket codes as people walk in. If a code has already been scanned, someone has copied a ticket and the gate must flag it. Comparing every ticket with every other ticket would keep the queue waiting for hours. A set remembers what it has seen and answers "was this here before?" in an instant.
The rule
Before you store it, ask the set whether it has seen it.
The slow way compares every pair: for 100,000 tickets that is about five billion comparisons. The seen-set does one question and one insert per item:
def first_repeat(codes):
seen = set()
for code in codes:
if code in seen: # ask first...
return code
seen.add(code) # ...then store
return Nonefirst_repeat(["A7", "B2", "C9", "B2"]) returns "B2". The cost is one pass, n steps, plus memory for up to n codes. Memory is the price you pay for speed, and it is almost always worth it.
The same move answers many disguised questions: the first repeated letter in a word, whether two sign-ups share an email, whether a walk on a grid ever returns to a square it has visited.
If you only need yes or no, Python has a one-liner: a set drops duplicates, so the list has a repeat exactly when the set is smaller.
has_repeat = len(set(codes)) != len(codes)There is a third option when memory is tight: sort, then compare neighbours. Equal items end up side by side, so one pass over the sorted list finds them. That costs n log n time but no extra set, and it is the answer to the follow-up question "what if you cannot afford a big extra set?"
The shortcut
Whenever a problem's inner question is "have I met this before?", the answer is a set, and the loop is always the same two lines: check, then add. The order matters. Add first and every item finds itself.
A7
Is
A7in the empty set? No. Add it. Seen: {A7}.
The early return is a bonus: when a repeat sits near the front, the seen-set finishes long before the end, while sorting always has to process everything.
Drills
Answer fast — trust the rule.
What does first_repeat(["K1", "K2", "K1", "K2"]) return?
What goes wrong if you swap the two lines, so each code is added before the check?
How long does the seen-set approach take for n codes?
The interviewer says: "Now do it without building a big extra set." What is the natural move?
Which expression is True exactly when codes contains a repeat?
Remember
- Before you store it, ask the set whether it has seen it.
- Shortcut: "have I met this before?" means a set, with check-then-add.
- Trap: adding before checking, which makes every item look like a repeat.