23 patterns
Worked in dependency order — each one only assumes the patterns above it. 308 curated problems across the set.
The three workhorse structures behind almost every other pattern. A hash map buys you O(1) lookup; a stack remembers the most recent thing; a queue remembers the oldest. Pick the right one and half the problem disappears.
Keep two indices into the data and move them in a coordinated way — converging from opposite ends, chasing in the same direction, or walking two arrays at once. By exploiting structure (usually sorted order), you skip combinations that cannot win and squeeze an O(n²) pair search into one pass.
Maintain a contiguous window over the input and slide it forward, updating state incrementally instead of recalculating from scratch. The pattern that turns O(n·k) brute force into one clean O(n) pass.
Seven small, sharp tools — prefix sums, Kadane's, cyclic sort, Dutch flag, Boyer‑Moore, difference arrays, matrix walks. Each turns a quadratic brute force into a linear pass with O(1) tricks, usually by using the array's own indices as free storage.
Clean, idiomatic Python saves time and signals competence. Knowing the standard library means fewer bugs and faster implementations — this is the reference for the moves that answer “can you do that more cleanly?” before it's asked.
A Python string is a frozen list of characters. Every technique on this page is really a choice of representation — grow outward from a center, swap two ends of a character list, collapse a word into a canonical key, or prefix a payload with its own length.
Explore as deep as possible along each branch before backtracking, powered by a stack — the call stack (recursion) or an explicit one. One idea covers tree traversals, graph cycles, island counting, and topological sort.
Explore a graph level by level with a FIFO queue: everything at depth d is visited before anything at depth d+1. That one property means the first time BFS reaches a node is the shortest path to it — in unweighted graphs.
Eliminate half the search space with every comparison. It works on any monotonic search space — not just sorted arrays — turning linear scans into O(log n).
Pointer-based structures with no random access — every operation is a traversal, and mastery is nothing more than clean pointer manipulation. Three moves (dummy node, fast/slow, prev/curr/next) cover almost every interview question.
Anything with a start and an end — meetings, ranges, balloons — yields to the same move: sort by start, then sweep, comparing each interval only against the last one kept.
Floyd's tortoise and hare: two pointers walk the same list at different speeds — one hop vs. two. If there's a cycle, the fast one must lap the slow one; if there isn't, fast hits the end when slow is at the middle. Cycle detection, midpoints, and duplicates in O(1) space.
Treat an integer as a row of on/off switches instead of a quantity. A handful of operators — XOR, AND, shifts — turn "find the number that appears once" and "count the set bits" into one clean pass with no extra memory.
A binary search tree is an ordinary binary tree plus one promise: every value on the left is smaller, every value on the right is larger. That single promise turns lookup into binary search and makes an in-order walk hand you the values already sorted. This page is about tree structure itself — the invariant, height, balance, diameter, and how to rebuild a tree — not about traversal mechanics.
Break a problem into overlapping subproblems, solve each one exactly once, and store the results. The recipe that collapses exponential recursion trees into linear tables.
Make the locally optimal choice at each step and never look back. When it works, it beats DP on every axis — the hard part is knowing when it's actually safe.
Try something. If it doesn't work, undo it and try something else. Backtracking explores every possible solution by making a choice, recursing deeper, then reversing the choice — abandoning a path the moment it can't lead to a valid answer.
Find the k largest, smallest, or most frequent elements without sorting everything — keep a heap capped at size k and let it evict the losers. O(n log n) becomes O(n log k).
A stack that keeps its elements in sorted order — and pops anything that would break it. Every pop answers a "next greater / next smaller" question, and since each element is pushed and popped at most once, the whole thing is one amortized O(n) pass.
A prefix tree (pronounced "try"): one character per node, so words that share a prefix share a path from the root. The structure behind autocomplete, multi-word grid search, and wildcard matching — everything a hash set can't do, in O(m) per operation.
Track a collection of elements partitioned into non-overlapping sets with just two operations — find and union. With path compression and union by rank, both run in near-constant amortized time.
Once edges carry weights or direction with dependencies, plain BFS stops being enough. This is the toolbox: build the adjacency list, then reach for Dijkstra, Bellman-Ford, topological sort, or an MST.