The Python toolkit

Problem

An algorithm's complexity is only as good as the data structure underneath it. The same idea, "remove the oldest item", is O(1) on one container and O(n) on another, and picking the wrong one turns a linear solution into a quadratic one without any visible change in the code. Python also offers shortcuts, such as Counter and sorted(key=...), that replace twenty lines of loop with one.

The signals below tell you which tool to reach for. They also appear later in nearly every pattern page.

Intuition

Every container is a trade. A list is a row of boxes: reaching box k is instant, but squeezing a box in at the front means moving all the others along. A dict or set is a coat check: hand over a ticket (the hash of the key) and the attendant goes straight to the hook, without scanning the rack. A deque is a row you can add to or remove from at either end. A heap is a tournament bracket kept loosely sorted: only the champion is guaranteed to be on top, but keeping that true after every change takes just one walk up or down a tree.

So the skill is not memorizing syntax. It is asking "which operation will my loop repeat n times?" and choosing the container for which that operation is cheap.

The tree is only a way of reading the array. Index i has children 2i + 1 and 2i + 2, so no pointers are stored.

Mechanics

What each operation costs

Why hash lookups are O(1)

A dict computes hash(key), turns it into a slot number, and checks that slot. If two keys land in the same slot, it probes nearby slots. As long as the table stays under a load limit and resizes (doubling, which is the amortized argument from the complexity analysis page), the expected number of probes is a constant. The caveat is that this is an average: adversarial keys that all collide would degrade it, which interview inputs don't do.

The heap invariant

A binary min-heap stores a complete binary tree in an array with one rule: every parent is less than or equal to both children. heappush appends to the end and sifts up, swapping with the parent while it is larger. heappop takes the root, moves the last element into the root slot and sifts down, swapping with the smaller child while it is larger than that child. A swap only ever fixes one violated pair and the tree has height ⌊log₂ n⌋, so each operation is O(log n). Python has only a min-heap. For a max-heap, push negated values.

The binary search invariant

bisect_left(a, x) returns the first index where a[index] >= x (or len(a) if there is none). The search keeps the answer inside the half-open range [low, high): if the middle value is smaller than x, everything up to the middle is too small, so low = middle + 1; otherwise the middle may itself be the answer, so high = middle. The range halves each time and ends with low == high, which is the answer. The halving argument bounds this at about log₂ n probes.

Worked example

First, build a heap by pushing 5, 3, 8, 1, 9, 2 in that order. The array after each push:

The array is not sorted, only heap-ordered. Popping repeatedly returns the values in order: 1, 2, 3, 5, 8, 9. That is heapsort in two lines.

Second, a binary search with bisect_left over the sorted list [1, 3, 5, 7, 9, 11, 13, 15], looking for 11:

The insertion point is index 5, reached in 3 probes for 8 items, the same answer bisect.bisect_left gives.

Blue cells are still candidates; the amber outline is the probe.

Implementation

from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
import heapq

# Counting and membership
counts = Counter("abracadabra")            # Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})
seen = set()                               # O(1) average add / lookup
groups = defaultdict(list)                 # missing key starts as []
for word in ["eat", "tea", "tan"]:
    groups["".join(sorted(word))].append(word)   # anagram key -> words

# Queue: both ends in O(1)
queue = deque([start])
while queue:
    node = queue.popleft()
    # ... queue.append(neighbour)

# Heap: smallest first; negate for a max-heap
heap = []
heapq.heappush(heap, (distance, node))     # tuples compare element by element
smallest = heapq.heappop(heap)
heapq.heapify(existing_list)               # O(n), cheaper than n pushes

# Sorted list: positions
position = bisect_left(sorted_list, x)     # first index with value >= x
present = position < len(sorted_list) and sorted_list[position] == x
how_many = bisect_right(sorted_list, hi) - bisect_left(sorted_list, lo)

# Sorting by a key, and the other builtins
people.sort(key=lambda p: (-p.score, p.name))   # descending score, then name
total = sum(x for x in nums if x % 2 == 0)
best = max(words, key=len)
pairs = list(zip(a, b))
for index, value in enumerate(nums):
    pass

Variations and edge cases

• Top-k with a bounded heap. Keep a min-heap of size k and push each new value, popping when the size exceeds k. The heap holds the k largest, in O(n log k). heapq.nlargest(k, nums) does this for you.
• Lazy deletion. A heap cannot remove an arbitrary item cheaply. Leave stale entries in and skip them when they reach the top, checking against a dict of current values.
• Tie-breaking. If two heap tuples have equal first elements, Python compares the second ones. Put an integer counter in the tuple when the second item (such as a node object) isn't orderable.
• Mutable keys. [1, 2] can't be a dict key or set member; convert with tuple(...). Likewise [[0] * m] * n makes n references to one row: build a grid with [[0] * m for _ in range(n)].
• Integer division and modulo. // floors toward negative infinity and % of a negative number is non-negative in Python, unlike C or Java. Use int(a / b) or math.trunc when a problem wants truncation toward zero.
• Edge cases that break naive code: empty input, a single element, heappop on an empty heap (raises IndexError), and bisect_left returning len(a) when x is bigger than everything.

Complexity and tradeoffs

Emptying a list of 8 items with pop(0) moves 28 elements in total, against 0 for deque.popleft, and the gap grows as n². The wrong container is the brute-force baseline on many problems, and the right container turns n repeated O(n) steps into n repeated O(1) steps.

• Memory. A set of n integers takes several times the memory of a list of them, because of the hash table's spare slots. The trade for O(1) lookup is nearly always worth it, unless the values fit a small integer range, where a plain boolean array is both smaller and faster.
• Sorting first. If you only need membership, a set (O(n) to build) beats sorting plus binary search (O(n log n) to build). If you need order, ranges or neighbours, the sorted list wins.
• Heap against sorting. A heap helps when items arrive over time or you only need the top k. When all the data is in hand and you need it all in order, one sort is simpler.
• No balanced tree. Python has no built-in ordered set or sorted map. A sorted list with bisect gives O(log n) search but O(n) insertion, which is fine up to about 10⁵ elements; beyond that, think about a different pattern.
• Hash-order assumptions. Dicts preserve insertion order, but sets do not. Never rely on set iteration order in an answer.

Problems

The two problems below are here because they are about the plain tools themselves: slicing, comparing and building lists. The problems that use a heap, a deque or a counter as part of a bigger idea live under the pattern pages.

Easy

• 14. Longest Common Prefix Grind 169 NeetCode 250
  Compare the strings column by column and stop at the first position where any string ends or disagrees.
• 1929. Concatenation of Array NeetCode 250
  The output is the array followed by itself, so index i and i + n hold the same value.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 179. Largest Number Medium
• 380. Insert Delete GetRandom O(1) Medium

Connections

The hash-map page builds on the dict and set rows above. Heaps, top-k and the k-way merge pages build on heapq. Binary search turns the bisect invariant into a general technique, including searching over answers rather than arrays.

Check yourself

References

• Python documentation: the heapq, bisect and collections modules, and "TimeComplexity" in the Python wiki.
• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms: chapter 6 (heapsort and priority queues), chapter 11 (hash tables) and section 2.3 (binary search).
• Sedgewick and Wayne, Algorithms: section 2.4 (priority queues), section 3.4 (hash tables).
• Steven Skiena, The Algorithm Design Manual: sections on dictionaries and priority queues.
• J. W. J. Williams, "Algorithm 232: Heapsort", Communications of the ACM, 1964.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.