Contains duplicate
StopTrace
- CH1 i
9/9
A set answers one question: has this number come up before?
Step through it →Hashing & Frequency Maps
A hash map remembers what you've already read, so asking for a value, a partner or a group takes one lookup instead of a scan.
Two Sum: find the two numbers that add up to the target
StopTrace
numstarget
seen starts empty: no number has been read yet.
Typical cost O(n) time, O(n) space (amortized O(1) per op)Full lesson: Two Sum →
When to reach for it
- You keep asking whether you've seen something before.
- Each item needs a partner: the number that completes a sum, the letter that cancels a count.
- Items belong together when they share a key, like their letter counts.
- The brute force is a nested loop that rescans what it already read.
What stays true
Each number is stored only after its own lookup, so seen never holds the current number or anything after it. A repeat overwrites its index, so a match pairs with the latest copy.
The map holds exactly what's been read
StopTrace
Invariantseen maps every number before i to its latest index, and nothing else.✓ Holds
seen starts empty: no number has been read yet.
Break it
Each input here has tripped up a version of this code. The stage runs the one that gets it right.
Storing 3 before its lookup finds it at once and answers [0, 0]. Looking up first finds 2 + 4.
Two Sum on the inputs that trip it up
StopTrace
seen starts empty: no number has been read yet.
Answer[1, 2]Steps10
Variants
Valid anagram
StopTrace
15/15
Count up for one string and down for the other. Anagrams end at all zeros.
Step through it →Group anagrams
StopTrace
14/14
Key each word by its letter counts, and the groups form on their own.
Step through it →Longest consecutive sequence
StopTrace
20/20
Walk a run only from its first number, the one whose left neighbor is missing.
Step through it →The code
The same algorithm in plain Python. The lit line is the one the current frame came from.
Two Sum: find the two numbers that add up to the target
StopTrace
seen starts empty: no number has been read yet.
two_sum.py
def two_sum(nums, target): seen = {} for i, num in enumerate(nums): complement = target - num if complement in seen: return [seen[complement], i] seen[num] = i return []Drill it
Two SumRuns live,EasyContains DuplicateRuns live,EasyValid AnagramRuns live,EasyGroup AnagramsRuns live,MediumTop K Frequent ElementsRuns live,MediumLongest Consecutive SequenceRuns live,MediumLongest Substring Without Repeating CharactersRuns live,MediumSubarray Sum Equals KRuns live,MediumLRU CacheMedium