A reference collection of classic algorithms implemented in C++. Each file is self-contained: include the headers, compile with g++ -std=c++17 file.cpp -o out, and run.
Companion YouTube playlist: https://www.youtube.com/playlist?list=PLVJxzz1cOIRH-bsmJzXQxGb3HXgRTd2Jb
- General — number-theory and arithmetic building blocks
- Searching — array search and string pattern matching
- Sorting — comparison and non-comparison sorts
- Graph — traversal, shortest paths, MST, ordering, connectivity
- Dynamic Programming — classic DP problems
In the tables below, n is the input size, V and E are graph vertex/edge counts, m and n are string lengths for string algorithms, W is a knapsack capacity, and k is the alphabet/bucket size.
| # | Algorithm | Time | Space | File |
|---|---|---|---|---|
| 1 | GCD (Euclidean) | O(log min(a,b)) | O(1) | GCD.cpp |
| 2 | LCM | O(log min(a,b)) | O(1) | LCM.cpp |
| 3 | Iterative Factorial | O(n) | O(1) | Iterative Factorial.cpp |
| 4 | Recursive Factorial | O(n) | O(n) stack | Recursive Factorial.cpp |
| 5 | Fibonacci (Iterative) | O(n) | O(1) | Fibonacci Iterative.cpp |
| 6 | Fibonacci (Recursive) | O(2^n) | O(n) stack | Fibonacci Recursive.cpp |
| 7 | Power (naive) | O(n) | O(1) | Power.cpp |
| 8 | Power (iterative fast) | O(log n) | O(1) | Power Iterative.cpp |
| 9 | Power (recursive fast) | O(log n) | O(log n) | Power Recursive.cpp |
| 10 | Sum of Powers | O(n log k) | O(1) | Sum Powers.cpp |
| 11 | Factors of n | O(√n) | O(d(n)) | Factors.cpp |
| 12 | Prime Check | O(√n) | O(1) | Prime Numbers.cpp |
| 13 | Sieve of Eratosthenes | O(n log log n) | O(n) | Sieve.cpp |
| 14 | Modular Exponentiation | O(log e) | O(1) | Modular Exponentiation.cpp |
| 15 | Extended Euclidean | O(log min(a,b)) | O(log min(a,b)) | Extended Euclidean.cpp |
| 16 | Modular Inverse | O(log m) | O(1) | Modular Inverse.cpp |
| 17 | Miller-Rabin Primality | O(k log³ n) | O(1) | Miller Rabin.cpp |
| 18 | Segmented Sieve | O((R-L+√R) log log R) | O(R-L+√R) | Segmented Sieve.cpp |
| # | Algorithm | Time | Space | File |
|---|---|---|---|---|
| 1 | Linear Search | O(n) | O(1) | 01- Linear Search.cpp |
| 2 | Binary Search | O(log n) | O(1) | 02- Binary Search.cpp |
| 3 | Modified Binary Search (first/last occurrence) | O(log n) | O(1) | 03- Modified Binary Search.cpp |
| 4 | KMP Pattern Matching | O(n + m) | O(m) | 04- KMP Searching Pattern.cpp |
| 5 | Rabin-Karp | O(n + m) avg, O(nm) worst | O(1) | 05- Rabin Karp Algorithm.cpp |
| 6 | Ternary Search | O(log₃ n) | O(1) | 06- Ternary Search.cpp |
| 7 | Jump Search | O(√n) | O(1) | 07- Jump Search.cpp |
| 8 | Exponential Search | O(log n) | O(1) | 08- Exponential Search.cpp |
| 9 | Z-Algorithm | O(n + m) | O(n + m) | 09- Z Algorithm.cpp |
Notes. Binary, ternary, jump, and exponential search require a sorted input. KMP and Z-algorithm both achieve linear pattern matching; Z computes a length-array useful for many string problems beyond plain matching. Rabin-Karp is the right tool when you want to match many patterns at once via rolling hash.
| # | Algorithm | Time (avg) | Time (worst) | Space | Stable | File |
|---|---|---|---|---|---|---|
| 1 | Selection Sort | O(n²) | O(n²) | O(1) | No | 01- Selection Sort.cpp |
| 2 | Insertion Sort | O(n²) | O(n²) | O(1) | Yes | 02- Insertion Sort.cpp |
| 3 | Bubble Sort | O(n²) | O(n²) | O(1) | Yes | 03- Bubble Sort.cpp |
| 4 | Heap Sort | O(n log n) | O(n log n) | O(1) | No | 04- Heap Sort.cpp |
| 5 | Merge Sort | O(n log n) | O(n log n) | O(n) | Yes | 05- Merge Sort.cpp |
| 6 | Quick Sort | O(n log n) | O(n²) | O(log n) | No | 06- Quick Sort.cpp |
| 7 | Counting Sort | O(n + k) | O(n + k) | O(n + k) | Yes | 07- Count Sort.cpp |
| 8 | Shell Sort | O(n log² n) | O(n²) | O(1) | No | 08- Shell Sort.cpp |
| 9 | Radix Sort | O(d·(n + k)) | O(d·(n + k)) | O(n + k) | Yes | 09- Radix Sort.cpp |
| 10 | Bucket Sort | O(n + k) | O(n²) | O(n + k) | Yes | 10- Bucket Sort.cpp |
Picking a sort. For general-purpose work use merge or quick sort. For integer keys with bounded range use counting/radix. Insertion sort is preferred for small or nearly-sorted inputs (and is the base case inside many hybrid sorts).
| # | Algorithm | Time | Space | File |
|---|---|---|---|---|
| 1 | Depth-First Search | O(V + E) | O(V) | 01- Depth First Search.cpp |
| 2 | Breadth-First Search | O(V + E) | O(V) | 02- Breadth First Search.cpp |
| 3 | Dijkstra (matrix) | O(V²) | O(V²) | 03- Dijkstra Using Matrix Representation.cpp |
| 4 | Dijkstra (adj list + heap) | O((V+E) log V) | O(V + E) | 04- Dijkstra Using List Representation.cpp |
| 5 | Dijkstra with path reconstruction | O((V+E) log V) | O(V + E) | 05- Printing Path in Dijkstra's Algorithm.cpp |
| 6 | Bellman-Ford | O(V·E) | O(V) | 06- Bellman Ford Algorithm.cpp |
| 7 | SPFA (Bellman-Ford queue variant) | O(V·E) worst, faster avg | O(V) | 07- Shortest Path Faster Algorithm.cpp |
| 8 | Floyd-Warshall (all-pairs) | O(V³) | O(V²) | 08- Floyd-Warshall Algorithm.cpp |
| 9 | Kruskal MST | O(E log E) | O(V) | 09- Kruskal's Algorithm(MSP).cpp |
| 10 | Prim MST | O((V+E) log V) | O(V + E) | 10- Prim's Algorithm (MSp).cpp |
| 11 | Topological Sort | O(V + E) | O(V) | 11- Topological Sorting.cpp |
| 12 | Union-Find (DSU) | O(α(n)) per op | O(n) | 12- Union Find.cpp |
| 13 | Tarjan SCC | O(V + E) | O(V) | 13- Tarjan SCC.cpp |
| 14 | Kosaraju SCC | O(V + E) | O(V) | 14- Kosaraju SCC.cpp |
| 15 | Articulation Points & Bridges | O(V + E) | O(V) | 15- Articulation Points and Bridges.cpp |
| 16 | 0-1 BFS | O(V + E) | O(V) | 16- 0-1 BFS.cpp |
Picking a shortest-path algorithm.
- Non-negative weights, single source → Dijkstra
- Edges weighted only 0 or 1 → 0-1 BFS (a deque-based Dijkstra)
- Negative weights, single source → Bellman-Ford (also detects negative cycles); SPFA is the same idea but faster in practice on sparse graphs
- All pairs, dense graph → Floyd-Warshall
| # | Algorithm | Time | Space | File |
|---|---|---|---|---|
| 1 | Fibonacci (memoized) | O(n) | O(n) | 01- Fibonacci.cpp |
| 2 | Rod Cutting | O(n²) | O(n) | 02- Rod Cutting.cpp |
| 3 | Maximum Subarray (Kadane) | O(n) | O(1) | 03- Maximum Subarray.cpp |
| 4 | LCS — length only | O(mn) | O(mn) | 04- Longest Common Subsequence.cpp |
| 5 | LCS — reconstruct sequence | O(mn) | O(mn) | 05- Longest Common Subsequence.cpp |
| 6 | Minimum Edit Distance (Levenshtein) | O(mn) | O(mn) | 06- Minimum Edit Distance.cpp |
| 7 | Subset Sum | O(n·S) | O(n·S) | 07- Subset Sum.cpp |
| 8 | 0/1 Knapsack | O(nW) | O(nW) | 08- Knapsack Problem.cpp |
| 9 | Longest Increasing Subsequence | O(n log n) | O(n) | 09- Longest Increasing Subsequence.cpp |
| 10 | Matrix Chain Multiplication | O(n³) | O(n²) | 10- Matrix Chain Multiplication.cpp |
| 11 | Maximum Path in Grid | O(rc) | O(rc) | 11- Maximum Path In Grid.cpp |
| 12 | Coin Change — min coins | O(n·A) | O(A) | 12- Coin Change Min.cpp |
| 13 | Coin Change — count ways | O(n·A) | O(A) | 13- Coin Change Ways.cpp |
| 14 | Egg Drop | O(n·k²) | O(n·k) | 14- Egg Drop.cpp |
| 15 | Palindrome Partitioning (min cuts) | O(n²) | O(n²) | 15- Palindrome Partitioning.cpp |
| 16 | Catalan Numbers | O(n²) | O(n) | 16- Catalan Numbers.cpp |
| 17 | Longest Palindromic Subsequence | O(n²) | O(n²) | 17- Longest Palindromic Subsequence.cpp |
g++ -std=c++17 -O2 -Wall path/to/file.cpp -o out
./outEach file has a main() with a small example demonstrating the algorithm. Modify the inputs at the top of main() to experiment.
- C++17, no external dependencies
- One algorithm per file
- File header comment states: problem, approach, complexity
main()runs a small demo and prints the result
This repository is intended for educational/reference use.