Data structures and algorithms: A practical reference

A practical reference covering the core data structures and common algorithm patterns, from arrays and binary search to graph traversal and dynamic programming.

Contents: Complexity · Core structures · Search and sorting · Array patterns · Graphs · Trees · Heaps · Greedy algorithms · Backtracking · Dynamic programming · Combinatorics · References

Complexity

Input constraints can suggest which algorithms are worth trying. Treat these ranges as rough clues, not hard limits or runtime guarantees.

The subset row assumes constant work per subset. Copying all elements of every subset instead takes O(n * 2^n) total work.

Use the table to narrow the search, not determine the solution. For example, at n = 10^5, consider sorting in O(n log n) or a linear scan before trying every pair. The problem still decides which approach is correct. A small input does not require a slow algorithm, and a large input does not automatically imply binary search.

The O(n) row allows n = 10^8 as a possibility, not a promise. Big-O describes growth, not seconds. Check the time limit, language, work per item, and memory use rather than assuming that many Python iterations will fit. For the final row, n may describe a number or search range. Reading n separate input items already takes linear work.

Unless stated otherwise, the bounds below treat fixed-size arithmetic as constant time. Python’s arbitrary-size integers cost more as their digit counts grow.

Core data structures

Choose a structure based on the operations you need, not just what it stores.

Python lists are arrays of references, not linked lists. Repeatedly using pop(0) to process a queue shifts the remaining elements and can turn a linear traversal into quadratic work.

For a singly linked list, deleting a node usually requires its predecessor. A doubly linked list stores both directions but uses more memory. Neither gives constant-time access to the middle.

A stack is a natural fit for undo history, bracket matching, and iterative depth-first search. A queue fits work waiting to be processed and breadth-first search. A dictionary fits counts, caches, and mapping an item to its last position.

Search and sorting

Binary search

Binary search repeatedly discards half of a sorted search range. Keep a precise invariant instead of guessing how to move the endpoints.

This version finds the first index whose value is at least the target. Its search interval is half-open, [left, right), and it returns the list length if every value is smaller.

def lower_bound(values, target):
    left, right = 0, len(values)
    while left < right:
        middle = (left + right) // 2
        if values[middle] < target:
            left = middle + 1
        else:
            right = middle
    return left

It takes O(log n) comparisons and O(1) extra space. The input must already be sorted.

Using Python’s bisect. bisect_left(values, target) returns the first position whose value is at least the target, just like lower_bound above. bisect_right(values, target) returns the first position whose value is greater than the target. Both return len(values) if no such position exists, and neither changes the list.

from bisect import bisect_left, bisect_right, insort

values = [1, 3, 3, 5, 8, 12]
target = 3
left = bisect_left(values, target)
right = bisect_right(values, target)
index = left if left < len(values) and values[left] == target else None
count = right - left

insort(values, 4)

Here left = 1, right = 3, index = 1, and count = 2. The matching values occupy [left, right). If the target is absent, both boundaries are the same, count is zero, and index is None. Check the boundary and equality before treating an insertion position as a match.

insort(values, 4) inserts in place, leaving [1, 3, 3, 4, 5, 8, 12]. By default, insort inserts after existing equal values. Use insort_left to insert before them. Finding a boundary takes O(log n) comparisons, but insertion takes O(n) overall because the list may need to shift elements.

The same pattern can search a monotonic condition, such as whether a proposed capacity is large enough. It does not work when the condition flips unpredictably between true and false.

Binary search narrows the interval. For [1, 3, 3, 5, 8, 12] and target 3, the first match is at index 1, not index 2. All indices are zero-based.

