Comparison sorts can’t beat Ω(n log n): the decision tree has n! leaves, and log2(n!) is Θ(n log n).
Python’s sorted and Java’s object sorts use Timsort; Java’s primitive arrays use dual-pivot quicksort. A random pivot makes quicksort’s worst case unlikely.
Binary search
def lower_bound(a, target): # first index with a[i] >= target lo, hi = 0, len(a) # search space is [lo, hi) while lo < hi: mid = (lo + hi) // 2 if a[mid] < target: lo = mid + 1 # answer is right of mid else: hi = mid # mid might be the answer return lo # len(a) if every item is smaller
python
Found? i < len(a) and a[i] == target. First index > target: test <= instead (bisect_right). Last index ≤ t: bisect_right(a, t) - 1. Count of t: bisect_right - bisect_left.
Rotated sorted array: compare a[mid] with a[hi] to find the sorted half, then check if the target lies in it.
Binary search on the answer when feasibility is monotone (“smallest speed or capacity that works”):
def first_true(lo, hi, ok): # smallest x in [lo, hi] with ok(x) while lo < hi: # ok must be monotone: F..F T..T mid = (lo + hi) // 2 if ok(mid): hi = mid else: lo = mid + 1 return lo # hi if ok is never true
python
Built in: bisect.bisect_left, bisect_right, insort (key= since 3.10).
contiguous subarray/substring, “longest with at most k”
longest substring without repeats
Prefix sums
range sums, “subarray sums to k” (+ hash map)
subarray sum equals k
Fast / slow pointers
cycles, middle of a list, O(1) space
linked list cycle
Monotonic stack
next greater/smaller element, spans
daily temperatures, histogram
Intervals
overlapping ranges: sort by start, merge
merge intervals, meeting rooms
Top-K with a heap
k largest / most frequent, streams
kth largest, merge k lists
BFS
shortest path unweighted, levels, grids
rotting oranges, word ladder
DFS
connectivity, islands, paths, trees
number of islands, clone graph
Topological sort
prerequisites, build order
course schedule
Union-find
dynamic connectivity, grouping
redundant connection
Backtracking
“all” subsets / permutations, constraints
N-Queens, word search
Dynamic programming
count ways, min/max cost, overlapping subproblems
coin change, LIS, LCS
Greedy
a local choice provably stays optimal
interval scheduling, jump game
Binary search on answer
“minimize the maximum”, monotone check
Koko bananas, ship in D days
Bit manipulation
XOR cancels pairs, masks, powers of two
single number, counting bits
Bits: x & (x - 1) clears the lowest set bit; x & -x isolates it; x > 0 and x & (x - 1) == 0 tests a power of two; (x >> k) & 1 reads bit k; a ^ a == 0; x.bit_count() (3.10); for mask in range(1 << n) enumerates subsets.
Top-K: a min-heap capped at size k leaves the kth largest at heap[0], in O(n log k); or heapq.nlargest(k, nums).
Templates: windows & backtracking
def min_window_sum(nums, target): # shortest subarray with sum >= target left = total = 0 # (all nums positive) best = float("inf") for right, x in enumerate(nums): total += x # grow the window while total >= target: # valid: shrink from the left best = min(best, right - left + 1) total -= nums[left] left += 1 return 0 if best == float("inf") else best
python
def subsets(nums): res, path = [], [] def backtrack(start): res.append(path[:]) # record a COPY of the current choice for i in range(start, len(nums)): path.append(nums[i]) # choose backtrack(i + 1) # explore path.pop() # un-choose backtrack(0) return res # 2^n subsets
python
Each index enters and leaves the window once: O(n). Backtracking prunes as soon as a partial choice can’t succeed.
Templates: BFS, DFS & topo sort
from collections import dequedef bfs(graph, start): # graph: {node: [neighbors]} dist = {start: 0} queue = deque([start]) while queue: node = queue.popleft() for nxt in graph[node]: if nxt not in dist: # mark on enqueue, not on dequeue dist[nxt] = dist[node] + 1 queue.append(nxt) return dist # fewest edges to each reachable node
python
def num_islands(grid): # grid of "1"/"0"; mutated in place if not grid: return 0 rows, cols = len(grid), len(grid[0]) def sink(r, c): # DFS flood fill if 0 <= r < rows and 0 <= c < cols and grid[r][c] == "1": grid[r][c] = "0" # mark visited for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): sink(r + dr, c + dc) return 1 return 0 return sum(sink(r, c) for r in range(rows) for c in range(cols))
python
def topo_sort(n, edges): # Kahn's algorithm; (u, v): u before v graph, indeg = [[] for _ in range(n)], [0] * n for u, v in edges: graph[u].append(v); indeg[v] += 1 queue = deque(i for i in range(n) if indeg[i] == 0) order = [] while queue: u = queue.popleft(); order.append(u) for v in graph[u]: indeg[v] -= 1 if indeg[v] == 0: queue.append(v) return order if len(order) == n else [] # [] means a cycle
python
Multi-source BFS (rotting oranges): seed the queue with every source at distance 0.
Graph algorithms
Algorithm
Solves
Time
Notes
BFS
shortest path, unweighted
O(V+E)
queue
DFS
reachability, components, cycles
O(V+E)
stack or recursion
Topological sort
ordering a DAG
O(V+E)
Kahn or DFS post-order
Dijkstra
single source, weights ≥ 0
O((V+E) log V), binary heap
wrong with negative edges
Bellman-Ford
single source, negative weights
O(V·E)
V-1 rounds; a Vth improvement means a negative cycle
Floyd-Warshall
all pairs
O(V^3) time, O(V^2) space
small V
Kruskal
minimum spanning tree
O(E log E)
sorted edges + union-find
Prim
minimum spanning tree
O(E log V), binary heap
grows one tree
import heapqdef dijkstra(graph, src): # graph: {u: [(v, w), ...]}, w >= 0 dist, heap = {src: 0}, [(0, src)] while heap: d, u = heapq.heappop(heap) if d > dist[u]: continue # stale entry, skip for v, w in graph[u]: nd = d + w if nd < dist.get(v, float("inf")): dist[v] = nd heapq.heappush(heap, (nd, v)) return dist
python
parent, size = list(range(n)), [1] * ndef find(x): while parent[x] != x: parent[x] = parent[parent[x]] # path halving x = parent[x] return xdef union(a, b): # False if already connected ra, rb = find(a), find(b) if ra == rb: return False if size[ra] < size[rb]: ra, rb = rb, ra # union by size parent[rb] = ra; size[ra] += size[rb] return True
python
Dynamic programming
State: what identifies a subproblem, e.g. dp[i] for the first i items, dp[i][j] for prefixes a[:i] and b[:j].
Transition: combine smaller states, one term per choice (take or skip, which coin).
Base cases: the smallest states (empty prefix, amount 0).
Order: dependencies first; memoization does it for you, tabulation loops upward.
Answer & space: locate the answer; keep one row if that’s all the transition reads.
Time = states × work per state. DP needs overlapping subproblems and optimal substructure.
from functools import cachedef coin_change(coins, amount): # fewest coins, -1 if impossible @cache def best(rem): # state: amount still to pay if rem == 0: return 0 # base case if rem < 0: return float("inf") return 1 + min(best(rem - c) for c in coins) # transition ans = best(amount) return -1 if ans == float("inf") else ans
python
def coin_change(coins, amount): # bottom-up: no recursion depth limit dp = [0] + [float("inf")] * amount # dp[a] = fewest coins that make a for a in range(1, amount + 1): # order: smaller amounts first for c in coins: if c <= a: dp[a] = min(dp[a], dp[a - c] + 1) return -1 if dp[amount] == float("inf") else dp[amount]
python
Problem
State
Transition
Time
Climbing stairs
dp[i] ways to step i
dp[i-1] + dp[i-2]
O(n)
House robber
dp[i] best of first i houses
max(dp[i-1], dp[i-2] + a[i-1])
O(n)
0/1 knapsack
dp[i][w]
max(skip, take + value)
O(n·W)
LIS
dp[i] longest ending at i
max(dp[j] + 1), j < i, a[j] < a[i]
O(n^2); O(n log n) with bisect
LCS / edit distance
dp[i][j] two prefixes
diagonal on match, else best neighbor
O(m·n)
Interval DP
dp[i][j] a range
best split point k
O(n^3)
Python toolkit for DSA
Need
Use
Watch out
Stack
list.append / pop()
pop(0) is O(n)
Queue
deque.append / popleft()
middle indexing is O(n)
Min-heap
heapq.heappush, heappop, heapify
max-heap: push -x (3.14 adds heappush_max etc.)
Counting
Counter, defaultdict(list)
most_common(k) for top-k
Sorted search
bisect_left, bisect_right, insort
insort is O(n)
Memoization
@functools.cache
hashable arguments (tuples, not lists)
Ordered map
none in the stdlib
sorted list + bisect, or third-party sortedcontainers
BFS vs DFS? Shortest unweighted paths but stores whole levels vs less memory, suits paths, cycles, topological order.
Dijkstra vs Bellman-Ford? Faster, non-negative weights only vs slower, handles negative weights and detects negative cycles.
Heap vs balanced BST? O(1) min, no ordered iteration vs O(log n) everything plus sorted order and range queries.
Memoization vs tabulation? Top-down recursion with a cache vs bottom-up loops (no recursion limit, easy space savings).
DP vs greedy? DP tries every choice via subproblems; greedy commits to one and needs a proof (exchange argument).
Cycle in a linked list? Floyd’s fast and slow pointers meet inside it; O(1) space.
Cycle in a graph? Undirected: union-find or DFS ignoring the parent edge. Directed: three-color DFS, or Kahn’s leaving nodes unprocessed.
Why is comparison sorting Ω(n log n)? log2(n!) comparisons are needed to tell n! orderings apart.
Gotchas & traps
Off-by-one: choose [lo, hi) with lo < hi or [lo, hi] with lo <= hi and keep the invariant. With lo = mid, use (lo + hi + 1) // 2 or the loop never ends.
Integer overflow (Java, C++; Python ints don’t overflow): (lo + hi) / 2 can overflow, so write lo + (hi - lo) / 2; keep sums and products in long.
Recursion limit: CPython defaults to 1000 frames, so deep DFS or memoization raises RecursionError. Use an explicit stack or bottom-up DP; sys.setrecursionlimit can still crash the process.
Mutable defaults: def dfs(node, path=[]) shares one list across calls; [[0] * m] * n shares one row.
Backtracking must record path[:], not path.
Mark BFS nodes visited on enqueue, or they’re queued repeatedly.
heapq compares whole tuples: a priority tie falls through to items that may not support <. Push (priority, counter, item).
Always test empty input, one element, all duplicates and the maximum size.