Dictionaries and Sets in Python
If you learn one thing from this primer that unlocks fast solutions, it is the dictionary. Dictionaries and sets use hashing to give you average O(1) lookups, which turns many O(n squared) brute-force solutions into O(n) ones.
Dictionaries: key to value#
A dictionary maps unique keys to values:
1ages = {"ana": 30, "ben": 25}
2print(ages["ana"]) # 30
3ages["cara"] = 40 # add a new pair
4ages["ben"] = 26 # update an existing value
5print("ben" in ages) # True (fast membership, O(1) average)
Accessing a missing key raises KeyError. Use .get() to supply a default instead:
1print(ages.get("dan", 0)) # 0 (no error)
The counting pattern#
Counting occurrences is one of the most common DSA tasks. A dictionary handles it cleanly:
1text = "banana"
2counts = {}
3for ch in text:
4 counts[ch] = counts.get(ch, 0) + 1
5print(counts) # {'b': 1, 'a': 3, 'n': 2}
Python ships a shortcut for exactly this:
1from collections import Counter
2print(Counter("banana")) # Counter({'a': 3, 'n': 2, 'b': 1})
Iterating over a dictionary#
1scores = {"math": 90, "cs": 95}
2for subject, score in scores.items():
3 print(subject, score)
4
5print(list(scores.keys())) # ['math', 'cs']
6print(list(scores.values())) # [90, 95]
Sets: unique membership#
A set stores unique items with no order and gives O(1) membership tests:
1seen = set()
2seen.add(3)
3seen.add(3) # duplicate ignored
4print(3 in seen) # True (O(1) average, unlike a list)
5print(len(seen)) # 1
Sets shine when you need to detect duplicates or track what you have visited:
1def has_duplicate(nums):
2 seen = set()
3 for n in nums:
4 if n in seen:
5 return True
6 seen.add(n)
7 return False
8
9print(has_duplicate([1, 2, 3, 2])) # True
Set operations#
Sets support mathematical operations, which are useful for comparing collections:
1a = {1, 2, 3}
2b = {2, 3, 4}
3print(a & b) # {2, 3} intersection
4print(a | b) # {1, 2, 3, 4} union
5print(a - b) # {1} difference
Why this matters#
Compare the two-sum brute force (checking every pair, O(n squared)) to the dictionary version from the track overview, which runs in a single O(n) pass. That speedup comes entirely from swapping a nested scan for a hash lookup. See the Big-O cheat sheet for the full comparison.
Next up: strings, which behave a lot like the sequences you have already seen.