flowchart TD
    accTitle: Lower bound search for 3
    accDescr: The half-open interval shrinks from zero through six to zero through three, then zero through one. Since the value at index zero is smaller than three, left becomes one and the search ends.
    A["Range [0, 6)<br/>middle = 3, value = 5"]
    B["Range [0, 3)<br/>middle = 1, value = 3"]
    C["Range [0, 1)<br/>middle = 0, value = 1"]
    D["left = right = 1<br/>Return index 1"]
    A -->|"5 >= 3: right = 3"| B
    B -->|"3 >= 3: right = 1"| C
    C -->|"1 < 3: left = 1"| D

Sorting

Stability means equal keys retain their original order. Use sorted(values) for a new list or values.sort() to modify a list. In application code, prefer those maintained implementations.

For understanding divide and conquer, this merge sort splits the input, sorts each half, and merges the two ordered results:

def merge_sort(values):
    if len(values) < 2:
        return list(values)
    middle = len(values) // 2
    left = merge_sort(values[:middle])
    right = merge_sort(values[middle:])
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

Taking from the left on equality preserves stability. This implementation uses O(n) peak auxiliary storage, including its slices and merged lists.

Merge sort splits, then combines. Single-element lists are already sorted. Each merge compares the next unused value from its two inputs.

flowchart TD
    accTitle: Splitting and merging four values
    accDescr: Split four, one, three, two into pairs and then single values. Merge four and one into one, four. Merge three and two into two, three. The final merge produces one, two, three, four.
    A["[4, 1, 3, 2]"] --> B["[4, 1]"]
    A --> C["[3, 2]"]
    B --> D["[4]"]
    B --> E["[1]"]
    C --> F["[3]"]
    C --> G["[2]"]
    D --> H["[1, 4]"]
    E --> H
    F --> I["[2, 3]"]
    G --> I
    H --> J["[1, 2, 3, 4]"]
    I --> J

Array patterns

Two pointers can avoid comparing every pair when the input has useful order. In a sorted array, if the sum of the smallest and largest remaining values is too small, move the left pointer right. If it is too large, move the right pointer left.

Sliding windows maintain information about a contiguous range while moving its endpoints. The example below finds the length of the longest substring without repeated characters. Each endpoint only moves forward.

Prefix sums trade preprocessing and storage for fast range queries. Store a leading zero, then each running total. The sum over the half-open range [left, right) is prefix[right] - prefix[left].

def two_sum_sorted(values, target):
    left, right = 0, len(values) - 1
    while left < right:
        total = values[left] + values[right]
        if total == target:
            return left, right
        if total < target:
            left += 1
        else:
            right -= 1
    return None


def longest_unique_substring(text):
    last_seen = {}
    left = best = 0
    for right, character in enumerate(text):
        if character in last_seen:
            left = max(left, last_seen[character] + 1)
        last_seen[character] = right
        best = max(best, right - left + 1)
    return best


def prefix_sums(values):
    prefix = [0]
    for value in values:
        prefix.append(prefix[-1] + value)
    return prefix

Two-sum here takes O(n) time and O(1) extra space, returning two distinct indices or None. The substring algorithm takes expected O(n) time and up to O(n) dictionary space. Prefix sums take O(n) preprocessing time and space, followed by O(1) queries for valid endpoints.

A sliding window is not a universal replacement for nested loops. For example, moving one endpoint based on a running sum may rely on all values being nonnegative. Negative values can break that reasoning.

Prefix sums remove the part before the range. The query [1, 3) includes indices 1 and 2, so its answer is 4 + 1 = 5. Subtracting the two prefix totals gives the same result.

flowchart TD
    accTitle: A range sum from two prefix totals
    accDescr: Values two, four, one, three produce prefix totals zero, two, six, seven, ten. The sum over indices one through two is prefix three minus prefix one, or seven minus two, which is five.
    V["Values: 2, 4, 1, 3"] --> P["Prefix totals: 0, 2, 6, 7, 10"]
    P --> R["prefix[3] = 7"]
    P --> L["prefix[1] = 2"]
    R --> S["Range sum = 7 - 2 = 5"]
    L --> S

Graphs

