The Data Structures and Algorithms Picture Book
array linked list stack tree key → valuehash map graph Choosing the structure is most of the algorithm same problem: O(n²) with a list, O(n) with a hash map learn the trade-offs, not just the code
PLATE 0 — A programmer's toolbox. Each tool is fast at some things and slow at others.
A picture book for grown-ups · with code

Data Structures and Algorithms

Nine spreads on how to store data and process it efficiently: Big-O, arrays, hash maps, stacks and queues, trees, graphs, sorting, and dynamic programming. Code is Python.

Say it like a pro

"A hash map makes the lookup O(1), so the whole thing drops from quadratic to linear time and linear space."

Use the tabs or the ← → keys. Run each snippet and change it.

1 log n n n log n n² input size n →time ↑
PLATE 1 — What matters is how the work grows as the input grows.
Chapter 1 · Big-O

How cost grows with input

Big-O describes the shape of growth, ignoring constants. It tells you whether code will survive 10× or 1,000× more data.

ClassExamplen = 1,000,000
O(1)dict lookup, array index1 step
O(log n)binary search~20 steps
O(n)scan a list1 M
O(n log n)good sorting~20 M
O(n²)nested loops over the same list10¹²: too slow
O(2ⁿ)naive recursion on subsetsimpossible past ~40
# O(n²): for each item, scan the rest
def has_dup_slow(xs):
    return any(xs[i] == xs[j] for i in range(len(xs)) for j in range(i + 1, len(xs)))

# O(n) time, O(n) space: remember what you've seen
def has_dup_fast(xs):
    seen = set()
    for x in xs:
        if x in seen: return True
        seen.add(x)
    return False
time vs space
you can often trade memory for speed
best / average / worst
usually quote the worst unless told otherwise
rule of thumb
~10⁸ simple operations per second in Python-ish speed is optimistic; aim for O(n log n) or better for large n
Say it like a pro

"The nested loop is quadratic; a set makes it linear at the cost of O(n) extra memory."

Array: contiguous 73915 xs[2] → O(1) · insert middle → O(n) Linked list: nodes + pointers 7 →3 →9 → ∅ find k-th → O(n) · insert after node → O(1) Two handy patterns two pointers: l, r walk toward each other (sorted pairs, palindromes) sliding window: grow right, shrink left (longest substring, max sum of k) fast & slow pointers: detect a cycle, find the middle Python list = dynamic array; append is amortized O(1) list.insert(0, x) and x in list are O(n)
PLATE 2 — Arrays are fast to index. Linked lists are fast to splice. Most of the time you want arrays.
Chapter 2 · Arrays, lists & two patterns

Sequences and the pointer tricks

# two pointers: does a sorted list contain a pair summing to target? O(n)
def pair_sum(xs, target):
    l, r = 0, len(xs) - 1
    while l < r:
        s = xs[l] + xs[r]
        if s == target: return (xs[l], xs[r])
        if s < target: l += 1
        else: r -= 1
    return None

# sliding window: max sum of any k consecutive items. O(n)
def max_window(xs, k):
    cur = best = sum(xs[:k])
    for i in range(k, len(xs)):
        cur += xs[i] - xs[i - k]
        best = max(best, cur)
    return best

# linked list node + reverse in place
class Node:
    def __init__(self, val, nxt=None): self.val, self.next = val, nxt
def reverse(head):
    prev = None
    while head:
        head.next, prev, head = prev, head, head.next
    return prev
amortized
occasionally costly (resize), cheap on average
in place
O(1) extra memory
Say it like a pro

"Sorted input: two pointers. Contiguous subarray: a sliding window. Both cut a nested loop to one pass."

"alice" hash() % 8 = 5 0 1 bob → 31 2 3 4 5 alice → 28 → eve → 40 collision: two keys, one bucket (chain) Use a hash map when you ask… "have I seen this?" "how many times?" "what's paired with this key?" Costs average O(1) get/put/delete · worst O(n) with many collisions keys must be hashable (immutable) · no order guarantees across languages
PLATE 3 — Turn a key into an address and jump straight there.
Chapter 3 · Hash maps & sets

