Blog

A sorted linked list with express lanes stacked on top. Search, insert and delete in O(log n) expected time, with no rotations and no rebalancing — just a random height for each new node. Why Redis sorted sets use one.

The array isn't sorted. There is no array. You can still binary search — as long as you can write a yes/no question whose answers flip exactly once.

The O(n²) dynamic program is the one everyone learns. The faster version keeps one array of 'best endings' and binary searches it — and the array it builds is not the answer.

Pick k items uniformly at random from a sequence of unknown length, in one pass, holding only k items. The algorithm is four lines; the proof is one induction step.

Connect every node for the least total weight. Two greedy algorithms that both work, the one theorem that explains why, and how to choose between them.

A prefix sum array answers range queries in O(1) but costs O(n) to update. A Fenwick tree makes both O(log n) using nothing but the lowest set bit of an index.

One extra term in the priority function turns an exhaustive search into a guided one. What admissible and consistent heuristics mean, why they preserve optimality, and where A* degrades.

Precompute once, answer range queries in O(1). How prefix sums work, the sentinel zero that removes every edge case, difference arrays for range updates, and the 2D version.

A stack that refuses to hold out-of-order values turns a pile of quadratic problems into linear ones. How the invariant works, why the amortised cost is O(n), and the four questions it answers.

The naive substring search re-checks characters it's already seen and degrades to O(nm) on adversarial input. The Knuth-Morris-Pratt algorithm precomputes a failure table so the search pointer never moves backward, guaranteeing O(n + m).