Patterns & Complexity Cheat Sheet
A reference page, not a problem: a step-by-step method for approaching any unseen problem (Fin-flavored or plain LeetCode), a catalog of the ~20 patterns this problem set draws from with what signals each one and where it shows up in this set, and a complexity table for the everyday Python operations you'll reach for while implementing any of them.
How to Approach Any Problem
- Restate it in your own words. Confirm the input/output types, the
constraint ranges (how large can
nget?), and whether edge cases — empty input, a single element, all-duplicate values — are actually in scope. Half of avoidable mistakes in this set come from skipping this and guessing at a signature. - Say the brute-force out loud, even if you won't code it. A nested loop or a full sort-then-scan almost always works; stating it first anchors correctness and makes the next step concrete.
- Ask what the brute-force repeats or recomputes. That repeated work is almost always exactly what a hashmap, a heap, a sliding window, or a DP table exists to eliminate. "I'm re-scanning the same range every time" → sliding window. "I'm re-sorting after every insert" → heap. "I'm re-solving the same subproblem" → memoize it.
- Match the constraint to a complexity budget before you commit to an approach — the table below kills most wrong turns.
- Write the interface before the logic. Every problem in this set is structured stub-first for exactly this reason — nail down the function signature and what a correct return value looks like, then fill in the body.
- Trace the given example by hand before you trust your code. Most
off-by-one and boundary bugs in this set (empty list,
k=0, ties, single-node graphs) surface the moment you actually walk through an example on paper. - After it works, ask if it can drop a factor of n. O(n²) → O(n log n) usually means "stop re-scanning, sort or heap once." O(n log n) → O(n) usually means "stop sorting, a hashmap or counting approach doesn't need order."
- State the final time and space complexity out loud. Interviewers expect it, and if you can't state it confidently, you likely haven't fully convinced yourself the algorithm is correct either.
n → Complexity Budget
These are the standard competitive-programming rules of thumb (roughly "10⁸ simple operations per second" in a fast language) — treat them as a sanity check, not a promise. Python's per-operation constant factor is much heavier than C++/Java, so in practice push every row's n down by 1-2 orders of magnitude when you're actually timing Python code; in an interview, nobody expects you to compute the exact cutoff — the point is recognizing "this needs to not be quadratic," not hitting an exact number.
| Typical n | Safe complexity | What that rules in / out | Example |
|---|---|---|---|
| n ≤ ~10–12 | O(n!) | Full permutation enumeration — try every ordering | Not used in this set — none of the 50 problems permute a full ordering (classic example elsewhere: brute-force traveling salesman) |
| n ≤ ~20–25 | O(2ⁿ) | Subset enumeration / bitmask DP — try every combination | Not directly present; the backtracking in #19/#25 is bounded by word/pattern length, not a raw n≤20 input size (classic example elsewhere: bitmask-DP TSP) |
| n ≤ ~500–1,000 | O(n²) or O(n³) | Nested loops, O(n·m) DP tables | #23 (edit distance), #26 (LCS), #27 (regex DP) — all fill an n×m table |
| n ≤ ~100,000 | O(n log n) | Need a sort, heap, or binary search somewhere — O(n²) will time out | #1, #2, #30, #38 — anything built on heapq or sorted() |
| n ≤ ~10⁶–10⁷ (tighter in Python) | O(n) | Single-pass with a hashmap / two-pointer / sliding-window | #15, #22, #44 (sliding window), #46 (prefix sum + hashmap) |
The Fin Framing, and How to See Through It
Every problem in this set wraps a classic pattern in support-ops or ML-infra language — "top-k KB passages by relevance score" is a top-k heap; "splitting a multi-question email" is string parsing with delimiters; "clustering near-duplicate tickets" is Union-Find. The first real task when you read an unfamiliar Fin-flavored (or any domain-flavored) question is to strip the business-logic dressing and name the underlying pattern out loud — "this is really just interval merging" or "this is really just BFS on an implicit graph." Getting stuck trying to model the literal business rules, instead of translating to the pattern first, is the single most common way these problems eat more than an hour.
The Confirmed / General Pattern badge on each problem page is about the scenario's truthfulness, not the algorithm — it tells you whether that specific framing is backed by something Fin has actually published, or is a plausible general-industry scenario built to motivate the pattern. Either way, the pattern and its complexity are the part that actually transfers to a real interview.
Pattern Catalog
Roughly in the order this set introduces them, grouped by color. Examples link back to problems in this set that use the pattern.
Heap / Top-K / Priority Queue
Recognize
"top-k", "k largest/smallest", "merge k sorted lists", "running median", "schedule/process by priority or deadline"
Approach
Bounded min-heap of size k for top-k-largest (evict the smallest when full); two heaps (max-heap for the lower half, min-heap for the upper half) for a running median;
heapq is min-heap only — negate values to emulate a max-heapComplexity
O(log k) per push/pop, O(n log k) to stream n items into a size-k heap; O(n) to
heapify an existing listBinary Search — on a Sorted Array, or on the Answer
Recognize
"sorted input", or a monotonic predicate — "find the smallest/largest X such that condition(X) holds" — even when nothing looks literally sorted
Approach
bisect for a literal sorted-array search; a manual lo/hi loop when binary-searching over a value range, halving the space each step based on which side of the predicate you land onComplexity
O(log n)
Sliding Window / Two Pointers
Recognize
"contiguous subarray/substring", "window of size k", "at most/exactly K distinct", any constraint that only depends on a moving contiguous range
Approach
Expand a right pointer; shrink a left pointer only when the window violates the constraint; maintain running state incrementally rather than recomputing per window
Complexity
O(n) time — each pointer moves forward at most n times total — O(k) or O(alphabet) space
Two-List Merge / Interleaving
Recognize
inputs are already sorted (or already ranked) and you need to combine them — "merge", "interleave", "blend two orderings"
Approach
Walk both inputs with independent pointers, always taking the "next needed" element from whichever side is due — never re-sort the combined result from scratch
Complexity
O(n) for a two-list merge; O(n log k) for a k-way merge via a heap of the k current fronts
Prefix Sum + Hashmap
Recognize
"count subarrays/ranges whose sum equals K", any "range aggregate" question over a fixed array
Approach
Running prefix sum as you scan once; store how many times each prefix-sum value has been seen; the count ending here with sum K is how many times
(current_sum - K) appeared beforeComplexity
O(n) time, O(n) space for the hashmap
Examples
Union-Find (Disjoint Set)
Recognize
"cluster/group related items", "connected components", "detect a cycle in an undirected graph", "is this a valid tree"
Approach
A parent array with
find() (path compression: point every visited node straight at the root on the way out) and union() (attach by rank/size to keep the tree flat)Complexity
Amortized O(α(n)) per operation — effectively O(1) in practice
Graph Traversal — BFS / DFS
Recognize
"shortest path in an unweighted graph" (BFS), "visit everything reachable", "clone/copy a graph", "count regions/islands", "shortest transformation sequence"
Approach
BFS with a queue (
collections.deque, not a list) guarantees shortest path in hop count; DFS with a stack or recursion for full exploration or backtracking-style searchComplexity
O(V + E) — every node and edge visited once
Topological Sort
Recognize
"X must happen before Y", "dependency ordering", "detect a cycle in a directed graph", "derive a total order from partial constraints"
Approach
Kahn's algorithm — repeatedly pull nodes with in-degree 0 — or DFS with post-order + reverse; a cycle shows up as "fewer nodes processed than exist"
Complexity
O(V + E)
Tree Traversal & Serialization
Recognize
binary/n-ary tree input, "serialize/deserialize", "clone/validate a tree structure"
Approach
Preorder DFS with explicit null markers makes serialization unambiguously reversible; reconstruction consumes the same token stream in the same order it was produced
Complexity
O(n)
Examples
Dynamic Programming
Recognize
"count the ways to...", "longest/shortest X satisfying Y", "can this be partitioned/segmented into...", overlapping subproblems
Approach
Define the state precisely, write the recurrence in terms of smaller states, nail the base cases, then fill bottom-up (or memoize top-down) in dependency order
Complexity
Usually O(states × transition cost) — O(n) for a 1D table, O(n·m) for a 2D table; often reducible to O(min dimension) space with a rolling array
Backtracking
Recognize
"find all X", "search a grid/graph for a path satisfying a constraint", "generate every valid combination"
Approach
Recursive explore; mark state as visited/used before recursing, always unmark it on the way back out; prune as early as a branch is provably invalid
Complexity
Exponential worst case (e.g. O(rows·cols·4^L) for a grid search), pruning keeps it far below that in practice
Divide & Conquer
Recognize
the problem naturally splits into independent halves whose solutions combine cheaply — "merge k sorted things", "median across two sorted arrays"
Approach
Recursively solve each half, then do a cheap combine step; the combine cost, multiplied across O(log n) recursion levels, sets the total complexity
Complexity
Governed by the recurrence — O(n log k) for k-way merge sort, O(log(min(m,n))) for the partition-search version of median-of-two-sorted-arrays
Greedy
Recognize
"minimum number of X to cover all Y", "schedule to minimize/maximize Z" — and the locally-best choice provably never hurts the global optimum
Approach
Sort by the key that makes the greedy choice obvious (often end time, or frequency), then make one linear pass taking the locally optimal action
Complexity
O(n log n), dominated by the sort
Intervals
Recognize
"merge overlapping ranges", "minimum rooms/agents for overlapping meetings", "does this interval conflict with that one"
Approach
Sort by start (for merging) or track starts/ends separately (for a "how many active at once" sweep, often with a heap of end times)
Complexity
O(n log n)
Sort + Sweep for Threshold Optimization
Recognize
"find the best cutoff/threshold that maximizes some score against labeled outcomes" — precision, recall, F1
Approach
Sort candidates by score descending; sweep once, maintaining running counts rather than recomputing the metric at every candidate threshold; group tied scores together
Complexity
O(n log n) — the sort dominates a single O(n) sweep
Trie (Prefix Tree)
Recognize
"prefix search", "autocomplete", "does any word in this dictionary start with..."
Approach
A tree of nested dicts, one level per character, with a marker at nodes that complete a real word
Complexity
O(L) per insert or search, where L is the word/prefix length
Examples
Design — Composing Structures for O(1)/O(log n) Ops
Recognize
"design a class supporting operations X, Y, Z each in O(1)/O(log n)" — a cache, a rate limiter, a ring
Approach
Pair a hashmap (O(1) lookup) with a structure that gives ordering or eviction cheaply — a doubly linked list for LRU recency, a deque for a sliding time window, a sorted structure for range queries
Complexity
Usually O(1) or O(log n) per operation by construction
Bit Manipulation
Recognize
"flags/feature sets encoded as a bitmask", "count set bits", "subset enumeration via bits"
Approach
& to test/intersect, | to set/union, ^ to toggle; Brian Kernighan's n &= n - 1 clears the lowest set bit, useful for popcountComplexity
O(1) per operation; O(set bits) for a Kernighan's-trick popcount loop, or O(1) via
int.bit_count() (3.10+)Examples
none currently in this set
Randomized Algorithms
Recognize
"streaming input of unknown/unbounded length, maintain a uniform sample", or "avoid a worst-case input pattern by not being deterministic"
Approach
Reservoir sampling (Algorithm R) for uniform sampling from a stream in one pass with O(k) memory; randomized pivot selection for quickselect to avoid adversarial O(n²) inputs
Complexity
Reservoir sampling: O(n) time, O(k) space, single pass. Quickselect: O(n) expected time
String / Text Parsing
Recognize
"extract structured pieces from a raw text blob" — splitting on delimiters or markers, stripping known boilerplate, matching against simple patterns
Approach
Careful line-by-line or regex-based scanning; the risk is almost always edge cases (empty input, no marker found) rather than the core logic
Complexity
O(n) for a single linear scan; watch for accidental O(n²) from string concatenation in a loop — see the complexity table below
Complexity Cheat Sheet
The everyday operations you reach for while implementing any of the above — this is the
part that's easy to get subtly wrong under interview pressure (e.g. reaching for
list.pop(0) without noticing it's O(n), silently turning an O(n) solution into
O(n²)).
list
| Operation | Time | Notes |
|---|---|---|
lst[i] | O(1) | direct index into a contiguous array |
lst.append(x) | O(1) amortized | occasional O(n) resize, averages out |
lst.pop() | O(1) | from the end |
lst.pop(0) / lst.insert(0, x) | O(n) | every remaining element shifts — use collections.deque instead if you need this often |
x in lst | O(n) | linear scan — use a set/dict if you'll check membership repeatedly |
lst.sort() / sorted(lst) | O(n log n) | Timsort; stable — equal elements keep their relative order, several problems in this set rely on that |
lst[a:b] (slicing) | O(b − a) | copies the sliced range |
min(lst) / max(lst) / sum(lst) | O(n) | full scan |
len(lst) | O(1) | length is tracked, not counted |
dict / set
| Operation | Time | Notes |
|---|---|---|
x in d / x in s | O(1) average | hash-table lookup — this is the "checking presence" operation; O(n) only in a pathological worst case, essentially never hit in practice |
d[k] = v / d.get(k) / del d[k] | O(1) average | |
s.add(x) / s.remove(x) | O(1) average | |
for k in d / for x in s | O(n) | full iteration |
set_a & set_b (intersection) | O(min(len(a), len(b))) | |
set_a | set_b (union) | O(len(a) + len(b)) | |
| building a set/dict from n items | O(n) | one hash + insert per item |
collections.deque
| Operation | Time | Notes |
|---|---|---|
dq.append(x) / dq.appendleft(x) | O(1) | |
dq.pop() / dq.popleft() | O(1) | exactly why BFS queues and monotonic-window problems use deque, not list |
dq[i] (random access) | O(n) | a doubly-linked list of blocks, not a contiguous array — don't index into a deque in a hot loop |
heapq
| Operation | Time | Notes |
|---|---|---|
heapq.heappush(heap, x) | O(log n) | |
heapq.heappop(heap) | O(log n) | |
heapq.heapify(lst) | O(n) | cheaper than n individual pushes (O(n log n)) — always heapify an existing list rather than pushing one at a time |
heapq.heapreplace(heap, x) | O(log n) | one sift-down; cheaper than a separate pop then push |
heapq.nlargest(k, it) / nsmallest | O(n log k) | |
heap[0] (peek min) | O(1) | the min is always at index 0; nothing else is guaranteed sorted |
bisect (binary search on a sorted list)
| Operation | Time | Notes |
|---|---|---|
bisect.bisect_left(lst, x) / bisect_right | O(log n) | finds the insertion point only, doesn't insert |
bisect.insort(lst, x) | O(n) | O(log n) to find the spot + O(n) to shift everything after it — the shift dominates |
string
| Operation | Time | Notes |
|---|---|---|
s[i] | O(1) | |
s + t | O(len(s) + len(t)) | doing this n times in a loop is O(n²) total — build a list and "".join(parts) instead, O(total length) |
x in s (substring search) | O(n·m) worst case | CPython uses a fast practical algorithm close to O(n+m) for typical inputs, but the worst case is still quadratic |
s.split() / s.split(sep) | O(n) | |
s[::-1] (reverse) | O(n) | creates a new string; strings are immutable in Python |
Union-Find / Graph / Sort
| Operation | Time | Notes |
|---|---|---|
find(x) / union(x, y) | amortized O(α(n)) ≈ O(1) | with path compression + union by rank; α = inverse Ackermann, effectively constant |
| BFS / DFS over a whole graph | O(V + E) | |
| Dijkstra with a binary heap | O((V + E) log V) | see #50 |
| Topological sort (Kahn's or DFS) | O(V + E) | |
sorted(iterable, key=...) | O(n log n) | Timsort, stable |
random.Random().randint(a, b) | O(1) |