The most useful structure in interviews and in real code

# Two-sum: find indices i, j with xs[i] + xs[j] == target.  O(n) time
def two_sum(xs, target):
    idx = {}                              # value → index
    for i, x in enumerate(xs):
        if target - x in idx:
            return idx[target - x], i
        idx[x] = i

# Count frequencies
from collections import Counter, defaultdict
Counter("mississippi")                    # {'i': 4, 's': 4, 'p': 2, 'm': 1}

# Group anagrams
groups = defaultdict(list)
for w in ["eat", "tea", "tan", "ate", "nat", "bat"]:
    groups["".join(sorted(w))].append(w)  # key = sorted letters
print(list(groups.values()))              # [['eat','tea','ate'], ['tan','nat'], ['bat']]

# Set operations
a, b = {1, 2, 3}, {3, 4}
a & b, a | b, a - b                       # intersection, union, difference
load factor
entries ÷ buckets; the table resizes when it gets high
bloom filter
a tiny "probably seen / definitely not" set, used at scale
Say it like a pro

"I trade O(n) memory for O(1) lookups with a hash map, which brings the whole algorithm to linear time."

Stack · LIFO c ← top b a push / pop Queue · FIFO abc front (out)back (in) Where each shows up stack: undo, call stack, parentheses matching, DFS, expression parsing queue: task scheduling, BFS, buffers, message queues deque: sliding-window maximum, double-ended access priority queue (heap): next-smallest task, Dijkstra, top-k Python stack = list (append/pop) · queue = collections.deque (popleft is O(1)) list.pop(0) is O(n). Don't use a list as a queue.
PLATE 4 — Stack: the last thing in is the first out. Queue: first in, first out.
Chapter 4 · Stacks, queues & heaps

Order of processing