The Python examples are self-contained within each section. Directed graph edges (u, v) point from u to v. In topological sorting, that means u must come before v.

Topological sorting

A topological order puts each vertex before all vertices it points to. It exists only for a directed acyclic graph, or DAG. Vertices here are integers from 0 through n - 1.

Dependencies form a partial order. Here 0 must precede both 1 and 2, and both must precede 3. The orders [0, 1, 2, 3] and [0, 2, 1, 3] are both valid.

flowchart TD
    accTitle: A dependency graph with two valid orders
    accDescr: Vertex zero points to vertices one and two. Vertices one and two both point to vertex three. There is no edge ordering one relative to two.
    A(("0")) --> B(("1"))
    A --> C(("2"))
    B --> D(("3"))
    C --> D

Both implementations use this helper to build adjacency lists and count incoming edges:

def build_graph(n, edges):
    if n < 0:
        raise ValueError("The vertex count must be nonnegative.")
    adjacency = [[] for _ in range(n)]
    indegree = [0] * n
    for u, v in edges:
        if not (0 <= u < n and 0 <= v < n):
            raise ValueError("An edge contains an out-of-range vertex.")
        adjacency[u].append(v)
        indegree[v] += 1
    return adjacency, indegree

Depth-first search (DFS). Visit a vertex’s outgoing neighbors before adding it to the result. That produces reverse topological order, so reverse the list at the end. Three states distinguish an unseen vertex, a vertex on the active recursion path, and a finished vertex. An edge back to an active vertex reveals a cycle.

def topological_sort_dfs(n, edges):
    adjacency, _ = build_graph(n, edges)
    state = [0] * n
    postorder = []

    def visit(u):
        if state[u] == 1:
            raise ValueError("The graph contains a directed cycle.")
        if state[u] == 2:
            return
        state[u] = 1
        for v in adjacency[u]:
            visit(v)
        state[u] = 2
        postorder.append(u)

    for u in range(n):
        if state[u] == 0:
            visit(u)
    return postorder[::-1]

Kahn’s algorithm. Put every vertex with zero incoming edges into a queue. Remove one, append it to the order, and decrement its neighbors’ incoming-edge counts. If fewer than n vertices are processed, a cycle remains.

from collections import deque


