Hashing for Lookup: Two Sum, Duplicates and Anagram Groups
24 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Many problems ask "have I seen this before?". Checking a list each time is slow. A set or a dictionary answers in about one step, and that turns many O(n^2) solutions into O(n).
Searching a list is slow
Hash table is a structure that turns a key into a position with a hash function, so it finds the key without scanning. Python dict and set are hash tables, and a lookup takes O(1) on average.
A checkout system must know whether an order id was already processed. A list checks ids one by one. A set finds an id in about one step, however many ids it holds.
done_list = [1001, 1002, 1003]done_set = {1001, 1002, 1003}
print(1002 in done_list)print(1002 in done_set)print(1009 in done_set)Example 1 · Filter with a blocked set
orders = [("A1", "asha"), ("A2", "ravi"), ("A3", "meena"), ("A4", "ravi")]blocked = {"ravi", "diya"}print([code for code, customer in orders if customer not in blocked])['A1', 'A3']
What this code does
- Each
intest on the set is one lookup, not a scan. - The comprehension keeps orders from customers who are not blocked.
Both give the same answer. For a list the work grows with its length, O(n). For a set it is O(1) on average.
Duplicates with a set
To find the first repeated id, remember every id you have seen. When an id is already in the set, you have your answer.
def first_duplicate(ids): seen = set() for x in ids: if x in seen: return x seen.add(x) return None
print(first_duplicate([4, 8, 15, 8, 4]))Example 2 · Duplicates, two ways
ids = [101, 102, 103, 102]print(len(set(ids)) != len(ids))
seen = set()for x in ids: if x in seen: print("first repeat:", x) break seen.add(x)True first repeat: 102
What this code does
- The first check only answers yes or no. A set drops repeats, so a shorter set means a duplicate.
- The loop also tells you which value repeats first, and stops there.
One pass: O(n) time and O(n) space. Comparing every pair costs O(n^2). For a plain yes or no, len(set(ids)) != len(ids) is enough.
Two sum with a dictionary
Find two prices that add up to a budget. Brute force tries every pair. Instead, for each price look up its partner, target - price, among the prices already seen.
def two_sum(prices, target): seen = {} for i, price in enumerate(prices): if target - price in seen: return seen[target - price], i seen[price] = i return None
print(two_sum([2, 7, 11, 15], 9))Example 3 · Two sum, brute force and hashing
prices = [3, 8, 12, 5, 9]target = 17
for i in range(len(prices)): for j in range(i + 1, len(prices)): if prices[i] + prices[j] == target: print("brute", i, j)
seen = {}for j, price in enumerate(prices): if target - price in seen: print("hash", seen[target - price], j) break seen[price] = jbrute 1 4 brute 2 3 hash 2 3
What this code does
- The nested loops check every pair, O(n^2), and report both pairs that reach 17: (1, 4) and (2, 3).
- The dictionary version stops at the first pair it completes while scanning, which is (2, 3), in O(n).
Example 4 · Why the insert comes after the lookup
def two_sum(prices, target): seen = {} for i, price in enumerate(prices): if target - price in seen: return seen[target - price], i seen[price] = i return None
print(two_sum([3, 3], 6))print(two_sum([3], 6))(0, 1) None
What this code does
- Two different items with the value 3 pair up: indexes 0 and 1.
- A single 3 does not pair with itself, because it is stored only after its own lookup.
The dictionary maps a price to its index. One pass gives O(n) time and O(n) space. The lookup comes before the insert, so a price never pairs with itself.
Group anagrams by a shared key
Anagram is a word made from exactly the same letters as another word, in a different order. "listen" and "silent" are anagrams.
Words that are anagrams contain the same letters. Sort the letters of a word to make a key, and collect every word under its key.
from collections import defaultdict
words = ["listen", "silent", "enlist", "google", "gogole"]groups = defaultdict(list)for word in words: groups["".join(sorted(word))].append(word)print(list(groups.values()))Example 5 · Groups in order of first appearance
words = ["eat", "tea", "tan", "ate", "nat", "bat"]groups = {}for word in words: groups.setdefault("".join(sorted(word)), []).append(word)for group in groups.values(): print(group)['eat', 'tea', 'ate'] ['tan', 'nat'] ['bat']
What this code does
setdefaultadds an empty list the first time a key is seen, then returns the list.- A dict keeps insertion order, so the groups appear in the order their first word arrived.
Example 6 · Anagram test with Counter
from collections import Counter
print(Counter("listen") == Counter("silent"))print(Counter("aab") == Counter("abb"))print(set("aab") == set("abb"))True False True
What this code does
- Counter compares how many times each letter appears, which is what an anagram needs. It costs O(k).
- Comparing sets is wrong here: "aab" and "abb" have the same letters but not the same counts.
Sorting a word of k letters costs O(k log k). For long words, a tuple of letter counts is a key that costs O(k).
Keys must be hashable
Hashable describes a value that cannot change, so its hash stays the same. int, str and tuples of hashable items are hashable. list, dict and set are not, and cannot be keys.
A dictionary key or set item must never change, or its position would be wrong. Tuples can be keys. Lists cannot, so turn a list into a tuple first.
seen = set()seen.add((2, 3))print((2, 3) in seen)try: seen.add([2, 3])except TypeError as error: print(error)Example 7 · Tuples as keys
visited = {(0, 0), (0, 1)}print((0, 1) in visited)print((1, 0) in visited)note = {(0, 1): "start"}print(note[(0, 1)])True False start
What this code does
- A pair of numbers is a tuple, so it works as a set item or dictionary key.
- Grid cells and map coordinates are often stored this way.
Coordinates, pairs and sorted-letter keys are usually tuples or strings.
Next step
Check your understanding
12 quick questions