stdlib Power Tools for DSA

A huge chunk of “algorithm knowledge” in Python is really “know your stdlib”. Priority queues, binary search, combinatorics, memoization — they’re all one importimport away. This page is your toolbox: what each module gives you, and when to reach for it.

What you’ll learn

collectionscollections: dequedeque, CounterCounter, defaultdictdefaultdict, OrderedDictOrderedDict.
heapqheapq: a min-heap out of a plain list — push/pop, heapify, top-k.
bisectbisect: $O(\log n)$ search and sorted insertion on a sorted list.
itertoolsitertools: permutations, combinations, product, running totals.
functoolsfunctools: lru_cachelru_cache / cachecache for instant memoization, cmp_to_keycmp_to_key for custom sort comparisons.
mathmath: gcdgcd, isqrtisqrt, combcomb, infinf — stop hand-rolling these.

`collectionscollections` — beyond deque

You already met dequedeque for O(1)-both-ends. Three more are everywhere in CP:

collections_tour.py

from collections import Counter, defaultdict, OrderedDict
 
# Counter: frequency table in one call
freq = Counter("mississippi")
print("Counter:", freq)
print("2 most common:", freq.most_common(2))
 
# defaultdict: no more `if key not in d: d[key] = []`
groups = defaultdict(list)
for word in ["cat", "car", "dog", "do"]:
    groups[word[0]].append(word)
print("defaultdict:", dict(groups))
 
# OrderedDict: dict that remembers insertion order + supports move_to_end
# (plain dict has kept insertion order since 3.7, but OrderedDict adds
#  move_to_end/popitem(last=...) which is the backbone of an LRU cache)
od = OrderedDict()
od["a"] = 1
od["b"] = 2
od.move_to_end("a")
print("OrderedDict after move_to_end:", od)

collections_tour.py

from collections import Counter, defaultdict, OrderedDict
 
# Counter: frequency table in one call
freq = Counter("mississippi")
print("Counter:", freq)
print("2 most common:", freq.most_common(2))
 
# defaultdict: no more `if key not in d: d[key] = []`
groups = defaultdict(list)
for word in ["cat", "car", "dog", "do"]:
    groups[word[0]].append(word)
print("defaultdict:", dict(groups))
 
# OrderedDict: dict that remembers insertion order + supports move_to_end
# (plain dict has kept insertion order since 3.7, but OrderedDict adds
#  move_to_end/popitem(last=...) which is the backbone of an LRU cache)
od = OrderedDict()
od["a"] = 1
od["b"] = 2
od.move_to_end("a")
print("OrderedDict after move_to_end:", od)

CounterCounter alone replaces a whole “build a frequency dict” pattern you’d otherwise write by hand every time.

`heapqheapq` — a min-heap for free

Python has no built-in heap type — heapqheapq turns an ordinary listlist into a binary min-heap using module-level functions. The smallest element is always at index 00.

heapq_basics.py

import heapq
 
heap = []
for x in [5, 1, 8, 3, 9, 2]:
    heapq.heappush(heap, x)   # O(log n)
 
print("smallest:", heap[0])          # O(1) — peek
print("pop order:", [heapq.heappop(heap) for _ in range(3)])   # O(log n) each
 
# heapify: turn an existing list into a heap in-place, O(n)
data = [7, 2, 9, 1, 5]
heapq.heapify(data)
print("heapified:", data)
 
# top-k without sorting the whole thing
nums = [4, 1, 7, 3, 8, 2, 9]
print("3 largest:", heapq.nlargest(3, nums))
print("3 smallest:", heapq.nsmallest(3, nums))

heapq_basics.py

import heapq
 
heap = []
for x in [5, 1, 8, 3, 9, 2]:
    heapq.heappush(heap, x)   # O(log n)
 
print("smallest:", heap[0])          # O(1) — peek
print("pop order:", [heapq.heappop(heap) for _ in range(3)])   # O(log n) each
 
# heapify: turn an existing list into a heap in-place, O(n)
data = [7, 2, 9, 1, 5]
heapq.heapify(data)
print("heapified:", data)
 
