~/algos

All topics

Each page follows the same shape: when to reach for it, the idea, a graphic you can step through, tested code, and the mistakes people make.

01

Searching & scanning

Squeeze a linear scan down to one pass, or a search down to log n.

  1. Binary search Find a value in a sorted array by halving the range on every look. A million elements take at most 20 looks. O(log n)
  2. Two pointers Find two values that add up to a target in a sorted array with one pass from both ends. O(n) time, no extra memory. O(n)
  3. Sliding window Find the best contiguous stretch of an array or string in one pass: grow a window on the right, shrink it from the left. O(n)
  4. Monotonic stack Find each element's nearest bigger (or smaller) neighbour in one pass, with a stack that stays sorted. O(n)
  5. Prefix sums Add up an array once, left to right. After that, the sum of any range is one subtraction. O(n) to build, O(1) per query
  6. Binary search on the answer When you can check a guess but can't compute the answer directly, binary search over the guesses for the first one that works. O(n log m): log m checks of O(n) each
  7. Intervals Sort ranges by where they start, then sweep once: each range either joins the one before it or starts a new one. O(n log n)
  8. Greedy algorithms Make the choice that looks best right now and never undo it. Works when you can prove that choice is always safe. O(n log n)
02

Data structures

The containers that make the fast algorithms possible.

  1. Hash maps Store and find values by key in constant time on average. The workhorse behind counting, two sum and grouping. O(1) average per operation, O(n) worst case
  2. Linked lists Reverse a linked list in place with three pointers, then reuse the same habits: a dummy head, and fast and slow pointers. O(n)
  3. Heaps (priority queues) Always know the smallest item, even while items keep arriving. Push and pop in O(log n), peek in O(1). O(log n) push and pop, O(1) peek
  4. Trie (prefix tree) A tree of letters where words that share a start share nodes. Checking a word or a prefix takes one step per letter. O(L) per operation, L = word length
  5. Union-find Track which items belong together as you merge groups. Both merging and asking "same group?" take almost constant time. O(α(n))
  6. LRU cache A fixed-size cache that throws out whatever was used longest ago. A hash map plus a doubly linked list make get and put O(1). O(1) per get or put
  7. Fenwick tree (binary indexed tree) Prefix sums that survive updates: change one element or sum any prefix in O(log n), with an array and ten lines of code. O(log n) per update or query, O(n log n) to build
  8. Segment tree Answer range questions like "sum of a[l..r]" while the array keeps changing. Both updates and queries take O(log n). O(log n) per update and query, O(n) to build
03

Graphs

Grids, networks, dependencies: anything with things and links between them.

  1. Binary trees and traversals Visit every node of a binary tree in preorder, inorder, postorder or level order, with recursion, a stack or a queue. O(n)
  2. BFS and DFS The two ways to walk a graph. BFS spreads out in rings and finds fewest-edge paths; DFS dives down one path and backs up. O(V + E)
  3. Bipartite graphs (2-colouring) Can the nodes be split into two sides so every edge crosses between them? Colour them with BFS and watch for a clash. O(V + E)
  4. Cycle detection Find out whether a directed graph loops back on itself: DFS with three colours spots the edge that closes a cycle. O(V + E)
  5. Topological sort Put the nodes of a directed graph in an order where every edge points forward, or find out that a cycle makes it impossible. O(V + E)
  6. Dijkstra's algorithm Shortest paths from one source when edge weights are never negative. Always finish the closest unfinished node next. O((V + E) log V)
  7. Minimum spanning tree Connect every node of a weighted graph as cheaply as possible. Kruskal takes the lightest edges first and skips any that close a cycle. O(E log E)
04

Dynamic programming

Solve each subproblem once, remember it, build up the answer.

  1. Dynamic programming: the basics Solve each small subproblem once, store the answer, and build bigger answers from it. Learned here on House Robber. O(states × work per state), O(n) for House Robber
  2. Grid paths The cheapest route across a grid when you can only move right or down: each cell takes the better of the cell above and the one to its left. O(rows·cols)
  3. 0/1 knapsack Pick items with the most total value that fit under a weight limit, each item at most once, by filling a table of item × capacity. O(n·W)
  4. Longest increasing subsequence The longest run of values that only go up, picked in order from an array. O(n²) with a simple DP, O(n log n) with binary search. O(n log n), or O(n²) for the plain DP
  5. Edit distance The fewest single-letter inserts, deletes and replacements that turn one word into another, from a table over prefix pairs. O(n·m)
  6. Interval DP Solve a problem for every substring or subarray, shortest first, so each range is built from the smaller ranges inside it. O(n²) when a cell looks at its ends, O(n³) when it tries every split point
esc