Hashing patterns
Most "do it in one pass" interview questions have the same answer: remember what you've seen in a dictionary or a set, keyed by something you can look up in one step.
- Seen set: first repeat, duplicates, "have we met this id before?".
- Complement lookup: for two values that add up to a target, store each value's position, and for each new value look up
target - value.
- Grouping key: put items that belong together under the same key, like anagrams under their sorted letters.
- Counts: a
Counter answers "first item that appears once" in two passes.
- Set of all values: lets you start a run only at its first value (
x - 1 not in the set), so the longest run of consecutive numbers takes O(n).
The skill is choosing the key. Ask: what do I need to find instantly when the next item arrives?
def two_sum(nums, target):
pos = {}
for i, n in enumerate(nums):
if target - n in pos:
return (pos[target - n], i)
pos[n] = i
two_sum([12, 7, 3, 9], 16)
Out: (1, 3). When 9 arrives, its partner 7 is already in the dictionary.