Built-in data structures & their complexity

The single most common reason an interview solution is "too slow" is the wrong container. Swap a list for a set and an x in xs check drops from O(n) to O(1) — the whole algorithm goes from O(n²) to O(n) without touching the logic.

Why this matters

Choosing the right data structure is the optimization most of the time. This lesson goes from the four core builtins (list, tuple, dict, set/frozenset) and the cost of each operation, to the collections power tools (deque, Counter, defaultdict, OrderedDict, namedtuple), and finally to two algorithm-enabling modules (heapq for priority/top-k, bisect for sorted arrays). For every structure we answer three questions: what is it (the underlying mechanism — array? hash table? heap?), what does each operation cost (big-O), and when to reach for it and when not to.

The one big idea

Big-O follows from the mechanism. A dynamic array (list/deque) is O(1) at the end but O(n) in the middle or front. A hash table (dict/set) is O(1) average lookup and insert, with unordered logic. A binary heap (heapq) is O(log n) push/pop and O(1) peek-min. A sorted array + bisect is O(log n) search but O(n) insert (shifting). Memorize the mechanism and the costs are not facts to recall but consequences.

The complexity table

list — dynamic array, the default sequence

Mechanism: a contiguous resizable array of object references. Use it for ordered data, index access, or a stack (append/pop at the end). Do not use it as a queue or for front-insertion — pop(0) and insert(0, ...) are O(n) because every other element must shift. Use a deque instead.

xs = [1, 2, 3]
xs.append(4)                                     # O(1) amortized
assert xs == [1, 2, 3, 4]
assert xs.pop() == 4                             # O(1) from the end

# As a STACK: append = push, pop = pop. Both O(1).
stack = []
stack.append(10); stack.append(20)
assert stack.pop() == 20                         # LIFO

# The trap: pop(0) is O(n) — it reindexes the whole list.
xs.pop(0)                                        # O(n): removes 1, shifts rest
assert xs == [2, 3]

tuple — immutable, hashable sequence

Tuples are immutable and therefore hashable, so they can serve as dict keys or set members. Use them for fixed-size records like (x, y), composite dict keys, returning multiple values, or anything you want frozen.

point = (3, 4)
seen = {point: "origin-ish"}                     # tuple as a hashable key
assert seen[(3, 4)] == "origin-ish"
# Cannot mutate: point[0] = 9 would raise TypeError.

dict — hash table, insertion-ordered (3.7+)

Mechanism: an open-addressing hash table, average O(1) get/set/del/contains. Use it for any lookup-by-key, counting, memoization, or adjacency lists. get() supplies a default; setdefault() reads-or-initializes in one call.

freq = {}
for ch in "mississippi":
    freq[ch] = freq.get(ch, 0) + 1               # get-with-default counting
assert freq == {"m": 1, "i": 4, "s": 4, "p": 2}

# setdefault: read-or-initialize in one call (grouping without defaultdict).
groups = {}
for word in ["ant", "bee", "ape"]:
    groups.setdefault(word[0], []).append(word)
assert groups == {"a": ["ant", "ape"], "b": ["bee"]}

# Insertion order is guaranteed; keys()/values()/items() reflect it.
assert list(freq.keys()) == ["m", "i", "s", "p"]

set / frozenset — hash table of unique keys

O(1) membership and set algebra (| union, & intersection, - difference). Use a set for dedup, "have I seen this?", and fast membership. Use frozenset when you need an immutable set — for example as a dict key or an element of another set.

a = {1, 2, 3}
b = {3, 4, 5}
assert (2 in a) is True                          # O(1) vs O(n) for a list
assert a | b == {1, 2, 3, 4, 5}                  # union
assert a & b == {3}                              # intersection
assert a - b == {1, 2}                           # difference

# Dedup a list while we're at it (order not preserved).
assert set([1, 1, 2, 2, 3]) == {1, 2, 3}

# frozenset is hashable -> can live inside a set or key a dict.
fs = frozenset({1, 2})
container = {fs: "pair"}
assert container[frozenset({2, 1})] == "pair"

deque — double-ended queue, O(1) at both ends

Mechanism: a doubly-linked list of fixed-size blocks, so there is no reindexing on the ends. Use it as a queue (the BFS workhorse), a sliding window, or any time you push/pop the front. Do not use it for random indexed access into the middle — that is O(n).

from collections import deque

q = deque([1, 2, 3])
q.appendleft(0)                                  # O(1) front insert
q.append(4)                                      # O(1) back insert
assert list(q) == [0, 1, 2, 3, 4]
assert q.popleft() == 0                          # O(1) front removal
assert q.pop() == 4                              # O(1) back removal

# As a FIFO QUEUE (the BFS workhorse): append to enqueue, popleft to dequeue.
queue = deque()
queue.append("a"); queue.append("b")
assert queue.popleft() == "a"                    # FIFO order

# maxlen makes a fixed-size sliding window that auto-evicts the oldest.
window = deque(maxlen=3)
for v in [1, 2, 3, 4]:
    window.append(v)
assert list(window) == [2, 3, 4]                 # 1 fell off the left

Counter — a dict subclass for tallying

Use it for frequency counts, "top-k frequent", and multiset arithmetic. Building counts is O(n); most_common(k) is the top-k-by-frequency idiom. Missing keys return 0 instead of raising, and equality ignores order and zero counts — perfect for anagram checks.

