Data Structures & Algorithms Roadmap¶
- Roadmap: https://roadmap.sh/datastructures-and-algorithms
1. Pick a Language¶
- 1.1 JavaScript
- 1.2 Java
- 1.3 Go
- 1.4 C#
- 1.5 C++
- 1.6 Python
- 1.7 Rust
- 1.8 Ruby
01. Introduction to DSA¶
What DSA is, why it matters, how to study it, how problems map to data structures.
02. Programming Fundamentals¶
03. What are Data Structures?¶
04. Why are Data Structures Important?¶
05. Basic Data Structures¶
- 5.1 Array
- 5.2 Linked Lists
- 5.3 Queues
- 5.4 Stacks
- 5.5 Hash Tables
- 5.6 Set
- 5.7 Multiset / Bag
- 5.8 Map / Dictionary
- 5.9 Deque
- 5.10 Two Pointers
- 5.11 Sliding Window
- 5.12 Prefix Sums & Difference Arrays
- 5.13 Monotonic Stack
- 5.14 Monotonic Queue
- 5.15 Floyd's Cycle Detection (Tortoise & Hare)
- 5.16 MEX (Minimum Excludant)
06. Algorithmic Complexity¶
6.1 Time vs Space Complexity¶
6.2 How to Calculate Complexity?¶
6.3 Common Runtimes¶
6.4 Asymptotic Notation¶
07. Sorting Algorithms¶
- 7.1 Bubble Sort
- 7.2 Merge Sort
- 7.3 Insertion Sort
- 7.4 Quick Sort
- 7.5 Selection Sort
- 7.6 Heap Sort
- 7.7 Counting Sort
- 7.8 Radix Sort
- 7.9 Bucket Sort
- 7.10 Shell Sort
- 7.11 Tim Sort
- 7.12 Intro Sort
08. Search Algorithms¶
- 8.1 Linear Search
- 8.2 Binary Search
- 8.3 Ternary Search
- 8.4 Newton's Method
- 8.5 Binary Search on Answer
- 8.6 Jump Search
- 8.7 Interpolation Search
- 8.8 Exponential Search
- 8.9 Fibonacci Search
09. Trees¶
- 9.1 Binary Tree
- 9.2 Binary Search Tree (BST)
- 9.3 AVL Tree
- 9.4 Red-Black Tree
- 9.5 Trie
- 9.6 Segment Tree
- 9.7 Fenwick Tree (BIT)
- 9.8 B-Tree
- 9.9 Sparse Table (RMQ)
- 9.10 Sqrt Decomposition / Mo's Algorithm
- 9.11 B+ Tree
- 9.12 Interval Tree
- 9.13 Quadtree / Octree
- 9.14 R-Tree
10. Heaps & Priority Queues¶
- 10.1 Binary Heap
- 10.2 Priority Queue
- 10.3 Fibonacci Heap
- 10.4 D-Ary Heap
- 10.5 Binomial Heap
- 10.6 Pairing Heap
- 10.7 Leftist Heap
- 10.8 Skew Heap
11. Graphs¶
- 11.1 Representation (matrix, list)
- 11.2 BFS
- 11.3 DFS
- 11.4 Dijkstra
- 11.5 Bellman-Ford
- 11.6 Floyd-Warshall
- 11.7 Topological Sort
- 11.8 Tarjan's SCC
- 11.9 A* Search
- 11.10 Minimum Spanning Tree (Kruskal, Prim)
- 11.11 Articulation Points & Bridges
- 11.12 Eulerian Path / Circuit
- 11.13 LCA (Lowest Common Ancestor)
- 11.14 Heavy-Light Decomposition
- 11.15 Centroid Decomposition
- 11.16 Max Flow (Edmonds-Karp / Dinic)
- 11.17 Max Flow (Push-Relabel)
- 11.18 Min-Cost Max-Flow
- 11.19 Bipartite Matching
- 11.20 2-SAT
- 11.21 Small-to-Large Merging
- 11.22 0-1 BFS
- 11.23 Edge / Vertex Connectivity
- 11.24 Kirchhoff Theorem
- 11.25 Prüfer Code
- 11.26 Strong Orientation
- 11.27 Graph Coloring
- 11.28 NP-Hard: TSP & Hamiltonian
- 11.29 Planar Graph Faces
- 11.30 Online Bridge Finding
- 11.31 Second-Best MST
- 11.32 Paths of Fixed Length (Matrix Exp on Graphs)
12. Disjoint Set (Union-Find)¶
13. Dynamic Programming¶
- 13.1 Memoization vs Tabulation
- 13.2 Knapsack (0/1, unbounded)
- 13.3 LCS / LIS
- 13.4 Edit Distance
- 13.5 Interval DP
- 13.6 Bitmask DP
- 13.7 Tree DP
- 13.8 Digit DP
- 13.9 SOS DP
- 13.10 Convex Hull Trick / Li Chao Tree
- 13.11 Divide & Conquer Optimization
- 13.12 Knuth's Optimization
- 13.13 Profile DP
- 13.14 Nim
- 13.15 Sprague-Grundy Theorem
- 13.16 Minimax & Alpha-Beta
- 13.17 Game DP
- 13.18 Josephus Problem
- 13.19 Coin Change
- 13.20 Matrix Chain Multiplication
- 13.21 Rod Cutting
- 13.22 Subset Sum / Partition
- 13.23 Word Break
- 13.24 Egg Dropping
- 13.25 Kadane's Algorithm (Max Subarray Sum)
- 13.26 Games on Arbitrary Graphs
14. Greedy Algorithms¶
- 14.1 Activity Selection
- 14.2 Huffman Coding
- 14.3 Fractional Knapsack
- 14.4 Job Scheduling
- 14.5 Exchange Argument
- 14.6 Interval Scheduling Variations
- 14.7 Set Cover Approximation
- 14.8 Vertex Cover Approximation
15. Divide & Conquer¶
- 15.1 Merge Sort
- 15.2 Quicksort
- 15.3 Master Theorem
- 15.4 Karatsuba Multiplication
- 15.5 FFT
- 15.6 Meet in the Middle
16. Backtracking¶
- 16.1 N-Queens
- 16.2 Sudoku Solver
- 16.3 Permutations & Subsets
- 16.4 Constraint Satisfaction
- 16.5 Rat in Maze
- 16.6 Knight's Tour
- 16.7 Word Search
- 16.8 Branch and Bound
- 16.9 15-Puzzle Solvability
17. String Algorithms¶
- 17.1 KMP
- 17.2 Z-Function
- 17.3 Rabin-Karp
- 17.4 Suffix Arrays
- 17.5 Aho-Corasick
- 17.6 Edit Distance
- 17.7 Tries (string-focused)
- 17.8 Boyer-Moore
- 17.9 Boyer-Moore-Horspool
- 17.10 Burrows-Wheeler Transform
- 17.11 Manacher's Algorithm
- 17.12 Suffix Automaton
- 17.13 Suffix Tree (Ukkonen)
- 17.14 Palindromic Tree (Eertree)
- 17.15 Lyndon Decomposition
- 17.16 Expression Parsing (Shunting Yard)
18. Bit Manipulation¶
- 18.1 Bit Tricks
- 18.2 XOR Pairing
- 18.3 Bitmask Enumeration
- 18.4 Bit-Parallel Algorithms
- 18.5 Gosper's Hack & Gray Code
19. Number Theory¶
- 19.1 GCD / LCM
- 19.2 Modular Arithmetic
- 19.3 Prime Sieves
- 19.4 Fermat's Little Theorem / Euler's Totient
- 19.5 Chinese Remainder Theorem (CRT)
- 19.6 Extended Euclidean & Modular Inverse
- 19.7 Linear Diophantine
- 19.8 Miller-Rabin Primality
- 19.9 Pollard's Rho Factorization
- 19.10 Matrix Exponentiation
- 19.11 Discrete Log (BSGS)
- 19.12 Primitive Root & Discrete Root
- 19.13 NTT
- 19.14 Montgomery Multiplication
- 19.15 Garner's Algorithm
- 19.16 Continued Fractions
- 19.17 Gaussian Elimination
- 19.18 Matrix Determinant
- 19.19 Matrix Rank
- 19.20 Polynomial Operations
- 19.21 Binomial Coefficients
- 19.22 Catalan Numbers
- 19.23 Inclusion-Exclusion
- 19.24 Burnside / Pólya
- 19.25 Stars and Bars
- 19.26 Binary Exponentiation
- 19.27 Arbitrary-Precision Arithmetic (BigInt)
- 19.28 Divisor Functions (d(n), σ(n))
- 19.29 Factorial Modulo p (Lucas, Wilson)
- 19.30 Fibonacci Numbers (Closed Form, Matrix Form)
- 19.31 Simpson's Integration
20. Computational Geometry¶
- 20.1 Convex Hull
- 20.2 Line Intersection
- 20.3 Point in Polygon
- 20.4 KD-Tree
- 20.5 Sweep Line
- 20.6 Rotating Calipers
- 20.7 Closest Pair of Points
- 20.8 Minimum Enclosing Circle
- 20.9 Pick's Theorem
- 20.10 Minkowski Sum
- 20.11 Voronoi & Delaunay
- 20.12 Half-Plane Intersection
- 20.13 Circle-Line Intersection
- 20.14 Circle-Circle Intersection
- 20.15 Common Tangents to Circles
- 20.16 Manhattan & Chebyshev Distance
21. Advanced Data Structures¶
- 21.1 LRU Cache
- 21.2 Bloom Filter
- 21.3 Skip List
- 21.4 LSM Tree
- 21.5 Merkle Tree
- 21.6 Rope
- 21.7 Sqrt Tree
- 21.8 Count-Min Sketch
- 21.9 HyperLogLog
- 21.10 Cuckoo Filter
- 21.11 Persistent Segment Tree
- 21.12 Link-Cut Tree
- 21.13 Wavelet Tree
- 21.14 Van Emde Boas Tree
- 21.15 CAS & Atomic Primitives
- 21.16 Lock-Free Queue (Michael-Scott)
- 21.17 Lock-Free Stack
- 21.18 Concurrent Hash Map
- 21.19 RCU (Read-Copy-Update)
- 21.20 Hazard Pointers
- 21.21 LFU Cache
- 21.22 ARC / 2Q Cache
- 21.23 Counting Bloom Filter
- 21.24 Patricia Trie / Radix Tree
- 21.25 Hash Array Mapped Trie (HAMT)
22. Randomized Algorithms¶
- 22.1 Reservoir Sampling
- 22.2 MinHash
- 22.3 Monte Carlo vs Las Vegas
- 22.4 Treap
- 22.5 Randomized Quicksort
- 22.6 Quickselect (k-th Order Statistic)
- 22.7 Simulated Annealing
- 22.8 Misra-Gries Heavy Hitters
- 22.9 t-Digest Quantiles
- 22.10 Locality-Sensitive Hashing
- 22.11 Space-Saving Algorithm
23. Parallel Algorithms¶
- 23.1 Models: PRAM, Work & Span
- 23.2 Parallel Prefix Sum (Scan)
- 23.3 Parallel Sorting & Merging
- 23.4 Parallel Reduce & Map
- 23.5 Parallel Graph BFS
- 23.6 MapReduce Patterns
- 23.7 Fork-Join & Work-Stealing
24. External Memory & Cache-Aware¶
- 24.1 The I/O Model
- 24.2 Cache-Oblivious Algorithms
- 24.3 External Sorting
- 24.4 B-Tree I/O Analysis
- 24.5 Cache-Aware Data Layout
25. Online Algorithms¶
- 25.1 Competitive Analysis
- 25.2 Ski Rental & Rent-or-Buy
- 25.3 Paging & Caching Theory
- 25.4 The k-Server Problem
- 25.5 Online Scheduling & Load Balancing