# balanced brackets with a stack
def balanced(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    st = []
    for ch in s:
        if ch in "([{": st.append(ch)
        elif ch in pairs:
            if not st or st.pop() != pairs[ch]: return False
    return not st
balanced("{[()]}")   # True        balanced("(]")  # False

# queue and priority queue
from collections import deque
import heapq
q = deque([1, 2, 3]); q.append(4); q.popleft()     # O(1) both ends

h = []
for x in [5, 1, 8, 3]: heapq.heappush(h, x)        # O(log n)
heapq.heappop(h)                                    # → 1, the smallest, O(log n)
heapq.nlargest(2, [5, 1, 8, 3])                     # top-k → [8, 5]
heap
a tree stored in an array where the parent is ≤ its children; peek-min is O(1)
top-k
keep a heap of size k: O(n log k)
monotonic stack
"next greater element" problems in O(n)
Say it like a pro

"A min-heap gives me the next smallest in logarithmic time, so top-k is n log k."

8 3 10 1 6 14 left < node < right Traversals of this tree in-order (L, node, R) 1 3 6 8 10 14 ← sorted for a BST pre-order (node, L, R) 8 3 1 6 10 14 ← copy a tree post-order (L, R, node) 1 6 3 14 10 8 ← delete / evaluate level-order (BFS, row by row) 8 3 10 1 6 14
PLATE 5 — A tree is a node with children. Most tree code is recursion.
Chapter 5 · Trees & recursion

Solve the small case, trust the rest

Recursion = a base case plus a smaller version of the same problem. A balanced BST gives O(log n) search; an unbalanced one degrades to O(n) (so databases use B-trees, languages use red-black trees).

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def height(n):                                  # O(n)
    if n is None: return 0                      # base case
    return 1 + max(height(n.left), height(n.right))

def search(n, target):                          # O(h)
    while n:
        if target == n.val: return True
        n = n.left if target < n.val else n.right
    return False

def inorder(n):
    return inorder(n.left) + [n.val] + inorder(n.right) if n else []

from collections import deque
def level_order(root):                          # BFS with a queue
    out, q = [], deque([root] if root else [])
    while q:
        row = []
        for _ in range(len(q)):
            n = q.popleft(); row.append(n.val)
            q.extend(c for c in (n.left, n.right) if c)
        out.append(row)
    return out
recursion depth
Python's default limit is ~1000; use an explicit stack for deep trees
trie
a tree of characters for prefix search and autocomplete
Say it like a pro

"Base case, recurse on children, combine. It's O(n) since each node is visited once."

A B C D E F BFS from A: A → B, C → D, E → F (shortest path in an unweighted graph) DFS from A: A → B → D → F → E → C … (go deep, then backtrack) Representing a graph adjacency list: {"A": ["B","C"], …} → O(V+E) space, best for sparse graphs adjacency matrix: V×V grid → O(V²) space, O(1) edge check directed / undirected · weighted / not · cyclic / acyclic (DAG)
PLATE 6 — Anything with "things connected to things" is a graph: maps, networks, dependencies.
Chapter 6 · Graphs

BFS, DFS, and shortest paths

from collections import deque
import heapq

graph = {"A": ["B","C"], "B": ["A","D"], "C": ["A","E"], "D": ["B","F"], "E": ["C","F"], "F": ["D","E"]}

def bfs_shortest(g, start, goal):               # fewest hops. O(V+E)
    q, seen = deque([(start, [start])]), {start}
    while q:
        node, path = q.popleft()
        if node == goal: return path
        for nb in g[node]:
            if nb not in seen:
                seen.add(nb); q.append((nb, path + [nb]))

def dfs(g, node, seen=None):                    # O(V+E): connectivity, cycles, components
    seen = seen or set()
    seen.add(node)
    for nb in g[node]:
        if nb not in seen: dfs(g, nb, seen)
    return seen

def dijkstra(g, src):                           # weighted, non-negative. O((V+E) log V)
    dist = {src: 0}; pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float("inf")): continue
        for v, w in g[u]:                       # g[u] = [(neighbor, weight), …]
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd; heapq.heappush(pq, (nd, v))
    return dist
topological sort
order tasks so dependencies come first (build systems, course prerequisites)
union-find
fast "are these connected?" for components and Kruskal's MST
A*
Dijkstra with a heuristic, for maps and games
Say it like a pro

"BFS for fewest hops, Dijkstra for weighted shortest paths, topological sort for dependencies."

[5, 2, 9, 1, 7, 3] [5, 2, 9] [1, 7, 3] [2, 5, 9] sorted [1, 3, 7] sorted [1, 2, 3, 5, 7, 9] merge split log n times · merge n work each level → O(n log n) Binary search: sorted data, halve the range [1 3 5 7 9 11 13] find 11 → mid 7 → go right → mid 11 ✔ (3 steps for 7 items) Sorting cheat sheet merge O(n log n) stable · quick O(n log n) avg, O(n²) worst · heap O(n log n) insertion O(n²) but great for tiny/nearly-sorted · Python's sorted() = Timsort
PLATE 7 — Divide the problem in half, and you get a logarithm.
Chapter 7 · Sorting & searching

Divide and conquer

def merge_sort(xs):
    if len(xs) <= 1: return xs
    mid = len(xs) // 2
    a, b = merge_sort(xs[:mid]), merge_sort(xs[mid:])
    out, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]: out.append(a[i]); i += 1      # <= keeps it stable
        else:            out.append(b[j]); j += 1
    return out + a[i:] + b[j:]

def binary_search(xs, target):                       # O(log n), xs must be sorted
    lo, hi = 0, len(xs) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if xs[mid] == target: return mid
        if xs[mid] < target: lo = mid + 1
        else: hi = mid - 1
    return -1

