All 140 articles, sorted alphabetically
A* Pathfinding, in depth: admissible and consistent heuristics, grid heuristics, tie-breaking, weighted A* and when to move beyond it
How A* finds shortest paths: f = g + h from first principles, a correct Python implementation with lazy deletion, what admissibility and consistency e…
Read article →2-SAT, in depth: implication graphs, strongly connected components and a tested solver
How 2-SAT is solved in linear time: turning two-literal clauses into an implication graph, why strongly connected components decide satisfiability, re…
Read article →ARC architecture
Deep-dive on ARC, the Adaptive Replacement Cache that beats LRU and LFU by adapting the recency-versus-frequency balance automatically per workload, w…
Read article →Backtracking, in depth: choose, explore, unchoose, and the pruning that makes exponential search usable
A first-principles guide to backtracking: the state-space tree, the choose/explore/unchoose template, a bitmask N-Queens solver with measured node cou…
Read article →BFS and DFS, in depth: frontiers, visited sets, shortest paths, edge classification, cycle detection and the bugs that make traversals wrong or slow
Breadth-first and depth-first search from first principles: the frontier container, when to mark visited, BFS shortest paths and parent maps, DFS disc…
Read article →Big-O Notation
Asymptotic complexity done properly: the formal definitions of O, Omega and Theta, why worst case is a different axis from big-O, amortized and expect…
Read article →Bloom filter architecture
Deep-dive on Bloom filter architecture: hash family, sizing math, counting and cuckoo variants, and the ops layer for production use.
Read article →Count-Min Sketch Architecture in Depth
A 2500-word walkthrough of Count-Min Sketch: d × w counter matrix, hash functions, insert + query, overestimate math, parameters, applications, varian…
Read article →Consistent hashing architecture
Deep-dive on consistent hashing: ring, virtual nodes, replica walk, bounded loads, Anchor/Jump/Rendezvous variants, and cluster management.
Read article →Convex Hull, in depth: orientation tests, monotone chain, output-sensitive algorithms, robustness and rotating calipers
The convex hull from first principles: the n log n lower bound, the orientation predicate, Andrew's monotone chain with a full worked trace, Grah…
Read article →Count-Min Sketch, in depth: the error proof, and the queries beyond point lookups: ranges, quantiles, heavy-hitter recovery and join sizes
Count-Min Sketch from first principles, past the point query: a four-step proof of the error bound, the strict-turnstile caveat and skew, dyadic range…
Read article →Count-Min Sketch Architecture, in depth: an implementation guide to memory layout, hashing once, concurrency, serialization and testing the error bound
How to build a production Count-Min sketch: a contiguous counter layout with power-of-two width, deriving all row indices from one stable hash, a refe…
Read article →Cuckoo filters
Deep-dive on cuckoo filters: partial-key cuckoo hashing and the i2 = i1 XOR hash(fp) involution, fingerprint sizing and the 2b/2^f false-positive math…
Read article →Dijkstra's Algorithm, in depth: the settled-frontier invariant, a correct implementation, negative edges and production pitfalls
A complete guide to Dijkstra&a…
Read article →Dinic's Algorithm, in depth: level graphs, blocking flows, current-arc pointers and a max-flow implementation you can trust
Dinic's maximum-flow algorithm from first principles: residual graphs, BFS level graphs, blocking flows with current-arc …
Read article →DiskANN architecture
Deep-dive on DiskANN: the Vamana low-diameter graph, product-quantized guidance in RAM with full vectors on disk, beam search and exact re-rank, alpha…
Read article →Distributed Consensus Architecture: Raft, Paxos, and Beyond
A 2500-word walkthrough of a modern consensus system: client, coordinator, leader, log, followers, state machines, and snapshots.
Read article →Divide and Conquer, in depth: recursion trees, the master theorem, worked algorithms and making recursive code fast
Divide and conquer from first principles: divide, conquer, combine, reading a recursion tree, the master theorem with worked recurrences, counting inv…
Read article →Dynamic programming, in depth: states, recurrences, evaluation order and the bugs that break them
A first-principles guide to dynamic programming: optimal substructure and overlapping subproblems, the subproblem DAG, defining state and recurrence, …
Read article →Fenwick tree architecture
Deep-dive on the Fenwick tree (binary indexed tree): the range each cell owns via lowbit(i) = i &a…
Read article →Fast Fourier Transform, in depth: roots of unity, the butterfly, iterative in-place code, fast convolution, precision limits and where FFTs run in ML
The Fast Fourier Transform from first principles: the DFT as polynomial evaluation at roots of unity, the even/odd split and butterfly, recursive and …
Read article →Graph Coloring, in depth: bounds, greedy orderings, DSATUR, exact backtracking, and how compilers and schedulers use it
A practical guide to graph colouring: proper colourings and the chromatic number, the bounds that tell you when you are done, why greedy colouring dep…
Read article →Greedy Algorithms, in depth: when the locally best choice is globally right, and how to prove it
Greedy algorithms from first principles: the greedy-choice property and optimal substructure, exchange and stays-ahead proofs, activity selection and …
Read article →Hash Tables
What the O(1) in a hash table really promises: index reduction, probe-count arithmetic, chaining vs open addressing vs SwissTable, deletion, and resiz…
Read article →Heap Operations
How binary heaps implement priority queues in O(log n), the heapify trick, and applications from Dijkstra to scheduling.
Read article →HyperLogLog Algorithm Architecture in Depth
A 2500-word walkthrough of HyperLogLog: hash function, bucketing, rank via leading zeros, harmonic mean estimator, bias correction, merge, space-error…
Read article →HNSW architecture
Deep-dive on HNSW: layered proximity graphs, greedy descent and efSearch beam search, geometric level assignment, the diversity neighbor heuristic, fi…
Read article →HyperLogLog architecture, in depth: registers, sparse encoding, estimators and merge in production
How a production HyperLogLog is built: hash choice and canonicalisation, precision and memory, dense 6-bit register packing, sparse encodings in HLL++…
Read article →Integer Programming and LP, in depth: LP relaxations, branch and bound, cutting planes and models a solver can finish
Integer programming from linear programming: polyhedra and vertices, duality as a bound, LP relaxation and integrality gap, total unimodularity, branc…
Read article →IVF-PQ vector index architecture
Deep-dive on the IVF-PQ approximate nearest-neighbor index: coarse quantization and inverted lists (nlist/nprobe), product quantization into per-subsp…
Read article →KD-Tree, in depth: bounding-box pruning, best-first search, range counting and when it stops paying
Engineering a k-d tree that is fast and correct: tight bounding boxes as lower bounds, best-first nearest-neighbour search with early termination, ran…
Read article →KMP Algorithm
How the Knuth-Morris-Pratt algorithm finds a pattern in text in O(n+m) by precomputing a failure function.
Read article →Knapsack Problem, in depth: 0/1, unbounded and bounded DP, reconstruction, meet-in-the-middle, branch and bound and approximation
A first-principles guide to the knapsack family: why greedy fails, the 0/1 recurrence with a worked table, one-dimensional loop direction, reconstruct…
Read article →Lowest Common Ancestor, in depth: ancestor tests, path queries, rerooting, virtual trees and merge bases in DAGs
What to build once you have LCA: an O(1) ancestor test from entry and exit times, binary lifting driven by that test, weighted distance and path maxim…
Read article →Longest Common Subsequence, in depth: the recurrence, traceback, linear-space Hirschberg and how diff uses it
Longest common subsequence from first principles: why brute force fails, deriving the recurrence, a filled table for ABCBDAB and BDCABA, tested Python…
Read article →LRU cache architecture
Deep-dive on LRU cache: hash map + linked list, admission policies (TinyLFU), concurrency, TTL, weighted entries, variants.
Read article →LSM Tree Compaction Architecture in Depth
A 2500-word walkthrough of LSM compaction: memtable → SSTables, STCS/LCS/TWCS strategies, triggers, throttling, and read/write/space amplification.
Read article →LSM-Tree, in depth: invariants, a working implementation, the k-way merge and the amplification cost model
The log-structured merge tree as a data structure: why batching sorted runs makes writes cheap, the four invariants, a runnable mini-LSM in Python wit…
Read article →LSM trees vs B-trees
Deep-dive on LSM trees vs B-trees: in-place read-optimized B-trees vs append-merge write-optimized LSM trees, write/read/space amplification, compacti…
Read article →Matrix Exponentiation, in depth
Matrix exponentiation beyond the basics: augmented state for constant, polynomial and exponential terms, prefix sums and matrix geometric series, Kita…
Read article →Mergesort
Mergesort in depth: the merge step and where stability comes from, top-down versus bottom-up, TimSort&…
Read article →Merkle trees -- efficient verification of large data
Deep-dive on Merkle trees: hashing data blocks into leaves and up to a single root, tamper evidence (any change alters the root), O(1) root comparison…
Read article →Number Theory Algorithms, in depth: gcd, extended Euclid, modular inverses, fast exponentiation, sieves, Euler's phi and the Chinese remainder theorem
The core number theory toolkit for programmers, built from first principles: Euclid and extended Euclid, modular inverses, square-and-multiply exponen…
Read article →How a Matrix Multiply Runs on a GPU: Tiling, Shared Memory, and Tensor Cores, with Pseudocode
A step-by-step walk from a naive CUDA matrix multiply to shared-memory tiling, register blocking and tensor-core WMMA kernels, with the arithmetic-int…
Read article →Sieve of Eratosthenes, in depth: a hand trace, the n log log n argument, odd-only and segmented sieves, memory layouts and cache-aware production use
The Sieve of Eratosthenes from first principles: a worked trace to 30, why crossing off starts at p squared, why the cost is n log log n, tested Pytho…
Read article →Quicksort
Quicksort in depth: the partition invariant, Lomuto vs Hoare, pivot choice, three-way partitioning, stack bounding, and what introsort and pdqsort rea…
Read article →The quotient filter
Deep-dive on the quotient filter: splitting a key&…
Read article →Regular Expressions, in depth: from pattern to Thompson NFA, lockstep simulation, why backtracking explodes, and patterns that cannot hang
How regular expressions really execute: a recursive-descent parser, Thompson's NFA construction, lockstep simulation in O(m*n), a…
Read article →Rendezvous Hashing Architecture, in depth: score functions, weighted HRW, failure-domain-aware replicas and precomputed tables
A first-principles guide to rendezvous (highest random weight) hashing: why only K/n keys move, building a score function that really mixes key and no…
Read article →Reservoir sampling architecture, in depth: skip-based sampling, mergeable bottom-k keys, weighted variants and windows
Reservoir sampling as a production system: Algorithm L to skip most random draws, the bottom-k random-key form that merges across shards, correct merg…
Read article →Reservoir sampling
Deep-dive on reservoir sampling (Algorithm R): drawing k items uniformly at random from a stream of unknown length in a single forward pass with O(k) …
Read article →Ribbon filter architecture
Deep-dive on the ribbon filter: a static approximate-membership structure that encodes the key set as a solved banded linear system over GF(2), reachi…
Read article →Roaring bitmaps -- compressed bitmaps that stay fast
Deep-dive on roaring bitmaps: the bitmap dilemma (fast but big, or small but slow), chunking the integer space by the high 16 bits, the three adaptive…
Read article →Segment Tree
Segment trees end to end: canonical decomposition, the 4n array layout, O(n) build, lazy propagation, and when a Fenwick tree beats one.
Read article →Skip list architecture
Deep-dive on skip lists: levels, level selection, search, insert/delete, concurrent variants, range iterators, memory, use cases.
Read article →Space-Saving architecture
Deep-dive on the Space-Saving algorithm for approximate top-k heavy hitters: a fixed table of k counters, the increment-or-evict-the-minimum rule that…
Read article →String Matching, in depth: choosing between naive, Horspool, Rabin-Karp and Two-Way, worst cases and Unicode traps
How to choose and implement an exact string-matching algorithm: the naive baseline and vector scans, Horspool with a worked trace, randomised Rabin-Ka…
Read article →t-digest architecture
Deep-dive on the t-digest quantile sketch: (mean, count) centroids, the scale function that warps cluster sizes to keep the tails sharp, the compressi…
Read article →Top-K / heavy hitters -- finding the most frequent in a stream
Deep-dive on top-K / heavy-hitter algorithms: the most-frequent-items problem, why exact counting is memory-prohibitive, Space-Saving (bounded counter…
Read article →Topological Sort, in depth: Kahn and DFS, cycle reporting, deterministic orders, parallel levels and build systems
Topological sort from first principles: what a dependency order is, Kahn&a…
Read article →Trie in Depth: Prefix Trees From First Principles to Radix Trees, Autocomplete and Longest-Prefix Match
How a trie works and when to use one: node representations and their memory cost, insert, search, prefix counting, deletion with pruning, cached top-k…
Read article →Union-Find, in depth: disjoint sets, union by size, path compression and the inverse Ackermann bound
Union-Find (disjoint set union) explained from first principles: the parent-pointer forest, why naive unions degrade to linear chains, union by size o…
Read article →Balanced Binary Tree Check, in depth: the definition, the O(n) post-order pass, iterative versions and the traps
How to test whether a binary tree is height-balanced: the precise definition, why the top-down approach repeats work, the single post-order pass with …
Read article →BFS on Grids, in depth: flat indexing, mark-on-enqueue, path reconstruction, multi-source BFS, islands, border floods, (cell, k) states and memory at scale
Grid breadth-first search from first principles: the template with direction tables and parent arrays, a traced worked example, multi-source BFS, comp…
Read article →BFS on Implicit Graphs, in depth: designing states, generating neighbours, visited-set memory, the 8-puzzle, bidirectional search and when the state space is too big
How to run breadth-first search on graphs that are never stored: what a state must contain, encoding and visited-set memory, testing goals at generati…
Read article →0-1 BFS, in depth: shortest paths with 0 and 1 weights using a deque, the invariant, stale entries and how to model problems for it
A first-principles guide to 0-1 BFS: why plain BFS fails once some edges are free, the two-value deque invariant that replaces Dijkstra&am…
Read article →Bipartite Check, in depth
Bipartite checking in depth: the odd-cycle theorem with proof, BFS two-colouring over every component in Python, recovering an odd-cycle certificate f…
Read article →Bounded Knapsack, in depth
Bounded knapsack in depth: the per-count recurrence, binary splitting with a proof, the O(nW) monotone-queue method over residue classes, the used-cou…
Read article →Bridges and Articulation Points with Tarjan's Low-Link Algorithm: One DFS, Two Answers, and the Details That Break Real Implementations
Find every bridge and articulation point of an undirected graph in O(V + E) with one depth-first search: discovery times and low-links from first prin…
Read article →BST Insert, Search and Delete, in depth: the invariant, iterative code, all three delete cases traced by hand, height analysis and testing
A first-principles guide to binary search tree operations: the ordering invariant and why every operation costs O(height), iterative search, floor and…
Read article →BST Validation, in depth: bounds recursion, in-order checks, duplicates and validating real ordered structures
How to check that a binary tree is a valid binary search tree: the global invariant, why the local parent-child check is wrong, bounds recursion, iter…
Read article →Build a Binary Tree From Two Traversals, in depth: why preorder or postorder plus inorder is unique, O(n) recursive and stack builds, validation, and why preorder plus postorder is not enough
Reconstructing a binary tree from two traversal sequences: the uniqueness argument, a traced worked example, O(n) builders for preorder+inorder and po…
Read article →Cartesian Tree, in depth: linear-time construction, range minimum via LCA, ties, treaps and when to use one
A first-principles guide to Cartesian trees: the heap-plus-in-order definition, the O(n) stack construction traced by hand, why range minimum equals l…
Read article →Convex Hull, in depth: Graham scan, exact orientation tests and degenerate inputs
Graham scan from first principles: the cross-product orientation test and its 64-bit overflow headroom, sorting by angle without atan2, the stack inva…
Read article →Deep Copy List with Random Pointer, in depth: the identity map, the O(1)-space interleaving trick, a copy verifier and graph cloning
How to deep-copy a linked list whose nodes also carry a random pointer: why a naive copy fails, the two-pass hash map, a one-pass memoised version, th…
Read article →Cycle Detection in Directed Graph, in depth: three-colour DFS that returns the cycle, an explicit-stack version for deep graphs, Kahn leftovers, all cycles via SCCs and where it runs in production
How to detect and report cycles in directed graphs: why undirected tricks fail, three-colour DFS with a cycle witness, a worked example, an iterative …
Read article →Cycle Detection, in depth: Floyd's tortoise and hare, Brent's algorithm, the rho shape, proofs, linked lists, Pollard's rho and production pitfalls
A first-principles guide to cycle detection on iterated functions: the rho shape and its tail length mu and cycle length lambda, Floyd&amp…
Read article →Dijkstra's Algorithm, in depth: a reusable engine for state graphs, custom path costs, time-dependent edges and certified answers
Dijkstra's algorithm as a reusable engine: one loop w…
Read article →Dijkstra's Shortest Path, in depth: the algorithm as an event stream, a frame-by-frame trace, and rendering the wavefront
Dijkstra's algorithm rebuilt as a stream of observable events so you can animate it: an i…
Read article →Coin Change, in depth: minimum coins and counting ways, loop order, reconstruction, greedy checks and the bugs that break each variant
Coin change from first principles: the minimum-coins and number-of-ways variants worked by hand, why loop order counts combinations or ordered sequenc…
Read article →Edmonds-Karp in Depth: Why Shortest Augmenting Paths Bound Max Flow at O(VE²), With a Traced Proof and an Implementation You Can Trust
Edmonds-Karp from first principles: why augmenting along BFS shortest paths guarantees polynomial time, the monotone-distance and critical-edge proof …
Read article →Euler Tour Technique, in depth
The Euler tour technique in depth: the three tour shapes, entry and exit times that turn subtrees into array slices, an O(1) ancestor test, an iterati…
Read article →Eulerian Path, in depth: the degree conditions, the Hierholzer algorithm with an explicit stack, multigraphs, itineraries and de Bruijn sequences
How to find a path or circuit that uses every edge exactly once: the degree and connectivity conditions for undirected and directed graphs, why Hierho…
Read article →Fibonacci Computation, in depth: fast doubling, big-integer cost and modular answers
Computing Fibonacci numbers properly: why naive recursion makes 2F(n+1)-1 calls, the true big-integer cost of the loop, fast doubling derived from the…
Read article →Flood Fill, in depth: connectivity, stack-safe fills, scanline spans, tolerance and region labeling
Flood fill as an image and region operation: 4- versus 8-connectivity and diagonal leaks, why recursive fills crash, explicit-stack and scanline (span…
Read article →Fractional Knapsack, in depth: the greedy proof, a linear-time algorithm and the LP bound
Fractional knapsack from first principles: greedy by value density, a worked five-item example, the exchange-argument proof, the LP and critical-ratio…
Read article →Hamiltonian Path, in depth
Finding a path that visits every vertex once: why it is NP-complete, backtracking with reachability and dead-end pruning, a measured worked example, t…
Read article →Huffman Coding, in depth: optimal prefix codes, canonical codes, length limits and table-driven decoding
Huffman coding from first principles to a working codec: prefix codes, the Kraft inequality and the entropy bound, a worked six-symbol example, canoni…
Read article →Interval Merging + Meeting Rooms, in depth: half-open intervals, merge, the room count three ways, room assignment and production traps
Interval merging and the meeting rooms problem from first principles: half-open conventions, why sort-by-start merging is correct, minimum rooms by mi…
Read article →Interval Tree, in depth: the max-end augmented BST, tested code, query pruning and when to use something else
How interval trees answer overlap and stabbing queries: half-open intervals, the max-end augmentation on a balanced BST, tested treap code for insert,…
Read article →Iterative DFS, in depth: explicit stack frames, finish times, the two shortcuts that break, and an iterative Tarjan SCC
How to write depth-first search without recursion and keep it correct: stack frames with cursors, Python and Java code, a step-by-step trace, why mark…
Read article →Job Scheduling with Deadlines, in depth: the profit-maximising greedy, union-find slots, Moore-Hodgson, EDF and where greedy stops working
Job sequencing with deadlines from first principles: the unit-time profit problem, the latest-free-slot greedy with a worked example and proof sketch,…
Read article →K-d Tree, in depth: median construction, nearest-neighbour pruning, range search, the curse of dimensionality and production layouts
How a k-d tree partitions k-dimensional space and answers nearest-neighbour, k-NN and range queries: median construction, the plane-pruning rule trace…
Read article →Kosaraju's Algorithm, in depth: the finish-time lemma, iterative two-pass SCC, output order and real uses
Kosaraju's algorithm for strongly connected components explained from first p…
Read article →Kth Smallest in a BST, in depth: early-exit inorder, Morris traversal without leaving threads behind, and size-augmented order-statistic trees for repeated queries
A complete guide to finding the kth smallest key in a binary search tree: why inorder order is sorted order, recursive and iterative early-exit traver…
Read article →Kuhn's Algorithm, in depth: maximum bipartite matching with augmenting paths, a traced example, recursive and iterative Python, correctness, complexity and when to switch
Kuhn's algorithm for maximum bipartite matching from first principles: matchings, alternating and augmenting path…
Read article →Label Propagation, in depth: community detection in near-linear time, a hand trace, an implementation, oscillation and flooding, variants and evaluation
How label propagation finds communities: the Raghavan, Albert and Kumara algorithm with asynchronous random-order updates and its stopping rule, a ste…
Read article →LCP Array, in depth: Kasai linear-time construction, the proof, a full banana trace, the PLCP variant and the string problems it solves
What the longest-common-prefix array is and how Kasai's algorithm builds it from a suffix array in O(n): the key lemm…
Read article →Legendre and Jacobi Symbols, in depth: quadratic residues, reciprocity, a gcd-speed algorithm and where primality tests use them
A first-principles guide to the Legendre and Jacobi symbols: what quadratic residues are, Euler&am…
Read article →LFU Cache, in depth: the O(1) frequency-bucket design, tie-breaking, aging, Redis's approximated LFU and when frequency beats recency
Build a Least Frequently Used cache from first principles: why frequency, the naive scan and heap designs, the O(1) structure of a key map plus per-co…
Read article →Linear Diophantine Equations, in depth: existence, every solution from one, counting in a range, non-negative solutions and overflow
How to solve ax + by = c over the integers: the gcd existence test, extended Euclid, the general solution, a worked crate-packing example, counting so…
Read article →Singly Linked List, in depth
Singly linked lists in depth: node layout and the head/tail/size invariants, push and pop at both ends with complexity, sentinel and pointer-to-pointe…
Read article →Longest Palindromic Subsequence
Find the longest subsequence (not contiguous) that reads the same forwards and backwards. O(N²) DP via LCS reduction or direct recurrence; examples, c…
Read article →Longest Path in DAG, in depth
Longest path in a directed acyclic graph in depth: why it is NP-hard in general and linear on DAGs, the topological DP with reconstruction and cycle d…
Read article →Lowest Common Ancestor (LCA), in depth: naive climbing, binary lifting, Euler tour with sparse tables, Tarjan's offline algorithm, and how to choose
A practical guide to lowest common ancestor queries on trees: the definition, the naive climb, binary lifting, Euler tour plus sparse-table RMQ, Tarja…
Read article →Lucas' Theorem, in depth: binomial coefficients modulo a prime when n is larger than p, with proof, worked examples, code and the CRT extension
Lucas' theorem from first principles: why the factorial-inverse method for C(n, k) mod p breaks once n reaches p, the…
Read article →Manacher's Algorithm, in depth: all longest palindromes by centre in linear time, the mirror argument, a full trace, and O(1) palindrome queries
Manacher's algorithm from first principles: why expand-around-centre is quadratic, the separator transform and why separators nev…
Read article →Matrix Exponentiation, in depth: building transition matrices, a worked example by hand, overflow-safe code, walks, min-plus shortest paths and automata
Matrix exponentiation from first principles: writing a step as a matrix, constructing transition matrices for recurrences, constants, polynomial terms…
Read article →Max Flow in Depth: Ford-Fulkerson, Residual Graphs, Edmonds-Karp and the Minimum Cut, with Working Code
A from-first-principles guide to maximum flow: flow networks, residual graphs and reverse edges, the Ford-Fulkerson method, Edmonds-Karp&a…
Read article →Merge K Sorted Lists, in depth: the min-heap merge, divide and conquer, and k-way merging in real systems
How to merge k sorted lists into one sorted output: why naive approaches cost O(N log N) or O(kN), the min-heap algorithm with its O(N log k) proof, c…
Read article →Miller-Rabin, in depth: strong probable primes, witnesses, deterministic base sets and the bugs that break primality tests
How the Miller-Rabin primality test works from first principles: the n-1 = 2^s d decomposition, square roots of one, worked traces, error bounds, dete…
Read article →Mo's Algorithm, in depth: answering offline range queries in O((n + q) sqrt n) by reordering them
A first-principles guide to Mo's algorithm: the cost model behind sqrt decomposition of q…
Read article →Modular Exponentiation, in depth: square-and-multiply traced by hand, overflow, exponent reduction, windows, Montgomery multiplication, constant time and RSA-CRT
Modular exponentiation from first principles: why reducing after each step works, left-to-right and right-to-left square-and-multiply with a hand trac…
Read article →Morris Traversal, in depth: threading a binary tree for O(1)-space inorder, preorder and postorder walks
How Morris traversal walks a binary tree with no stack and no recursion by temporarily threading null right pointers: the invariant, a full worked tra…
Read article →Path Sum Problems Family, in depth: root-to-leaf checks, all paths, prefix-sum counting, maximum path sum and grid paths
One mental model for the path sum family of tree and grid problems: carrying state down a DFS, returning gains up, counting any downward path with pre…
Read article →Permutations and Combinations by Backtracking, in depth: decision trees, duplicates, combination sum, next permutation, the Heap algorithm and ranking
Generating permutations, combinations and subsets correctly: the decision tree and its output-size cost, used-array and swap permutations, start-index…
Read article →Planarity Testing
Determine if a graph can be drawn on a plane without edge crossings in linear time O(V+E). Kuratowski and Wagner characterizations, Hopcroft-Tarjan pa…
Read article →Populate Next Right Pointers in a Binary Tree, in depth: queue BFS, O(1)-space level walking, the dummy-head trick and the traps in each
A complete guide to populating next right pointers in perfect and arbitrary binary trees: the level-order linked list model, queue BFS, the constant-s…
Read article →Prim's Minimum Spanning Tree, in depth: the cut property, lazy and eager heaps, the dense-graph version and the bugs that break it
Prim's algorithm from first principles: what a minimum spanning tree is, why …
Read article →Priority Queue via Binary Heap, in depth: an indexed heap with update and remove, stable ties, a scheduler and the tests that keep it honest
Build a production priority queue on a binary heap: the abstract contract, a complete indexed min-heap with push, pop, update and remove, why removal …
Read article →Reverse a Linked List, in depth: the three-pointer loop, its invariant, recursion and the stack limit, sublist and k-group reversal
How to reverse a singly linked list in place from first principles: the iterative three-pointer loop and why it is correct, a worked trace, the recurs…
Read article →Detecting Negative Cycles, in depth: the Bellman-Ford proof, extracting the cycle, finding every affected vertex, and currency arbitrage
How to detect negative cycles in a weighted directed graph and act on the result: why the n-th Bellman-Ford pass is a proof, the virtual-source trick,…
Read article →Small-to-Large Merging, in depth: the doubling argument, subtree queries in O(n log n), carrying aggregates, the sack variant, and where it breaks
Small-to-large merging from first principles: why naive merging is quadratic, the proof that each element moves at most log2 n times, measured move co…
Read article →Smallest Enclosing Circle, in depth: Welzl's randomized algorithm, why it runs in expected linear time, and a robust implementation
The smallest enclosing circle from first principles: uniqueness and support sets, Welzl's recursive and iterative algorithms, backwards analysis …
Read article →SPFA, in depth: queue-based Bellman-Ford, its real worst case, negative-cycle detection and when to choose it
The Shortest Path Faster Algorithm explained from first principles: why only improved vertices need rescanning, a correct implementation with hop-coun…
Read article →Subset Sum, in depth: existence and counting tables, bitsets, every target in one pass, size-k counts, undoing an item and the pseudo-polynomial wall
Subset sum from first principles: the boolean and counting dynamic programs, why the inner loop runs backwards, a big-integer bitset, counting under a…
Read article →Suffix Arrays, in depth: prefix doubling in code, SA-IS in outline, pattern search, LCP-powered queries and the BWT connection
Suffix arrays from first principles: the banana example, why naive sorting is quadratic, prefix doubling with sort and radix versions in tested Python…
Read article →Symmetric Tree Check, in depth: the mirror invariant, recursive and iterative solutions, traps that look correct, and checking every subtree in linear time
How to decide whether a binary tree is a mirror image of itself: the pair-based invariant, recursive and queue-based code in Python and Java, a pair-b…
Read article →Target Sum, in depth: from 2^n sign assignments to a subset-sum count, with the offset table, the parity rule, zeros, reconstruction and meet in the middle
How to count the ways to put + or - in front of each number so the total equals a target: brute force as a reference, memoised recursion, the offset t…
Read article →Tarjan's SCC, in depth: low-links, the on-stack rule, an iterative implementation and what the condensation buys you
Strongly connected components of a directed graph in one depth-first search: discovery indices and low-links from first principles, why the on-stack c…
Read article →Topological Sort, in depth: the Kahn algorithm as a live scheduler, with priorities, retries and failure propagation
The Kahn algorithm run as a DAG executor rather than a sort: the task state machine, event-driven dispatch versus level barriers, critical-path priori…
Read article →Topological Sort, in depth: batch versus online, and keeping an order valid as edges arrive with Pearce-Kelly
The two ways software needs a topological order: once, over a finished graph (Kahn or DFS), or continuously, while edges keep arriving. A compact batc…
Read article →Traveling Salesman Problem
Bitmask DP: O(2^N × N²) beats brute-force O(N!). Subset enumeration, state definition, recurrence, and the exact boundary where approximation takes ov…
Read article →Treap, in depth: a binary search tree balanced by random priorities, with split, merge, order statistics and implicit keys
How a treap works and how to implement one: the BST and heap invariants, why random priorities give expected O(log n) depth, split and merge as the tw…
Read article →Tree Isomorphism Check, in depth: AHU canonical ids, centres for free trees and subtree hashing
How to decide whether two trees are isomorphic: rooted versus free and ordered versus unordered trees, why canonical strings are quadratic, the AHU al…
Read article →Trie, in depth: bitwise tries, longest-prefix match for IP routing, multibit strides, HAMT bitmap nodes and the lock-free Ctrie
Tries over bits rather than characters: longest-prefix match with a working binary trie and worked routing example, why one bit per level is slow, mul…
Read article →Trie (Prefix Tree), in depth: building a ranked, typo-tolerant autocomplete with best-first top-k, Levenshtein pruning and snapshot builds
Use a trie as the engine of a real autocomplete service: normalised keys, subtree-maximum scores, best-first top-k search with a heap, a worked trace,…
Read article →Union-Find Variants, in depth: potential DSU, component aggregates, movable elements, next-free slots and offline dynamic connectivity
Five union-find variants built and run: potential (offset) DSU with contradiction detection and the compression-order trap, per-component aggregates a…
Read article →Word Search
Word search on a 2D grid: why the no-revisit constraint kills memoisation, in-place marking vs a visited bitmask, the 3^L bound, frequency and reversa…
Read article →Z-Algorithm, in depth: the Z-box invariant, a linear-time proof, pattern search in O(m) memory, periods and the prefix function
How the Z-algorithm computes the Z-array in linear time: the definition, the Z-box and its clamp, the amortised proof, a full hand trace, tested Pytho…
Read article →