Algorithms, visualised
Every algorithm here runs as a real trace you can scrub, rewind and question. Playback pauses at decision points and asks you to predict — because watching teaches almost nothing, and predicting is where the learning happens.
Sorting
- Merge sortmediumSplit until trivially sorted, then merge sorted halves. The canonical divide-and-conquer, and the sort that guarantees O(n log n). Stable, but needs O(n) space.O(n log n)
- QuicksortmediumPartition around a pivot that lands exactly where it belongs, then recurse on each side. The fastest comparison sort in practice. In place and cache-friendly.O(n log n) average
- Heap sortmediumBuild a max-heap in place, then repeatedly swap the maximum to the end. O(n log n) guaranteed, O(1) extra space. The heap makes the maximum free to find.O(n log n)
- Insertion sorteasyGrows a sorted prefix by inserting each value into it. The sort real libraries fall back to for small or nearly-sorted runs. Shifts, not swaps, do the work.O(n²)
- Bubble sorteasyRepeatedly walks the array swapping out-of-order neighbours. Slow, but the clearest possible picture of what sorting is. Every pass sinks one more maximum.O(n²)
- Selection sorteasyFinds the smallest remaining value and puts it in place. Makes the fewest writes of any simple sort — exactly n-1 swaps. Costly scans, minimal movement.O(n²)
- Counting sorteasyNo comparisons anywhere: tally how many of each value exist, then write the values back in order. O(n + k), and the engine inside radix sort.O(n + k)
- Radix sortmediumSorts by one digit at a time, least significant first, with a stable shuffle per digit. Linear time for fixed-width keys. Counting sort runs once per digit.O(d·(n + b))
Searching
- Binary searcheasyHalve the search range with every probe. The most important loop invariant in interviewing, and the easiest to get subtly wrong. Twenty probes search a million.O(log n)
- Two pointerseasyTwo indices closing in from both ends of a sorted array, eliminating an element against all remaining partners each step. Linear time from sorted order.O(n)
- Sliding windoweasyA fixed-width window slides across the array, updating its sum with one add and one subtract. The move that turns O(n·k) into O(n). No re-scanning, ever.O(n)
Graphs
- Breadth-first searchmediumExplores a graph in rings of increasing distance. The queue is the whole idea: first discovered, first explored. First paths found are shortest paths.O(V + E)
- Depth-first searchmediumFollows one path as deep as it goes, then backtracks. The call stack is the data structure. Cycle detection, topo sort and maze-solving fall out of it.O(V + E)
- Dijkstra's algorithmhardShortest paths with non-negative weights: always settle the cheapest unsettled node, because nothing can ever undercut it. Greedy, and provably right.O((V + E) log V)
- Topological sortmediumOrder a DAG so every edge points forward. Kahn's algorithm peels off nodes with no remaining prerequisites. A leftover node proves there is a cycle.O(V + E)
- Union–FindmediumDisjoint sets with near-constant merge and lookup. Process edges once and components, cycles and connectivity all fall out. Path compression does the magic.O(α(n)) per op
- Bellman–FordmediumShortest paths with negative edges allowed: relax every edge, V−1 times, and let a fixed point — or a negative cycle — announce itself. Slower, but unfooled.O(V·E)
- KruskalmediumMinimum spanning tree by global greed: consider edges lightest-first, accept each unless it would close a cycle. Union-find is the cycle referee.O(E log E)
- PrimmediumMinimum spanning tree by local greed: one connected blob swallows its cheapest neighbour, forever. Dijkstra’s twin with a different key. O(E log V) with a heap.O(E log V)
- A* searchhardDijkstra with a compass: the heap is ordered by cost so far PLUS a never-overestimating guess of the cost remaining. Fewer expansions, same optimal path.O(E log V)
Trees
- In-order traversaleasyLeft, node, right — recursively. On a search tree the output comes out sorted, which is the BST property made visible. Three lines, one sorted stream.O(n)
- BST insertioneasyBuild a binary search tree by repeated insertion. The input order decides the shape — sorted input builds a useless chain. The shape decides every later cost.O(h) per insert
- BST searcheasyFollow one comparison per level; each one discards an entire subtree. Binary search, tree-shaped. Half the tree vanishes per step — while the tree is balanced.O(h)
- BST deletionmediumThree shapes of removal — leaf, one child, two children — and the third is the one interviews are about: the inorder successor stands in. Order is preserved.O(h)
- Heap operationsmediumPush bubbles up, pop sinks down, and the tree is always complete. The machine inside every priority queue, drawn as the tree it secretly is.O(log n) per operation
- TriemediumA tree where each edge is a letter and shared prefixes are stored once. Lookup costs the word length — the dictionary size never appears. Autocomplete, solved.O(L) per word
- AVL insertionhardA BST that refuses to degenerate: after every insertion, at most two rotations restore balance. Sorted input builds a bushy tree anyway. O(log n), guaranteed.O(log n) per insert
Dynamic programming
- Longest common subsequencemediumFill a table where each cell answers the problem for a pair of prefixes. The canonical two-dimensional DP. Diff tools and DNA alignment run on it.O(mn)
- Coin changemediumFewest coins to make an amount — the problem where greedy confidently gives the wrong answer and the DP table quietly delivers the right one.O(n·amount)
- Memoization (Fibonacci)easyThe same recursion, plus a Map — and an exponential call tree collapses to a linear one. Memoization, watched happening. The gentlest doorway into DP.O(n) memoized
- 0/1 knapsackmediumPack a fixed capacity for maximum value, each item taken whole or not at all. The template half of all optimisation DP is cut from, built row by row.O(n·W)
- Longest increasing subsequencemediumThe longest chain of values that climbs left to right, skipping freely. Each element asks every smaller predecessor: can I extend you? Patience gets to n log n.O(n²)
- Edit distancehardThe fewest single-character edits turning one string into another. Three moves per cell: substitute, delete, insert. Spell-check and diff live here.O(mn)
Recursion & backtracking
- SubsetseasyEvery subset of a set, by a binary decision per element: exclude, recurse, include, recurse, un-choose. The smallest complete backtracking pattern.O(2^n · n)
- PermutationsmediumEvery ordering, by swapping each candidate into position, recursing, and swapping back. The array itself is the state — and the un-swap is the algorithm.O(n! · n)
- N-QueenshardPlace queens row by row; when every column of a row fails, take the previous queen back off. Backtracking, undisguised. The recursion tree is the lesson.O(n!) pruned
- Sudoku solverhardConstraint-satisfaction by try, fail, un-choose: guesses fill the board, contradictions erase them, and the clues are never touched. A 4×4 board stays legible.exponential in empty cells
Linked lists & pointers
- Linked-list reversaleasyThree pointers walk the list once and every arrow flips. The most-asked pointer question in interviewing, and the cleanest. One loop, no extra space.O(n)
- Cycle detectionmediumFloyd's tortoise and hare: two runners at speeds 1 and 2. A cycle traps them both, so they must meet — and phase 2 walks to the entry. O(1) space, provably.O(n)
Strings
- KMP string searchhardPattern search where the text pointer never moves backwards: the pattern precomputes how it overlaps itself, and mismatches slide instead of restart.O(n + m)
- Rabin–KarpmediumCompare numbers instead of strings: a rolling hash slides across the text in O(1) per step, and characters are consulted only when the numbers agree.O(n + m) expected