def topological_sort_kahn(n, edges):
    adjacency, indegree = build_graph(n, edges)
    ready = deque(u for u in range(n) if indegree[u] == 0)
    order = []

    while ready:
        u = ready.popleft()
        order.append(u)
        for v in adjacency[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                ready.append(v)

    if len(order) != n:
        raise ValueError("The graph contains a directed cycle.")
    return order

Both take O(V + E) time and O(V + E) total space, including the graph. They handle disconnected graphs and return [] for an empty graph. Cycles raise an error rather than returning a misleading order. Multiple valid orders may exist. For long dependency chains, prefer Kahn’s algorithm to avoid Python’s recursion limit.

Breadth-first and depth-first traversal

Breadth-first search (BFS) visits vertices in layers. In an unweighted graph, the first visit gives the shortest distance in number of edges. Depth-first search (DFS) follows a path before backtracking and is useful for reachability and structural checks.

In the dependency diagram above, BFS from 0 reaches 1 and 2 at distance 1 edge, then 3 at distance 2 edges. DFS explores one branch before the other. Traversal order and topological order answer different questions, even when they happen to agree on a small example.

These versions use the earlier build_graph helper. They follow directed edges. For an undirected graph, include both (u, v) and (v, u).

def shortest_unweighted_paths(n, edges, start):
    adjacency, _ = build_graph(n, edges)
    if not 0 <= start < n:
        raise ValueError("The start vertex is out of range.")
    distance = [-1] * n
    parent = [None] * n
    distance[start] = 0
    queue = deque([start])
    while queue:
        u = queue.popleft()
        for v in adjacency[u]:
            if distance[v] == -1:
                distance[v] = distance[u] + 1
                parent[v] = u
                queue.append(v)
    return distance, parent


def depth_first_order(n, edges, start):
    adjacency, _ = build_graph(n, edges)
    if not 0 <= start < n:
        raise ValueError("The start vertex is out of range.")
    visited = {start}
    stack = [start]
    order = []
    while stack:
        u = stack.pop()
        order.append(u)
        for v in adjacency[u]:
            if v not in visited:
                visited.add(v)
                stack.append(v)
    return order

Both take O(V + E) time including graph construction. Marking vertices when queued or stacked avoids repeatedly adding the same vertex. BFS returns -1 for unreachable vertices. Following its parent pointers back from a reachable target reconstructs a shortest path. This iterative DFS gives a reachability order, not the finishing times needed by the topological-sort implementation.

Shortest paths with weights

BFS minimizes edge count, not total weight. For nonnegative edge weights, use Dijkstra’s algorithm: repeatedly expand the smallest known distance and relax its outgoing edges.

from heapq import heappop, heappush
from math import inf, isfinite


def dijkstra(n, edges, start):
    if not 0 <= start < n:
        raise ValueError("The start vertex is out of range.")
    adjacency = [[] for _ in range(n)]
    for u, v, weight in edges:
        if not (0 <= u < n and 0 <= v < n):
            raise ValueError("An edge contains an out-of-range vertex.")
        if weight < 0 or (not isinstance(weight, int) and not isfinite(weight)):
            raise ValueError("Dijkstra requires finite, nonnegative weights.")
        adjacency[u].append((v, weight))

    distance = [inf] * n
    distance[start] = 0
    queue = [(0, start)]
    while queue:
        cost, u = heappop(queue)
        if cost != distance[u]:
            continue
        for v, weight in adjacency[u]:
            candidate = cost + weight
            if candidate < distance[v]:
                distance[v] = candidate
                heappush(queue, (candidate, v))
    return distance

The heap may hold an older, worse distance for a vertex. Skipping those stale entries is essential. Unreachable vertices keep infinity. This version uses O(V + E) space and O((V + E) log(V + E)) time with its potentially repeated heap entries.

Dijkstra is not valid for negative weights. Bellman-Ford handles negative edges in O(VE) time and can detect a reachable negative cycle. Floyd-Warshall finds all-pairs distances in O(V^3) time and O(V^2) space. Choose based on the graph size and the question being asked.

Fewest edges is not always lowest cost. Edge labels below are costs in arbitrary units. BFS prefers the one-edge route from 0 to 1, but Dijkstra finds 0 → 2 → 1 with total cost 2, rather than 5.

flowchart LR
    accTitle: Weighted paths from zero to one
    accDescr: The direct edge from zero to one costs five units. Going from zero to two and then to one costs one plus one, or two units, despite using more edges.
    A(("0")) -->|"5"| B(("1"))
    A -->|"1"| C(("2"))
    C -->|"1"| B

Union-find

Union-find tracks which items belong to the same connected component. It is useful when components are repeatedly joined and queried, such as in Kruskal’s minimum spanning tree algorithm.

This version uses union by size, attaching the smaller component to the larger one. Path compression shortens future searches for a component’s representative.

Shorten a parent chain. Arrows inside each box point from an item to its parent, not along the original graph’s edges. In this four-item component, find(0) skips parent 1 and points 0 directly at representative 3. Component membership does not change.

flowchart TD
    accTitle: Union-find before and after finding zero
    accDescr: Before the lookup, zero points to one, one points to representative three, and two points to three. After finding zero, zero also points directly to three.
    subgraph Before["Before find(0)"]
        direction BT
        B0["0"] --> B1["1"] --> B3["3: representative"]
        B2["2"] --> B3
    end
    subgraph After["After find(0)"]
        direction BT
        A0["0"] --> A3["3: representative"]
        A1["1"] --> A3
        A2["2"] --> A3
    end
    Before -->|"find(0)"| After

In Kruskal’s algorithm, sort an undirected graph’s edges by weight and accept an edge only when it joins different components. This builds a minimum spanning tree, or a minimum spanning forest if the graph is disconnected, in O(E log E) time dominated by sorting. A minimum spanning tree minimizes the total connecting-edge weight, not the distance from one source to every vertex.

class UnionFind:
    def __init__(self, n):
        if n < 0:
            raise ValueError("The item count must be nonnegative.")
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, u):
        if not 0 <= u < len(self.parent):
            raise ValueError("The item index is out of range.")
        while self.parent[u] != u:
            self.parent[u] = self.parent[self.parent[u]]
            u = self.parent[u]
        return u

    def union(self, u, v):
        u, v = self.find(u), self.find(v)
        if u == v:
            return False
        if self.size[u] < self.size[v]:
            u, v = v, u
        self.parent[v] = u
        self.size[u] += self.size[v]
        return True

