Paradigms

Four ways of attacking a problem: split it in half, take the best-looking step, try everything but back out of dead ends, or remember answers to smaller problems. Each one has a live visualizer running the real code.

1. 01Counting inversionsDivide and conquer: count out-of-order pairs while merge sort puts them right.O(n log n)
2. 02Greedy coin changeAlways take the biggest coin that fits, and see when that fails.O(k log k)
3. 03Jump gameGreedy: track the furthest reachable point to decide if the end is reachable.O(n)
4. 04Subset sumBacktracking: choose or skip each value, and back out of choices that overshoot.O(2ⁿ)
5. 05N-QueensBacktracking: place queens row by row, undoing any that clash.O(n!)
6. 06House robberDynamic programming: the best total up to each house, from the two before it.O(n)
7. 07Longest common subsequenceDynamic programming on a grid: the longest shared run of letters in order.O(n · m)
8. 080/1 knapsackDynamic programming: the best value for every capacity, one item at a time.O(n · W)