# top-k without sorting the whole thing
nums = [4, 1, 7, 3, 8, 2, 9]
print("3 largest:", heapq.nlargest(3, nums))
print("3 smallest:", heapq.nsmallest(3, nums))

heapqheapq is always a min-heap. Need a max-heap? Negate the values on the way in and out:

heapq_max_heap.py

import heapq
 
nums = [4, 1, 7, 3, 8]
max_heap = [-x for x in nums]
heapq.heapify(max_heap)
 
heapq.heappush(max_heap, -10)   # push -10 to represent "10"
largest = -heapq.heappop(max_heap)
print("largest via negation trick:", largest)

heapq_max_heap.py

import heapq
 
nums = [4, 1, 7, 3, 8]
max_heap = [-x for x in nums]
heapq.heapify(max_heap)
 
heapq.heappush(max_heap, -10)   # push -10 to represent "10"
largest = -heapq.heappop(max_heap)
print("largest via negation trick:", largest)

`bisectbisect` — binary search on a sorted list

bisectbisect gives you $O(\log n)$ search and $O(\log n)$ -search sorted insertion (the insertion itself is still $O(n)$ due to the shift, but finding where to insert is fast).

bisect_basics.py

import bisect
 
sorted_nums = [1, 3, 3, 5, 7, 9]
 
# bisect_left: leftmost valid insertion point (before existing equals)
print("bisect_left for 3: ", bisect.bisect_left(sorted_nums, 3))
# bisect_right: rightmost valid insertion point (after existing equals)
print("bisect_right for 3:", bisect.bisect_right(sorted_nums, 3))
 
# insort: insert while KEEPING the list sorted
bisect.insort(sorted_nums, 4)
print("after insort(4):", sorted_nums)
 
# classic use: is `target` present, in O(log n)?
target = 7
i = bisect.bisect_left(sorted_nums, target)
present = i < len(sorted_nums) and sorted_nums[i] == target
print("7 present?", present)

bisect_basics.py

import bisect
 
sorted_nums = [1, 3, 3, 5, 7, 9]
 
# bisect_left: leftmost valid insertion point (before existing equals)
print("bisect_left for 3: ", bisect.bisect_left(sorted_nums, 3))
# bisect_right: rightmost valid insertion point (after existing equals)
print("bisect_right for 3:", bisect.bisect_right(sorted_nums, 3))
 
# insort: insert while KEEPING the list sorted
bisect.insort(sorted_nums, 4)
print("after insort(4):", sorted_nums)
 
# classic use: is `target` present, in O(log n)?
target = 7
i = bisect.bisect_left(sorted_nums, target)
present = i < len(sorted_nums) and sorted_nums[i] == target
print("7 present?", present)

`itertoolsitertools` — combinatorics without the nested loops

itertools_tour.py

from itertools import permutations, combinations, product, accumulate
 
items = ["A", "B", "C"]
 
print("permutations:", list(permutations(items, 2)))
print("combinations:", list(combinations(items, 2)))
print("product:     ", list(product([0, 1], repeat=2)))
 
# accumulate: running totals — perfect for prefix sums
nums = [1, 2, 3, 4, 5]
print("prefix sums:", list(accumulate(nums)))

itertools_tour.py

from itertools import permutations, combinations, product, accumulate
 
items = ["A", "B", "C"]
 
print("permutations:", list(permutations(items, 2)))
print("combinations:", list(combinations(items, 2)))
print("product:     ", list(product([0, 1], repeat=2)))
 
# accumulate: running totals — perfect for prefix sums
nums = [1, 2, 3, 4, 5]
print("prefix sums:", list(accumulate(nums)))

Prefix sums via accumulateaccumulate turn “sum of a range” queries from $O(n)$ each into $O(1)$ each after one $O(n)$ pre-pass — a pattern you’ll reuse constantly.

`functoolsfunctools` — memoization and custom sorting

functools_tour.py

from functools import lru_cache, cmp_to_key
 
# lru_cache: turns exponential naive recursion into linear, for free
@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)
 
