References

Geometry

Convex hull
- Jarvis march aka gift wrapping: O(nh). At each point, brute force find next point that is at widest angle.
- Graham scan: O(n log n). Climb the bottom-up sorted points, popping off stack any that are “internal” to most inclusive path as determined by angles. Similar to my approach of climbing bottom-up, but .
Convex hull trick: problem is find max/min of multiple linear functions at a point. Find intersections, and bsearch the x space. Construct in O(N) and query in O(N), or if sorted then query in O(log N). guide

Sorting

Common sorts: quick sort (pivot), merge sort, heapsort, insertion sort, bubble (slow)
Radix sort: whenever you are performing a dense sort of n distinct sort keys

Arrays/strings

Pattern search
- KMP: at a failed character, shift until matching. Easy to see linear time with aaaa…
- Boyer-Moore (BM): skip max(bad-char rule, good-suffix rule)
  - Bad-char rule: like KMP
  - Good-suffix rule: skip until no mismatches with haystack suffix (but can be longer)
Suffixes
- Z algorithm: compute LCP of s with all suffixes of s. O n. Can be used for pattern search by prefixing the haystack string with the query string and a delimiter. Easy to implement. Like Manacher’s. Comparable to KMP.
- Suffix trie: O(n^2) nodes/edges
- Suffix tree: more compact than suffix trie with O(n) nodes (using index labels into orig string), since largest possible tree is binary tree with 2n-1 nodes. O n construction exists in Ukkonen's algorithm, which also produces suffix links.
- Suffix array: sorted suffixes, identified by their starting indices. log n binary search queries. O n construction exists in SA-IS, under 100LOC. Closely related to and convertible with suffix tree, and are constant factor more space efficient.
  - Competitions usually just need n log n. Source, source.
- LCP (longest common prefix) array: LCP's of all adjacent suffixes from the sorted suffix array, which it can be co-constructed with. Implementation.
Longest palindrome: Manacher’s algo is like Z algorithm but growing out from centers.
Range queries: for sums, range minimum queries (RMQ), etc.
- Prefix array: simple but expensive to update
- Segment tree: just the aggregates in a binary tree. Construct in O(n), query/update in O(log n).
- Fenwick tree aka binary index tree (BIT): like segment tree but more compact/efficient, using just length N array, by removing redundant info—but assumes aggregate function is invertible (like sum can have subtraction, but not for min/max). Construct in O(n).
- Sparse tables
  - Construct in O(n log n) time and space. Cell (i,j) contains aggregation over range A[j : j + 2^i] (omit cells that would look past end of array).
  - O(log n) queries in general, but overlap-friendly aggregations (like min/max) can be O(1).
  - Read-only unlike Fenwick tree / segment tree
Problems
- Count unique substrs
- RMQ (range minimum query): find min in any subarray. Use sparse tables.
- Sliding min range query: use deque
- k-LCS: LCP array with sliding window minimum that straddles ≥ k strs (or RMQ which is easier to impl)
- Longest repeating substring : Deepest internal node in suffix tree.

Shortest paths

Dijkstra: one-to-all. $O((E+V) log V)$ with min heap
- Doesn’t handle negative edges
DP for DAG: can do just one relaxation of Bellman Ford, since topological order. $O(V+E)$
- Doesn’t handle cycles
Bellman Ford: one-to-all. Iterative relaxation DP. $O(VE)$
- Handles negative edges and cycles. Detects negative cycles: run another iteration to see if still relaxing past last iteration.
Floyd Warshall: all-to-all. Like Bellman Ford, but over all sources. Iterative relaxation DP: best(k,i,j) = best path from i to j through k at some point = min( best(k-1,i,j), best(k-1,i,k) + best(k-1,k,j) ). $O(V^3)$
- Handles negative edges and cycles.

See also

Geometry

Sorting

Arrays/strings

Shortest paths