find(u) == find(v) tests connectivity. union returns whether two separate components were joined. Only a representative’s size entry is current.

Initialization takes O(n) time and space. With both optimizations, operations take amortized O(alpha(n)) time over a sequence, where alpha is the very slowly growing inverse Ackermann function. This is effectively near-constant for practical inputs, not a claim that every individual call takes constant time. See the longer union-find explanation.

Trees

Binary search trees and tries

A binary search tree maintains an ordering rule: smaller keys go to one side and larger keys to the other, with an explicit policy for duplicates. Inorder traversal produces sorted keys. Search, insertion, and deletion take O(h) for height h. A balanced tree keeps h = O(log n), while a chain-shaped tree can have h = O(n).

For binary-tree traversal, preorder visits the root before its children, inorder visits left subtree, root, then right subtree, and postorder visits children before the root. Each visits every node in O(n) time. Recursive depth-first traversal uses O(h) stack space. A queue-based level-order traversal instead needs space proportional to the tree’s widest level.

A trie stores keys along paths, often one character per edge. Searching or inserting a word of length L takes O(L) child lookups. It is useful for prefix queries, but the many nodes and child maps can use much more memory than a hash set. Constant-time child lookup assumes a suitable array or an expected constant-time hash map.

Lowest common ancestor

The lowest common ancestor of two nodes is the deepest node whose subtree contains both. A node counts as its own ancestor.

A shared subtree identifies the ancestor. For targets 1 and 3, the answer is 2, not 4. This example is also a binary search tree, with inorder traversal [1, 2, 3, 4, 6].

flowchart TD
    accTitle: Lowest common ancestor of one and three
    accDescr: Root four has children two and six. Node two has children one and three, so two is their lowest common ancestor.
    A["4"] --> B["2: lowest common ancestor"]
    A --> C["6"]
    B --> D["1: target"]
    B --> E["3: target"]

The following code works on a binary tree, not necessarily a binary search tree. It compares node identity rather than stored values, so duplicate values are fine. Two bits record whether each target has been found. The first subtree containing both targets supplies the answer.

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


def lowest_common_ancestor(root, p, q):
    answer = None

    def visit(node):
        nonlocal answer
        if node is None:
            return 0
        found = visit(node.left) | visit(node.right)
        if node is p:
            found |= 1
        if node is q:
            found |= 2
        if found == 3 and answer is None:
            answer = node
        return found

    visit(root)
    return answer

If either target is absent, the result is None. If p and q are the same node and it is in the tree, that node is returned. The traversal takes O(n) time and O(h) recursion space for tree height h. A highly unbalanced tree can exceed Python’s recursion limit, so use an iterative traversal for that case.

Heaps

A binary min-heap keeps its smallest value at the root. It is not a fully sorted list, so finding an arbitrary value is still linear.

Bottom-up heap construction is linear because most nodes are close to the leaves and need little or no downward movement.

