Shortest Paths
Listed inShortest PathsData Structures & Algorithmson
Dijkstra, Bellman-Ford, and A* — which one negative weights rule out, and which one a heuristic speeds up.
Advanced9 minDraft
#algorithms
The structures that cover almost everything, the algorithms worth recognising on sight, and the complexity vocabulary to argue about them — plus the point where theory stops predicting the benchmark.
36 articles
Listed inShortest PathsData Structures & Algorithmson
Dijkstra, Bellman-Ford, and A* — which one negative weights rule out, and which one a heuristic speeds up.
Listed inSolving an Unfamiliar ProblemData Structures & Algorithmson
A repeatable approach: examples first, brute force, find the redundancy, then optimise the part that matters.
Listed inBinary SearchData Structures & Algorithmson
The three-line algorithm nobody writes correctly first time, plus searching on the answer rather than the array.
Listed inArrays and Linked ListsData Structures & Algorithmson
Contiguous versus linked storage, amortised growth, and why cache locality usually settles the argument.
Listed inGreedy AlgorithmsData Structures & Algorithmson
When the locally best choice is provably globally best, and the far more common case where it is not.
Listed inHeaps and Priority QueuesData Structures & Algorithmson
The structure behind schedulers, top-k queries, and every "what should I do next" problem.
Listed inProbabilistic StructuresData Structures & Algorithmson
Bloom filters, HyperLogLog, and count-min sketch — trading exactness for orders of magnitude in memory.
Listed inGraphs and TraversalData Structures & Algorithmson
Adjacency lists versus matrices, BFS and DFS, and recognising a graph problem that was not described as one.
Listed inWhen Complexity Analysis LiesData Structures & Algorithmson
Cache misses, branch prediction, and allocator pressure — the constants that decide everything at small n.
Listed inSorting AlgorithmsData Structures & Algorithmson
Quicksort, mergesort, heapsort, and radix — stability, in-place behaviour, and why your standard library hybridises.
Listed inSpace ComplexityData Structures & Algorithmson
The axis people forget until the process is killed — auxiliary space, recursion depth, and in-place algorithms.
Listed inDivide and ConquerData Structures & Algorithmson
Split, solve, combine — and the master theorem for reading off the complexity without guessing.
Listed inTries and Prefix StructuresData Structures & Algorithmson
Prefix trees, radix trees, and the structure behind autocomplete, routing tables, and IP lookup.
Listed inRandomised AlgorithmsData Structures & Algorithmson
Reservoir sampling, randomised pivots, and using randomness to dodge an adversarial worst case.
Listed inPersistent Data StructuresData Structures & Algorithmson
Structural sharing so an "update" returns a new version cheaply, without copying the whole thing.
Listed inChoosing a Data StructureData Structures & Algorithmson
Starting from the access pattern rather than the structure, and why a plain array usually wins.
Listed inNetwork Flow and MatchingData Structures & Algorithmson
Max-flow, min-cut, and bipartite matching — the hammer for assignment problems that look nothing like graphs.
Listed inAmortised AnalysisData Structures & Algorithmson
Why a dynamic array append is O(1) even though some appends copy everything, and how to reason about the average.
Listed inTwo Pointers and Sliding WindowsData Structures & Algorithmson
Turning a nested loop into a single pass, and recognising the problems where that collapse is available.
Listed inTrees and Balanced TreesData Structures & Algorithmson
BSTs, AVL and red-black trees, B-trees, and why the database picked the one with the fat nodes.
Listed inDynamic ProgrammingData Structures & Algorithmson
Overlapping subproblems and optimal substructure, memoisation versus tabulation, and the classic patterns.
Listed inSkip ListsData Structures & Algorithmson
Probabilistic balancing that is far easier to implement than a balanced tree — and is why Redis sorts so well.
Listed inNumbers and Modular ArithmeticData Structures & Algorithmson
GCD, primes, modular exponentiation, and overflow-safe arithmetic — the maths that shows up in practice.
Listed inTopological SortingData Structures & Algorithmson
Ordering a dependency graph, detecting the cycle that makes it impossible, and why every build tool does this.
Listed inBig-O NotationData Structures & Algorithmson
Asymptotic complexity as a comparison tool, and the constants it deliberately throws away.
Listed inBit ManipulationData Structures & Algorithmson
Masks, shifts, and the handful of tricks worth memorising — plus bitsets as a compact set representation.
Listed inHash TablesData Structures & Algorithmson
Hashing, collision strategies, load factor, and the worst case that quietly turns O(1) into O(n).
Listed inBacktrackingData Structures & Algorithmson
Systematic search with early abandonment — N-queens, sudoku, and constraint problems generally.
Listed inSegment and Fenwick TreesData Structures & Algorithmson
Range queries with point updates, for when a prefix sum array is not enough and a rebuild is too slow.
Listed inIntractability and NP-CompletenessData Structures & Algorithmson
Recognising the problem nobody can solve efficiently, and what to do next: approximate, restrict, or heuristic.
Listed inMinimum Spanning TreesData Structures & Algorithmson
Kruskal and Prim, and the clustering and network-layout problems that turn out to be MST in disguise.
Listed inString AlgorithmsData Structures & Algorithmson
KMP, Rabin-Karp, suffix arrays, and edit distance — pattern matching beyond a nested loop.
Listed inStacks and QueuesData Structures & Algorithmson
LIFO, FIFO, deques, and ring buffers — the structures hiding inside schedulers, parsers, and undo.
Listed inRecursionData Structures & Algorithmson
Base cases, the call stack, tail calls, and converting a recursive solution to an iterative one when the stack runs out.
Listed inUnion-FindData Structures & Algorithmson
Disjoint sets with path compression — connectivity, cycle detection, and Kruskal in near-constant time.
Listed inWhen the Data Does Not FitData Structures & Algorithmson
External sorting, streaming, and chunked processing for datasets larger than memory.