My library of competitive-programming algorithms, with C++ implementations and Python ports based on the same techniques.
Each algorithm has its own directory containing:
README.md: algorithm, solution approach, complexity, usage, and C++ review notes.<Algorithm>.cpp: C++ implementation.<Algorithm>.py: Python implementation.test_<Algorithm>.pyandtest_<Algorithm>.cpp: reference checks and regression tests.
| Directory | Algorithm |
|---|---|
| Backtracking | Subsets, permutations, combinations, and N-Queens |
| BellmanFord | Bellman–Ford shortest paths and negative cycles |
| BFS | Breadth-first search |
| BigNumbers | Unsigned big integers |
| BinSearch | Binary search on a predicate |
| BitmaskDP | DP over subsets: Held–Karp, k-partition, all-nodes BFS |
| BitTricks | Bit manipulation identities and submask enumeration |
| Bridges | Bridges and articulation points |
| BST | Binary search tree |
| Cache | LRU and LFU caches |
| ClassicDP | House robber, coin change, grid paths, and word break |
| DFS | Depth-first search |
| Dijkstra | Dijkstra's shortest paths |
| EditDistance | Levenshtein distance with operation reconstruction |
| Fenwick | Fenwick tree (binary indexed tree) |
| FindAndUnion | Disjoint-set union |
| FloydWarshall | Floyd–Warshall all-pairs shortest paths |
| GCD | GCD and extended Euclid |
| Hashing | Double polynomial hashing |
| Heap | Binary min and max heaps |
| HeapSort | Heap sort |
| Intervals | Merging, inserting, and scheduling intervals |
| KMP | Knuth-Morris-Pratt prefix function |
| KMR | Karp-Miller-Rosenberg ranks and suffix arrays |
| Kruskal | Kruskal's minimum spanning forest |
| LCA | Lowest common ancestor |
| LCS | Longest common subsequence |
| LinkedList | Linked list reversal, merging, and Floyd cycle detection |
| LIS | Longest increasing subsequence |
| Manacher | Manacher's palindrome radii |
| MergeSort | Merge sort |
| Mo | Mo's algorithm for distinct counts |
| Modulo | Modular arithmetic |
| MonoQueue | Monotone maximum queue |
| MonoStack | Monotonic stack: next greater/smaller and histograms |
| Palindromes | Palindromic substrings, subsequences, and partitions |
| PrefixSum | Prefix sums, 2D sums, and difference arrays |
| Prim | Prim's minimum spanning forest |
| QuickSelect | Quickselect k-th element and top-k |
| QuickSort | Quicksort |
| SCC | Strongly connected components (Kosaraju) |
| Sieve | Linear sieve and smallest prime factors |
| SlidingWindow | Variable-size sliding window |
| SparseTable | Static range minimum sparse table |
| TopologicalSort | Topological sort with cycle detection |
| TreeDP | Tree DP: diameter, path sums, and rerooting |
| TreePointSegment | Point assignment / range maximum |
| TreeSegmentPoint | Range addition / point lookup |
| TreeSegmentSegment | Range addition / range sum |
| Trie | Trie / prefix tree |
| TwoPointers | Two-pointer scans on sorted arrays |
| UnboundedKnapsack | Unbounded knapsack |
| ZeroOneBFS | 0–1 BFS shortest paths |
| ZeroOneKnapsack | Zero-one knapsack |
Python 3.10+ and the standard library are sufficient; no third-party packages are required. Run from the repository root:
python3 run_tests.py
python3 run_tests.py --cppThe second command also requires g++ with C++17 support. It compiles all C++ implementations independently and runs all C++ tests with UndefinedBehaviorSanitizer, placing build products in a temporary directory. Python tests use deterministic randomized inputs and simple reference solutions where appropriate.
With Nix, obtain the tools without a global installation:
nix shell nixpkgs#python3 nixpkgs#gcc --command python3 run_tests.py --cppTo run only one Python suite:
python3 -m unittest discover -s QuickSort -t . -p 'test_*.py'Python graph vertices and array positions are zero-based. Range queries are inclusive for Mo and segment trees; string hash and KMR ranges are half-open. Each README explains the equivalent C++ indexing and initialization. The newer TopologicalSort, SCC, ZeroOneBFS, BellmanFord, Bridges, and Prim snippets also use zero-based C++ vertices and dynamic storage; UnboundedKnapsack, LCS, Palindromes, HeapSort, and BST use zero-based dynamic storage. SparseTable uses zero-based inclusive bounds in both languages. The LeetCode pattern snippets (SlidingWindow, TwoPointers, PrefixSum, MonoStack, Backtracking, Intervals, ClassicDP, EditDistance, Fenwick, QuickSelect, Cache, LinkedList, BitTricks, BitmaskDP, TreeDP, and FloydWarshall) are zero-based with dynamic storage; Fenwick and 1D PrefixSum ranges are half-open, while 2D PrefixSum rectangles and difference-array updates are inclusive, and each README states its interval conventions. Algorithms expect inputs satisfying their documented assumptions.
C++ files retain their original competitive-programming interfaces and fixed-capacity arrays where applicable. Files with a demo/input main can be compiled as programs; other files are reusable snippets. C++ regressions include each snippet in its own translation unit to avoid collisions between global names.
Correctness fixes cover quicksort pivot placement, duplicate union sizes, LCA parent traversal, knapsack input/output and memory, Mo query input and interval movement, substring hashing/comparison, and consistent segment-tree semantics. DFS, LCA, and quicksort avoid unbounded call-stack depth. See individual READMEs for details.