from heapq import heapify, heappop, heappush

heap = [7, 1, 4]
heapify(heap)
heappush(heap, 3)
minimum = heappop(heap)
assert minimum == 1
assert heap[0] == 3

The heap is only locally ordered. Just before heappop in this example, the array is [1, 3, 4, 7]. Every parent is no larger than its children. The left subtree can still contain values larger than a value in the right subtree.

flowchart TD
    accTitle: A min-heap before removing its root
    accDescr: The minimum value one is at the root, with children three and four. Seven is a child of three. Removing the root returns one.
    A["1: minimum"] --> B["3"]
    A --> C["4"]
    B --> D["7"]

Check for an empty heap before reading or removing its minimum. The O(log n) removal bound applies to the root, not to finding and deleting any requested value. Python’s heapq does not provide an indexed arbitrary-delete operation.

Greedy algorithms

A greedy algorithm makes a local choice and never revisits it. The important part is proving that this choice cannot prevent an optimal answer.

To select the largest number of non-overlapping, positive-length intervals, take the interval that finishes earliest, then repeat with compatible intervals. Choosing the earliest finish leaves at least as much room for what follows as choosing any later finish.

def select_intervals(intervals):
    ordered = sorted(intervals, key=lambda interval: interval[1])
    selected = []
    for start, end in ordered:
        if start >= end:
            raise ValueError("Intervals must have positive length.")
        if not selected or start >= selected[-1][1]:
            selected.append((start, end))
    return selected

Sorting dominates at O(n log n) time, with O(n) space here. Endpoints may touch. This maximizes the count, not a sum of rewards. Weighted interval scheduling needs a different approach.

Backtracking

Backtracking explores a choice, recurses, and then undoes that choice. Use it when the answer space is manageable or when constraints let you prune large parts of the search.

This generator enumerates subsets by choosing which position comes next:

def subsets(values):
    chosen = []

    def visit(start):
        yield chosen.copy()
        for index in range(start, len(values)):
            chosen.append(values[index])
            yield from visit(index + 1)
            chosen.pop()

    yield from visit(0)

Copying the current choice prevents later mutations from changing an already yielded result. There are 2^n subsets and O(n * 2^n) total work to copy them. The recursion and current choice use O(n) auxiliary space, excluding results retained by the caller. Positions are distinct, so duplicate input values can produce equal-looking subsets.

A small subset search tree. For input ["A", "B"], the generator yields [], ["A"], ["A", "B"], then ["B"]. Returning from a child undoes its last choice before exploring another branch.

flowchart TD
    accTitle: Backtracking through the subsets of A and B
    accDescr: The empty choice branches to A and B. The A branch can also choose B, yielding A and B together. After returning from that branch, choices are undone before exploring B alone.
    E["[]"] -->|"Choose A"| A["[A]"]
    A -->|"Choose B"| AB["[A, B]"]
    E -->|"Choose B"| B["[B]"]

Dynamic programming

Dynamic programming reuses answers to overlapping subproblems. Define the state, transition, base case, and evaluation order before writing the loops.

For unlimited use of positive integer coin denominations, let best[t] be the fewest coins needed to make total t. The transition tries each possible last coin. best[0] = 0, and totals are evaluated from small to large.

def minimum_coins(coins, amount):
    coins = tuple(coins)
    if not isinstance(amount, int) or amount < 0:
        raise ValueError("The amount must be a nonnegative integer.")
    if any(not isinstance(coin, int) or coin <= 0 for coin in coins):
        raise ValueError("Coin denominations must be positive integers.")
    coins = sorted(set(coins))
    best = [amount + 1] * (amount + 1)
    best[0] = 0
    for total in range(1, amount + 1):
        for coin in coins:
            if coin > total:
                break
            best[total] = min(best[total], best[total - coin] + 1)
    return None if best[amount] > amount else best[amount]

