Data Structures and Algorithm Patterns

Complexity, core patterns with Python templates, graphs, dynamic programming, and the cues that point to each pattern.

Complexity Basics

Complexity	Max n in ~1 s	Typical source
O(log n)	Huge	Binary search
O(n)	10⁸	Single pass
O(n log n)	10⁶–10⁷	Sorting, heaps
O(n²)	10⁴	Nested loops
O(2ⁿ)	20–25	Subsets
O(n!)	10–11	Permutations

Space counts too: Recursion depth, hash maps, and DP tables all use memory.

Choosing a Pattern

Sorted input?
Contiguous range?
Pairs or counts?
Graph or grid?
Optimal substructure?

Ask in order: binary search → window → hash → BFS/DFS → DP

Cue	Pattern
Sorted array, find target or boundary	Binary search
Longest/shortest subarray with a condition	Sliding window
Pair or triplet sums in sorted data	Two pointers
Seen before, counts, complements	Hash map / set
Next greater or smaller element	Monotonic stack
Top k, running median, merge k lists	Heap
Shortest path, unweighted	BFS
Dependencies, ordering	Topological sort
Connectivity, merging groups	Union-find

Prefix Sums and Hashing

Python

prefix = [0]
for v in nums:
    prefix.append(prefix[-1] + v)
# sum(nums[l:r+1]) == prefix[r+1] - prefix[l]

def subarray_sum(nums, k):      # count sums == k
    seen, run, count = {0: 1}, 0, 0
    for v in nums:
        run += v
        count += seen.get(run - k, 0)
        seen[run] = seen.get(run, 0) + 1
    return count

Two-sum: Store each value's index; look up target - x in O(1).
Counting: collections.Counter for anagrams and frequency problems.

Two Pointers

Python

def two_sum_sorted(a, target):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        s = a[lo] + a[hi]
        if s == target:
            return lo, hi
        if s < target:
            lo += 1
        else:
            hi -= 1
    return None

Uses: Pair sums, removing duplicates in place, palindromes, merging sorted arrays.
Fast / slow pointers: Cycle detection and finding the middle of a linked list.

Sliding Window

Python

def longest_unique(s):
    last, left, best = {}, 0, 0
    for right, ch in enumerate(s):
        if last.get(ch, -1) >= left:
            left = last[ch] + 1
        last[ch] = right
        best = max(best, right - left + 1)
    return best

Invariant: Expand right; shrink left until the window is valid again.
Fixed size k: Add the new element, drop the one leaving, update the answer.

Binary Search

Python

def first_true(lo, hi, ok):     # ok is monotonic
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Search on the answer: Minimize capacity or speed when feasibility is monotonic.
bisect: bisect_left gives the first index with a[i] >= x.

Off-by-one traps

Pick one convention (half-open [lo, hi) here) and keep it. Mixing conventions causes infinite loops.

Stacks, Queues, Heaps

Python

def next_greater(nums):
    res, stack = [-1] * len(nums), []
    for i, v in enumerate(nums):
        while stack and nums[stack[-1]] < v:
            res[stack.pop()] = v
        stack.append(i)
    return res

import heapq
top_k = heapq.nlargest(k, nums)

Monotonic stack: Next greater element, histogram area, daily temperatures.
deque: O(1) at both ends; sliding-window maximum.
Heap: heapq is a min-heap; push -x for a max-heap.

Trees

Python

def max_depth(node):
    if not node:
        return 0
    return 1 + max(max_depth(node.left),
                   max_depth(node.right))

Preorder: Node, left, right; copy or serialize a tree.
Inorder: Left, node, right; a BST yields sorted order.
Postorder: Children first; subtree sizes and heights.
BST lookup: O(h); h = log n when balanced, n when skewed.

Graphs: BFS and DFS

Python

from collections import deque

def bfs(graph, start):
    dist = {start: 0}
    q = deque([start])
    while q:
        u = q.popleft()
        for v in graph[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

Representation: Adjacency list for sparse graphs; matrix for dense ones.
BFS: Shortest paths in unweighted graphs; level-order traversal.
DFS: Connected components, cycle detection, path enumeration.
Grids: Treat cells as nodes with 4 or 8 neighbors; mark visited on push.

Topological Sort

Python

def topo(n, edges):
    indeg, adj = [0] * n, [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else []  # cycle

Kahn's algorithm: Repeatedly remove nodes with in-degree 0; O(V + E).
Cycle check: Fewer than n nodes in the order means the graph has a cycle.
Uses: Build systems, course schedules, task pipelines.

Union-Find

Python

parent = list(range(n))

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]  # path halving
        x = parent[x]
    return x

def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb:
        return False
    parent[ra] = rb
    return True

Use for: Connected components, cycle detection in undirected graphs, Kruskal's MST.
Cost: Nearly O(1) amortized per operation with path compression and union by rank.

Shortest Paths and MST

Algorithm	Graph	Complexity
BFS	Unweighted	O(V + E)
Dijkstra	Non-negative weights	O(E log V)
Bellman–Ford	Negative edges allowed	O(V · E)
Floyd–Warshall	All pairs	O(V³)
Kruskal / Prim	Minimum spanning tree	O(E log V)

Dijkstra is wrong with negative edge weights. Use Bellman–Ford, which also detects negative cycles.

Backtracking

Python

def subsets(nums):
    res, path = [], []
    def dfs(i):
        if i == len(nums):
            res.append(path[:])
            return
        path.append(nums[i]); dfs(i + 1)   # take
        path.pop(); dfs(i + 1)             # skip
    dfs(0)
    return res

Template: Choose, recurse, un-choose.
Pruning: Stop early when a partial solution can't succeed.

Dynamic Programming

Define state
Write recurrence
Base cases
Iteration order
Optimize space

Python

def coin_change(coins, amount):
    dp = [0] + [float("inf")] * amount
    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] < float("inf") else -1

Signals: "Count the ways", "min/max cost", overlapping subproblems.
0/1 knapsack: Iterate capacity downwards so each item is used once.

Intervals and Greedy

Python

def merge(intervals):
    out = []
    for s, e in sorted(intervals):
        if out and s <= out[-1][1]:
            out[-1][1] = max(out[-1][1], e)
        else:
            out.append([s, e])
    return out

Sort first: By start to merge; by end to schedule the most non-overlapping intervals.
Greedy proof: Show an exchange argument, or fall back to DP.

Tries, Bits, Strings

Trie: Prefix search and autocomplete in O(length of the word).
x & (x − 1): Clears the lowest set bit; x is a power of two when the result is 0.
XOR: a ^ a = 0, which finds the single non-duplicated number.
Rolling hash: Rabin–Karp substring search in expected O(n + m).
KMP: Prefix-function substring search in O(n + m) worst case.

Interview Checklist

Restate the problem and confirm input sizes and edge cases.
Name a brute force and its complexity.
Match cues to a pattern and explain the improvement.
Code with clear names; handle empty and single-element inputs.
Walk through a small example and state the final complexity.

Say the invariant out loud ("the window always holds unique characters"). It guides both the code and the proof.