import bisect
bisect.bisect_left([1, 3, 5, 7], 5)                  # library version → 2

people = [("Ama", 31), ("Kofi", 27), ("Esi", 31)]
sorted(people, key=lambda p: (-p[1], p[0]))          # by age desc, then name
stable sort
equal items keep their original order; handy for multi-key sorts
binary search on the answer
when "is x feasible?" flips from no to yes, search x's range in O(log range) checks
Say it like a pro

"Sort first, then binary search or sweep. The sort dominates at O(n log n)."

f(5) f(4) f(3) f(3) f(2) f(2) f(1) f(3) and f(2) are computed again and again → O(2ⁿ) Dynamic programming = remember subproblem answers 1 · define the state ("best answer for the first i items") 2 · write the recurrence (how a state uses smaller states) 3 · base cases · 4 · compute in order (or memoize) → O(states × transitions) greedy: take the locally best choice, when that is provably enough
PLATE 8 — Don't solve the same small problem twice.
Chapter 8 · Dynamic programming & greedy

Trade memory for repeated work

from functools import cache

@cache                                   # memoization in one line
def fib(n):                              # O(n) instead of O(2ⁿ)
    return n if n < 2 else fib(n - 1) + fib(n - 2)

def coin_change(coins, amount):          # fewest coins to make `amount`. O(amount × coins)
    INF = float("inf")
    dp = [0] + [INF] * amount            # dp[a] = fewest coins for amount a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a: dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != INF else -1
coin_change([1, 5, 10, 25], 63)          # 6  (25+25+10+1+1+1)

def lcs(a, b):                           # longest common subsequence. O(len(a) × len(b))
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            dp[i][j] = dp[i-1][j-1] + 1 if a[i-1] == b[j-1] else max(dp[i-1][j], dp[i][j-1])
    return dp[-1][-1]

def max_meetings(intervals):             # greedy: always take the one that ends earliest
    end, count = float("-inf"), 0
    for s, e in sorted(intervals, key=lambda x: x[1]):
        if s >= end: count += 1; end = e
    return count
top-down vs bottom-up
memoized recursion vs filling a table; same idea
greedy caution
coin change with arbitrary coins is not greedy; prove it or use DP
backtracking
try, recurse, undo: permutations, N-Queens, Sudoku; prune early
Say it like a pro

"Overlapping subproblems and optimal substructure, so DP: state, recurrence, base case."

sorted / search→ binary search · two pointers contiguous range→ sliding window · prefix sums seen before / count→ hash map / set next greater / matching→ stack top-k / min-max stream→ heap shortest / connected→ BFS · DFS · Dijkstra best of many choices→ DP · greedy · backtracking
PLATE 9 — Most problems are a known pattern in disguise. Learn to spot the clue.
Chapter 9 · Solving problems

A routine you can repeat

  1. Restate the problem and its constraints. How big is n? Sorted? Duplicates? Negatives?
  2. Work a small example by hand, including an edge case (empty, one item, all equal).
  3. Brute force first and state its Big-O. A correct slow answer beats a wrong fast one.
  4. Find the bottleneck: what repeated work can a hash map, sort, heap, or pointer remove?
  5. Code it cleanly, then test your examples and edge cases and state time and space.
# a tiny test harness
def check(fn, cases):
    for args, expected in cases:
        got = fn(*args)
        print("ok " if got == expected else "FAIL", fn.__name__, args, "→", got)
check(two_sum, [(([2, 7, 11, 15], 9), (0, 1)), (([3, 3], 6), (0, 1))])
practice
NeetCode 150 · LeetCode (easy → medium) · Advent of Code · Project Euler
read next
"Grokking Algorithms" (gentle) · "Introduction to Algorithms" (CLRS) · "The Algorithm Design Manual"
habit
after each problem, write the pattern name and the one clue that revealed it
Say it like a pro

"Brute force first, then I remove the repeated work with the right structure and state the complexity."