For k distinct denominations and target A, the table takes O(Ak) time and O(A) space, after sorting the coins. This is pseudo-polynomial: runtime depends on the numeric amount, not just the number of digits used to write it. None means the target cannot be formed.

Greedily taking the largest coin does not always work. With denominations 1, 3, 4, amount 6 needs two threes, not 4 + 1 + 1. Top-down memoization is another way to express the same recurrence, but an iterative table avoids recursion-depth limits.

Reuse three smaller answers. To compute best[6], try each possible last coin. Each arrow adds one coin to an already solved total. The middle choice gives the fewest coins.

flowchart TD
    accTitle: Dynamic programming for a total of six
    accDescr: With coin denominations one, three, and four, best five is two coins, best three is one coin, and best two is two coins. Adding the last coin gives candidates three, two, and three coins. The minimum is two.
    A["best[5]<br/>2 coins"] -->|"Add coin 1"| D["3 coins"]
    B["best[3]<br/>1 coin"] -->|"Add coin 3"| E["2 coins"]
    C["best[2]<br/>2 coins"] -->|"Add coin 4"| F["3 coins"]
    D --> G["best[6]<br/>2 coins"]
    E --> G
    F --> G

Combinatorics

Permutations, combinations, and Pascal’s triangle

For 0 <= r <= n, the number of ordered selections is P(n, r) = n! / (n - r)!. The number of unordered selections is C(n, r) = n! / (r! * (n - r)!).

Python’s math.perm(n, r) and math.comb(n, r) compute these exactly. Do not assume that math.comb costs constant time or that it must explicitly calculate three factorials.

Row n of Pascal’s triangle is C(n, 0) through C(n, n), using zero-based row numbers. Rebuilding every preceding row takes O(n^2) additions. To generate just one row, use the recurrence C(n, k + 1) = C(n, k) * (n - k) / (k + 1):

def pascal_row(n):
    if n < 0:
        raise ValueError("The row index must be nonnegative.")
    row = [1]
    for k in range(n):
        row.append(row[-1] * (n - k) // (k + 1))
    return row


assert pascal_row(4) == [1, 4, 6, 4, 1]

This uses O(n) arithmetic steps and stores n + 1 integers. It is not linear in bit operations or bytes, because the coefficients themselves grow with n.

Many combination queries modulo a prime

For repeated queries, precompute factorials and inverse factorials modulo a fixed prime. An inverse lets multiplication undo a nonzero factor under modular arithmetic.

The table below uses the prime 1,000,000,007 and requires limit to be smaller than that prime. At or above the prime, the factorial becomes zero modulo the prime and has no inverse. This method cannot be used unchanged for those inputs.

def make_comb_mod(limit):
    modulus = 1_000_000_007
    if not 0 <= limit < modulus:
        raise ValueError("Require 0 <= limit < 1,000,000,007.")

    factorial = [1] * (limit + 1)
    for i in range(1, limit + 1):
        factorial[i] = factorial[i - 1] * i % modulus

    inverse_factorial = [1] * (limit + 1)
    inverse_factorial[limit] = pow(factorial[limit], -1, modulus)
    for i in range(limit, 0, -1):
        inverse_factorial[i - 1] = inverse_factorial[i] * i % modulus

    def comb_mod(n, r):
        if not 0 <= r <= n <= limit:
            raise ValueError("Require 0 <= r <= n <= the table limit.")
        return (
            factorial[n] * inverse_factorial[r] * inverse_factorial[n - r]
            % modulus
        )

    return comb_mod


comb_mod = make_comb_mod(100)
assert comb_mod(4, 2) == 6

Preprocessing uses O(limit) table work plus one modular inverse, and O(limit) space. Each query then uses a constant number of modular multiplications for this fixed modulus. The returned number is the combination count modulo the prime, not the full exact count.

References

1. Codeforces: How to determine the solution of a problem by looking at its constraints?. Input-size guidelines, example approaches, and discussion of their limits.