Python Standard Library for DSA
Python ships with a standard library full of data structures and helpers that are already tuned and correct. Knowing them turns a fifteen-line loop into a one-liner and, more importantly, avoids off-by-one bugs. This page walks through the modules you will use most for algorithms, with a worked example for each.
If you have not read Python for DSA yet, start there for the basics these modules build on.
collections.Counter: count things#
Counter is a dict subclass that counts hashable items. It is the fastest way to build a frequency map.
1from collections import Counter
2
3text = "mississippi"
4counts = Counter(text)
5print(counts) # Counter({'i': 4, 's': 4, 'p': 2, 'm': 1})
6print(counts["s"]) # 4
7print(counts["z"]) # 0 (missing keys return 0, no KeyError)
8
9# The n most common items
10print(counts.most_common(2)) # [('i', 4), ('s', 4)]
11
12# Anagram check: two strings are anagrams if their counts match
13print(Counter("listen") == Counter("silent")) # True
Counter supports arithmetic too: Counter(a) - Counter(b) gives the surplus counts in a.
collections.defaultdict: no missing-key errors#
defaultdict builds a default value the first time you touch a missing key. This removes the “check if key exists, then create” dance when grouping.
1from collections import defaultdict
2
3pairs = [("fruit", "apple"), ("veg", "carrot"), ("fruit", "pear")]
4
5groups = defaultdict(list)
6for category, item in pairs:
7 groups[category].append(item) # no need to init the list
8
9print(dict(groups)) # {'fruit': ['apple', 'pear'], 'veg': ['carrot']}
10
11# Adjacency list for a graph, built with defaultdict
12graph = defaultdict(list)
13for u, v in [(1, 2), (1, 3), (2, 3)]:
14 graph[u].append(v)
15print(dict(graph)) # {1: [2, 3], 2: [3]}
Pass the type you want as the factory: defaultdict(int) for counters, defaultdict(set) for unique groups.
collections.deque: a fast queue#
A deque (double-ended queue) adds and removes from both ends in O(1). A plain list is O(n) to pop from the front, so use a deque for queues and breadth-first search.
1from collections import deque
2
3queue = deque([1, 2, 3])
4queue.append(4) # add to the right
5queue.appendleft(0) # add to the left
6print(queue) # deque([0, 1, 2, 3, 4])
7
8print(queue.popleft()) # 0 (fast, O(1))
9print(queue.pop()) # 4
10
11# Breadth-first traversal uses a deque as the frontier
12graph = {1: [2, 3], 2: [4], 3: [], 4: []}
13seen, frontier = {1}, deque([1])
14order = []
15while frontier:
16 node = frontier.popleft()
17 order.append(node)
18 for nb in graph[node]:
19 if nb not in seen:
20 seen.add(nb)
21 frontier.append(nb)
22print(order) # [1, 2, 3, 4]
heapq: a min-heap (priority queue)#
heapq turns a plain list into a binary min-heap. Push and pop are O(log n), and the smallest item is always at index 0. There is no separate max-heap, so negate values to simulate one.
1import heapq
2
3heap = []
4for value in [5, 1, 8, 3]:
5 heapq.heappush(heap, value)
6
7print(heapq.heappop(heap)) # 1 (always the smallest)
8print(heapq.heappop(heap)) # 3
9
10# Heapify an existing list in place (O(n))
11data = [9, 4, 7, 1]
12heapq.heapify(data)
13print(data[0]) # 1
14
15# k smallest without sorting everything
16print(heapq.nsmallest(2, [9, 4, 7, 1, 5])) # [1, 4]
To store a priority alongside a value, push tuples: heapq.heappush(heap, (priority, item)). The heap compares the first element first.
bisect: keep a list sorted#
bisect does binary search on a sorted list. bisect_left and bisect_right find the insertion point in O(log n), and insort inserts while keeping order.
1import bisect
2
3sorted_nums = [1, 3, 3, 5, 8]
4
5# Where would 4 go to keep the list sorted?
6print(bisect.bisect_left(sorted_nums, 4)) # 3
7print(bisect.bisect_right(sorted_nums, 3)) # 3
8
9# Insert while preserving order
10bisect.insort(sorted_nums, 4)
11print(sorted_nums) # [1, 3, 3, 4, 5, 8]
12
13# Count how many items are less than 5
14print(bisect.bisect_left(sorted_nums, 5)) # 4
The insertion itself is still O(n) because the list must shift elements, but the search is O(log n).
itertools: looping building blocks#
itertools provides memory-efficient iterators for combining and slicing sequences.
1from itertools import accumulate, product, combinations, chain
2
3# Running totals (prefix sums)
4print(list(accumulate([1, 2, 3, 4]))) # [1, 3, 6, 10]
5
6# Cartesian product (nested loops without nesting)
7print(list(product([0, 1], repeat=2))) # [(0,0),(0,1),(1,0),(1,1)]
8
9# All 2-item combinations
10print(list(combinations(["a", "b", "c"], 2))) # [('a','b'),('a','c'),('b','c')]
11
12# Flatten several iterables into one stream
13print(list(chain([1, 2], [3, 4]))) # [1, 2, 3, 4]
These return iterators, so wrap them in list() to see the values. accumulate in particular is a clean way to build prefix sums.
functools.lru_cache: memoize recursion#
lru_cache stores the results of a function so repeated calls with the same arguments return instantly. It converts an exponential recursion into a linear one, which is the essence of top-down dynamic programming.
1from functools import lru_cache
2
3@lru_cache(maxsize=None)
4def fib(n):
5 if n < 2:
6 return n
7 return fib(n - 1) + fib(n - 2)
8
9print(fib(50)) # 12586269025 (instant, thanks to the cache)
10print(fib.cache_info()) # shows hits, misses, and cache size
The arguments must be hashable, so cache functions that take numbers, strings, or tuples rather than lists. Use fib.cache_clear() to reset between test cases.
Where to go next#
Each of these modules maps to a data structure or pattern in the curriculum. Before you use them in a solution, check the Big-O cheat sheet so you know the cost of the operation you are calling, then apply them to real algorithms.