from collections import Counter

c = Counter("mississippi")                       # O(n) to build
assert c["s"] == 4
assert c["z"] == 0                               # missing key -> 0, no error

# most_common(k): the k highest-frequency items, sorted descending.
assert c.most_common(2) == [("i", 4), ("s", 4)]

# Counters support arithmetic (multiset add/subtract).
assert Counter("aab") + Counter("abc") == Counter({"a": 3, "b": 2, "c": 1})

# Equality ignores order and zero counts -> great for anagram checks.
assert Counter("listen") == Counter("silent")

defaultdict — auto-creates a default for missing keys

Use it for grouping (defaultdict(list)), counting (defaultdict(int)), and adjacency lists for graphs (defaultdict(list)). It removes the setdefault boilerplate.

from collections import defaultdict

words = ["ant", "bee", "ape", "bat"]
groups = defaultdict(list)                       # missing key -> new []
for w in words:
    groups[w[0]].append(w)                       # no setdefault boilerplate
assert groups == {"a": ["ant", "ape"], "b": ["bee", "bat"]}

# defaultdict(int) for counting.
counts = defaultdict(int)
for ch in "aabbb":
    counts[ch] += 1                              # missing key -> starts at 0
assert counts == {"a": 2, "b": 3}

# Graph adjacency list from an edge list (undirected).
adj = defaultdict(list)
for u, v in [(1, 2), (1, 3)]:
    adj[u].append(v); adj[v].append(u)
assert adj[1] == [2, 3]

OrderedDict — order plus LRU primitives

Plain dict has preserved insertion order since 3.7, so OrderedDict is mostly worth it for move_to_end and popitem(last=False), which together build an O(1) LRU cache.

from collections import OrderedDict

od = OrderedDict()
od["a"] = 1; od["b"] = 2; od["c"] = 3
od.move_to_end("a")                              # mark 'a' as most-recent
assert list(od.keys()) == ["b", "c", "a"]
# Evict the least-recently-used (front) item, O(1).
evicted_key, _ = od.popitem(last=False)
assert evicted_key == "b"

namedtuple — a lightweight immutable record

Use it for return values or records where p.x reads better than p[0], but you still want tuple immutability and cheap memory. It stays index-accessible and unpackable.

from collections import namedtuple

Point = namedtuple("Point", ["x", "y"])
p = Point(3, 4)
assert p.x == 3 and p.y == 4                     # named access
assert p[0] == 3                                 # still index-accessible
x, y = p                                         # still unpackable
assert (x, y) == (3, 4)
assert p._replace(x=99) == Point(99, 4)          # returns a NEW tuple

heapq — a binary min-heap on a plain list

Mechanism: an array-backed complete binary tree where heap[0] is always the minimum. Use it for Dijkstra, repeatedly taking the smallest or largest, top-k, and k-way merge. Two tricks: it is a min-heap, so for a max-heap push negated values; and for the top-k largest in O(n log k), keep a min-heap of size k and pop the smallest whenever it grows past k.

import heapq

h = [5, 1, 3]
heapq.heapify(h)                                 # O(n) build
assert h[0] == 1                                 # peek min is O(1)
heapq.heappush(h, 0)                             # O(log n)
assert heapq.heappop(h) == 0                     # O(log n) -> smallest out

# TOP-K LARGEST with a size-k min-heap (classic, O(n log k)).
nums = [3, 1, 5, 12, 2, 11]
k = 3
keep = []
for n in nums:
    heapq.heappush(keep, n)
    if len(keep) > k:
        heapq.heappop(keep)                      # drop the smallest of the heap
assert sorted(keep) == [5, 11, 12]               # the 3 largest

# nlargest / nsmallest do this for you.
assert heapq.nlargest(3, nums) == [12, 11, 5]
assert heapq.nsmallest(2, nums) == [1, 2]

# K-WAY MERGE of already-sorted streams, lazily, in O(total log k).
merged = list(heapq.merge([1, 4, 7], [2, 3], [5, 6]))
assert merged == [1, 2, 3, 4, 5, 6, 7]

bisect — binary search on a sorted list

Use it to keep a list sorted as you insert, count elements ≤ x, find the closest element, or run range queries on sorted data. bisect_left(a, x) is the first index where x could go (left of duplicates); bisect_right(a, x) is the index after any existing x. Their difference is the number of occurrences of x, and together they bracket the run of x.

import bisect

a = [1, 2, 2, 2, 5, 7]
assert bisect.bisect_left(a, 2) == 1             # leftmost slot for 2
assert bisect.bisect_right(a, 2) == 4            # just past the last 2
# Count occurrences of 2 = right - left.
assert bisect.bisect_right(a, 2) - bisect.bisect_left(a, 2) == 3

# "How many elements are < 5?" == bisect_left(a, 5).
assert bisect.bisect_left(a, 5) == 4

# insort inserts while keeping order (O(log n) search + O(n) shift).
b = [1, 3, 5]
bisect.insort(b, 4)
assert b == [1, 3, 4, 5]

# Binary "contains" via bisect_left.
def contains(arr, x):
    i = bisect.bisect_left(arr, x)
    return i < len(arr) and arr[i] == x
assert contains(a, 5) is True and contains(a, 6) is False