Blog

In a directed graph, which groups of nodes can all reach each other? How two depth-first searches — one on the graph, one on its reverse — find every strongly connected component in linear time, why the finish order is the trick, and where SCCs show up: dependency cycles, 2-SAT, and condensing a graph into a DAG.

The maximum of every window of size k in an array, in O(n) instead of O(n·k). How a deque of indices with decreasing values throws away elements that can never win, why every element is pushed and popped at most once, and where the same idea shows up.

Pick items with weights and values to maximise value without going over a capacity, using each at most once. Why greedy fails, how a table of 'best value with these items and this capacity' solves it, how to recover the chosen items, and the one-array version that iterates backwards.

The fewest inserts, deletes and substitutions to turn one word into another. How the Levenshtein distance is computed with a small DP table, how to recover the actual edits, and where it's used — from 'did you mean' to fuzzy search and DNA alignment.

Dijkstra answers 'how far from here to everywhere'. Floyd–Warshall answers 'how far from everywhere to everywhere' — with three nested loops and one table. How the via-vertex idea works, how to rebuild the paths, and when it beats running Dijkstra many times.

Find the contiguous slice of an array with the largest sum — in O(n) time and O(1) memory. Why a negative running sum should always be dropped, how to recover the slice itself, and how the same idea solves stock prices, circular arrays and products.

A hash function maps any input to a fixed-size number, the same input always to the same number. How a simple one works, why collisions are unavoidable, what makes a hash good, and how the same idea powers hash maps, caches and passwords.

Compare a fingerprint of each window instead of the window itself — and update that fingerprint in O(1) as the window slides. The string-matching algorithm that also powers plagiarism detection, rsync, and content-defined chunking.

Dijkstra locks in a node the moment it's popped, which is exactly what breaks when an edge weight is negative. Bellman-Ford gives up that greed, relaxes every edge V − 1 times, and can tell you when no shortest path exists at all.

Quicksort recurses into both halves. Quickselect recurses into one — and that single change drops the expected cost from O(n log n) to O(n). How it works, why it's linear, and when a heap is the better call.