DSA pattern lab 🐍
Most interview problems are one of a small number of shapes wearing a costume. Learn to spot the shape and the implementation follows. Each pattern below gives you the tell, a working Python implementation, the complexity, and the mistakes that actually cost people offers.
The problem set
The questions that recur across every "most asked" list, grouped by the pattern they teach. Each carries the tell that identifies it, the reasoning in derivation order, the complexity, a working Python solution, and the mistake that most often costs the offer.
Browse 81 problems →
Two pointers
Walk two indices toward each other, or one behind the other, in a single pass.
The tell: The input is sorted (or can be sorted) and you are looking for a pair, a triple, or a partition.
O(n) time after an O(n log n) sort, O(1) extra space.
Sliding window
Maintain a contiguous range and move its edges instead of re-scanning.
The tell: The words 'contiguous', 'substring', 'subarray', combined with longest/shortest/at most k.
O(n) — each index enters and leaves the window at most once.
Binary search on the answer
Search the space of possible answers, not the array.
The tell: 'Minimise the maximum', 'maximise the minimum', or a feasibility check that is monotone.
O(n log R) where R is the range of candidate answers.
Monotonic stack
Keep a stack that only ever increases (or decreases) to find the next greater element.
The tell: 'Next greater', 'previous smaller', 'span', histogram areas, or temperatures.
O(n) — every index is pushed once and popped at most once.
Graph traversal — BFS and DFS
BFS for fewest steps, DFS for reachability and structure.
The tell: Grids, islands, mazes, dependencies, connected components, or 'shortest path' with unit edges.
O(V + E). BFS uses O(V) queue space; recursive DFS uses O(V) stack.
Topological sort
Order nodes so every edge points forward — the answer to 'what can I do first?'
The tell: Prerequisites, build order, task scheduling, or any DAG where order matters.
O(V + E) time, O(V) space.
Heaps and top-k
Keep a size-k heap instead of sorting everything.
The tell: 'k largest', 'k closest', 'median of a stream', 'merge k sorted lists'.
O(n log k) for top-k, versus O(n log n) for a full sort.
Dynamic programming
Define the state, write the transition, then decide top-down or bottom-up.
The tell: Overlapping subproblems plus optimal substructure: 'count the ways', 'minimum cost', 'longest ...'.
states × transition cost. Coin change is O(amount × coins).
Union-find (disjoint set)
Merge groups and ask 'same group?' in near-constant time.
The tell: Connectivity queries, redundant edges, accounts merging, or Kruskal's MST.
Near O(1) amortised per operation with path compression + union by rank.
Backtracking
Build a candidate, recurse, undo. Prune early or it explodes.
The tell: 'All permutations', 'all subsets', 'all valid combinations', N-Queens, sudoku.
Exponential by nature — O(2^n) subsets, O(n!) permutations. Pruning is the whole game.