Hash Maps: O(1) Lookup
Why sets and dicts turn O(n²) searches into a single O(n) pass.
12 min, 0 of 3 activities solved
View cheatsheetGetting Python ready… examples can run in a moment.
A huge share of interview problems hide the same question: "have I seen this before?"
With a list, answering it means scanning every
element: x in my_list is O(n). Ask it once per
element and you're at O(n²).
A set or dict answers it in O(1) on average.
Python runs the key through hash(), which turns it
into a number, and uses that number to jump straight
to a slot (a "bucket") in an internal table.
To check x in s, Python hashes x again, lands
on the same slot and compares one item. No scanning.
Step through it below with small ints, which
conveniently hash to themselves (string hashes
change every time Python starts).
A set's slots: s = {13, 6, 20}
A new small set has a table of 8 slots. Where a value goes is decided by its hash, not by when it was added.
When two values want the same slot (a collision), Python tries another slot. Collisions are rare, which is why lookups are O(1) on average.
List vs set membership
Same 500 lookups, same answer. The list walks up to
20,000 items per lookup; the set jumps straight to
the slot. Double n and watch only the list time
grow.
Brute force vs the pattern. "Does this list contain a duplicate?" The brute force compares every pair: O(n²) time, O(1) space. The hashing version walks once and remembers what it has seen: O(n) time, O(n) space.
That's the core trade of this whole unit: spend memory to save time. Interviewers expect you to name it out loud.
Pairs vs a seen set
Both find the duplicate, but the pair version does about half a million comparisons, the set version 1,001. Notice the order inside the loop: check first, then add.
What can be a key? Only hashable values: ints, floats, strings, tuples (of hashables) and frozensets. Lists, dicts and sets are mutable, so their hash could change after you store them, and Python refuses:
Unhashable keys
The fix is almost always tuple(my_list). You'll
use tuple keys constantly in this unit: grid cells,
letter counts, slopes.
What does this print?
Which of these can NOT be used as a set element or dict key?
First repeat
Write first_repeat(nums) that returns the first
value whose second appearance comes earliest
while scanning left to right, or None if every
value is unique.
first_repeat([3, 1, 4, 1, 5, 3]) is 1: the
second 1 (index 3) shows up before the second
3 (index 5).
Do it in one pass with a set.