print("fib(30):", fib(30))   # instant, thanks to memoization
 
# cmp_to_key: sort with a custom two-argument comparator
def by_length_then_alpha(a, b):
    if len(a) != len(b):
        return len(a) - len(b)
    return -1 if a < b else (1 if a > b else 0)
 
words = ["banana", "fig", "kiwi", "apple"]
print("custom sort:", sorted(words, key=cmp_to_key(by_length_then_alpha)))

functools_tour.py

from functools import lru_cache, cmp_to_key
 
# lru_cache: turns exponential naive recursion into linear, for free
@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)
 
print("fib(30):", fib(30))   # instant, thanks to memoization
 
# cmp_to_key: sort with a custom two-argument comparator
def by_length_then_alpha(a, b):
    if len(a) != len(b):
        return len(a) - len(b)
    return -1 if a < b else (1 if a > b else 0)
 
words = ["banana", "fig", "kiwi", "apple"]
print("custom sort:", sorted(words, key=cmp_to_key(by_length_then_alpha)))

`mathmath` — stop hand-rolling these

math_tour.py

import math
 
print("gcd(48, 18):", math.gcd(48, 18))
print("isqrt(50):  ", math.isqrt(50))    # exact integer sqrt, no float error
print("comb(10, 3):", math.comb(10, 3))  # n choose k
print("inf trick:  ", min(math.inf, 5, 3, math.inf))

math_tour.py

import math
 
print("gcd(48, 18):", math.gcd(48, 18))
print("isqrt(50):  ", math.isqrt(50))    # exact integer sqrt, no float error
print("comb(10, 3):", math.comb(10, 3))  # n choose k
print("inf trick:  ", min(math.inf, 5, 3, math.inf))

math.infmath.inf (or float("inf")float("inf")) is the standard “worse than anything” sentinel for running minimums in shortest-path and DP code.

Which tool for which job

diagram stdlib tool map for common CP tasks mermaid

  graph TD
    A[What do you need?] --> B["Repeated min/max extraction
(top-k, Dijkstra, scheduling)"]
    A --> C["Search / insert into a SORTED list
(O(log n))"]
    A --> D["Count occurrences / group items"]
    A --> E["Generate all subsets / orders / pairs"]
    A --> F["Same subproblem solved many times
(recursion, DP)"]
    A --> G["Custom, non-key-based sort rule"]

    B --> H[heapq]
    C --> I[bisect]
    D --> J["Counter / defaultdict"]
    E --> K[itertools]
    F --> L["functools.lru_cache"]
    G --> M["functools.cmp_to_key"]

Practice

Drill 1 — top-k with a heap. Return the 2 largest values without sorting the whole list.

Drill 2 — sorted insert with bisect. Keep a list sorted as you insert, without re-sorting each time.

Drill 3 — memoize recursion. Speed up a naive recursive Fibonacci with lru_cachelru_cache so it doesn’t re-solve the same subproblem millions of times.

Recap

collectionscollections: CounterCounter for frequencies, defaultdictdefaultdict to skip existence checks, dequedeque/OrderedDictOrderedDict for order-aware structures.
heapqheapq: min-heap on a plain list; negate values for a max-heap.
bisectbisect: $O(\log n)$ search and sorted-insert point on a sorted list.
itertoolsitertools: permutations/combinations/product for brute force, accumulateaccumulate for prefix sums.
functools.lru_cachefunctools.lru_cache turns exponential recursion into linear; cmp_to_keycmp_to_key handles custom comparators.
math.gcdmath.gcd/isqrtisqrt/combcomb/infinf — small utilities, always faster and safer than hand-rolled versions.

Next: Fast I/O and Beating TLE — reading and writing at contest speed.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

stdlib Power Tools for DSA

What you’ll learn

collectionscollections — beyond deque

heapqheapq — a min-heap for free

bisectbisect — binary search on a sorted list

itertoolsitertools — combinatorics without the nested loops

functoolsfunctools — memoization and custom sorting

mathmath — stop hand-rolling these