Datastructures Algorithms Roadmap
20 sections • 498 topics
- 1. Time Complexity (Big O Notation)
- Example: Time Complexity Analysis
- 2. Space Complexity (Memory Analysis)
- Example: Space Complexity Analysis
- 3. Big O vs Big Theta vs Big Omega
- Mathematical Definitions
- Example: Notation Comparison
- 4. Best Case vs Average Case vs Worst Case
- Example: Case Analysis for Quick Sort
- 5. Amortized Analysis (Aggregate Method)
- Example: Dynamic Array Amortized Analysis
- Example: Binary Counter (Accounting Method)
- Amortized vs Worst Case
- 6. Master Theorem (Divide and Conquer Recurrence)
- Example: Applying Master Theorem
- Complexity Analysis Key Points
- 1. Array Operations (Insert, Delete, Access)
- Example: Basic Array Operations
- Example: Two Pointers Technique
- Example: Prefix Sum
- 2. 2D Arrays and Multi-dimensional Arrays
- Example: Matrix Traversal Patterns
- 3. Dynamic Arrays (ArrayList, Vector Resizing)
- Example: Dynamic Array Implementation
- 4. Sparse Arrays (Memory Optimization)
- Example: Sparse Array Implementations
- 5. Array Rotation (Left Rotation, Right Rotation)
- Example: Array Rotation
- Example: Matrix Rotation 90°
- Example: Dutch National Flag Problem
- 6. Kadane's Algorithm (Maximum Subarray Sum)
- Example: Kadane's Algorithm - Maximum Subarray Sum
- Example: Maximum Product Subarray
- Example: Subarray Sum Equals K
- Array Key Techniques Summary
- 1. Singly Linked List (Insert, Delete, Traverse)
- Example: Singly Linked List Implementation
- 2. Doubly Linked List (Bidirectional Traversal)
- Example: Doubly Linked List Implementation
- Example: LRU Cache with DLL
- When to Use Doubly Linked List
- 3. Circular Linked List (Floyd's Cycle Detection)
- Example: Floyd's Cycle Detection (Tortoise and Hare)
- Example: Circular Linked List
- 4. Skip List (Probabilistic Data Structure)
- Example: Skip List Implementation
- Skip List Key Points
- 5. Memory Pool (Linked List Implementation)
- Example: Memory Pool for Linked List Nodes
- Memory Pool Use Cases
- 6. Reverse Linked List (Iterative and Recursive)
- Example: Iterative Linked List Reversal
- Example: Reverse Between Positions
- Example: Reverse in Groups of K
- Example: Palindrome Check Using Reversal
- Linked List Key Concepts Summary
- 1. Stack Operations (Push, Pop, Peek/Top)
- Example: Basic Stack Interface
- Common Stack Applications
- Example: Balanced Parentheses
- 2. Array-based Stack Implementation
- Example: Fixed-size Array Stack
- Example: Dynamic Array Stack with Resizing
- 3. Linked List Stack (Dynamic Size)
- Example: Linked List Stack Implementation
- 4. Monotonic Stack (Next Greater Element)
- Example: Next Greater Element
- Example: Largest Rectangle in Histogram
- Example: Stock Span Problem
- 5. Expression Evaluation (Infix, Postfix, Prefix)
- Example: Postfix Expression Evaluation
- Example: Infix to Postfix Conversion
- Example: Direct Infix Evaluation
- 6. Function Call Stack and Recursion
- Example: Recursion and Call Stack Visualization
- Example: Tail Recursion Optimization
- Example: Converting Recursion to Iteration
- Example: Simulating Call Stack for Backtracking
- Stack Key Concepts Summary
- 1. Queue Operations (Enqueue, Dequeue, Front)
- Example: Queue Implementation with Array
- Example: Linked List Queue
- Common Queue Applications
- 2. Circular Queue (Ring Buffer Implementation)
- Example: Circular Queue Implementation
- Example: Overwriting Circular Buffer
- 3. Deque (Double-ended Queue Operations)
- Example: Deque Implementation with Doubly Linked List
- Example: Palindrome Checker with Deque
- Deque Use Cases
- 4. Priority Queue (Heap-based Implementation)
- Example: Min-Heap Priority Queue
- Example: Priority Queue with Custom Comparator
- Priority Queue Applications
- 5. Sliding Window (Deque Optimization)
- Example: Sliding Window Maximum
- Example: Sliding Window Minimum
- Example: First Negative in Each Window
- 6. BFS (Breadth-First Search Queue Pattern)
- Example: Binary Tree Level Order Traversal
- Example: Graph BFS Shortest Path
- Example: Multi-source BFS (Rotting Oranges)
- Example: 0-1 BFS with Deque
- Queue Key Concepts Summary
- 1. Binary Tree Traversal (Inorder, Preorder, Postorder)
- Example: All Traversal Methods (Recursive)
- Example: Iterative Traversals with Stack
- Example: Level Order Traversal
- 2. Binary Search Tree (BST Insert, Delete, Search)
- Example: BST Implementation
- Example: Validate BST
- Example: Inorder Successor
- 3. AVL Tree (Self-balancing, LL RR LR RL Rotations)
- Example: AVL Tree Node and Rotations
- 4. Red-Black Tree (Balanced Binary Search Tree)
- Example: Red-Black Tree Node Structure
- AVL vs Red-Black Comparison
- 5. B-Tree and B+ Tree (Database Indexing)
- Example: B-Tree Node Structure (Simplified)
- B+ Tree Advantages
- 6. Heap (Min Heap, Max Heap, Priority Queue)
- Example: Min Heap Implementation
- Example: Heap Sort
- Example: K Largest Elements
- 7. Trie (Prefix Tree, Autocomplete)
- Example: Trie Implementation
- Example: Word Search II (Trie + Backtracking)
- Example: Longest Common Prefix
- Trie Optimization
- 8. Segment Tree (Range Query, Range Update)
- Example: Segment Tree for Range Sum
- Example: Range Minimum Query
- Example: Lazy Propagation (Range Update)
- 9. Fenwick Tree (Binary Indexed Tree, BIT)
- Example: Fenwick Tree (BIT) Implementation
- Example: Count Inversions
- Example: Range Update Point Query
- Fenwick vs Segment Tree
- 1. Binary Tree Traversal (Inorder, Preorder, Postorder)
- Example: Serialize/Deserialize with Preorder
- Example: Level Order Serialization
- Example: BST from Preorder (No Nulls)
- 1. Binary Tree Traversal (Inorder, Preorder, Postorder)
- Example: LCA for Binary Tree (DFS)
- Example: Binary Lifting
- Example: Distance Between Nodes
- Tree Data Structures Summary
- 1. Graph Representation (Adjacency Matrix vs Adjacency List)
- Example: Graph Representations
- 2. DFS and BFS (Depth-First vs Breadth-First Search)
- Example: DFS Implementation
- Example: BFS Implementation
- 3. Dijkstra's Algorithm (Shortest Path)
- Example: Dijkstra's Algorithm
- 4. Bellman-Ford Algorithm (Negative Weight Edges)
- Example: Bellman-Ford Algorithm
- Example: Detect Negative Cycle
- When to Use Bellman-Ford
- 5. Floyd-Warshall Algorithm (All Pairs Shortest Path)
- Example: Floyd-Warshall Algorithm
- Example: Transitive Closure
- Example: Johnson's Algorithm
- All-Pairs Shortest Path Comparison
- 6. Kruskal's and Prim's Algorithm (Minimum Spanning Tree)
- Example: Kruskal's Algorithm
- Example: Prim's Algorithm
- 7. Topological Sort (Kahn's Algorithm, DFS)
- Example: Kahn's Algorithm (BFS)
- Example: DFS-based Topological Sort
- 8. Max Flow Min Cut (Ford-Fulkerson, Dinic's Algorithm)
- Example: Edmonds-Karp (Ford-Fulkerson with BFS)
- Example: Bipartite Matching using Max Flow
- Network Flow Applications
- 9. Strongly Connected Components (Tarjan's Algorithm, Kosaraju)
- Example: Tarjan's SCC Algorithm
- Example: Build Condensation Graph
- SCC Applications
- 1. Graph Representation (Adjacency Matrix vs Adjacency List)
- Example: Bipartite Matching (Augmenting Path)
- Example: Check if Bipartite (BFS 2-Coloring)
- Matching Applications
- 1. Graph Representation (Adjacency Matrix vs Adjacency List)
- Example: Min Cost Max Flow
- 1. Graph Representation (Adjacency Matrix vs Adjacency List)
- Example: Find Articulation Points and Bridges
- Applications of Articulation Points and Bridges
- 1. Graph Representation (Adjacency Matrix vs Adjacency List)
- Example: Hierholzer's Algorithm (Eulerian Circuit)
- Eulerian Path Applications
- 1. Graph Representation (Adjacency Matrix vs Adjacency List)
- Example: Hamiltonian Path (Backtracking)
- Graph Algorithms Summary
- 1. Hash Function Design (Division, Multiplication Method)
- Example: Hash Function Implementations
- 2. Collision Resolution (Separate Chaining)
- Example: Hash Table with Chaining
- Chaining Advantages
- 3. Open Addressing (Linear Probing, Quadratic Probing)
- Example: Linear Probing Hash Table
- 4. Robin Hood Hashing (Variance Reduction)
- Example: Robin Hood Hashing
- 5. Consistent Hashing (Distributed Systems)
- Example: Consistent Hashing Implementation
- Consistent Hashing Applications
- 6. Bloom Filter (Probabilistic Data Structure)
- Example: Bloom Filter Implementation
- Bloom Filter Applications
- Hashing Summary
- 1. Union Find (Disjoint Set, Path Compression)
- Example: Disjoint Set Union Find
- Union Find Applications
- 2. LRU Cache (HashMap + Doubly Linked List)
- Example: LRU Cache Implementation
- 3. Skip List (O(log n) Search)
- Example: Skip List Implementation
- Skip List Advantages
- 4. Treap (Tree + Heap, Randomized BST)
- Example: Treap Implementation
- 5. Splay Tree (Self-adjusting Binary Search Tree)
- Example: Splay Tree Implementation
- Splay Tree Applications
- 6. Rope (String Concatenation Optimization)
- Example: Rope Data Structure
- 7. Persistent Data Structures (Immutable Versions)
- Example: Persistent Array (Path Copying)
- Persistent Data Structures Applications
- 8. Lock-free Data Structures (Concurrent Programming)
- Example: Lock-free Stack (Treiber Stack)
- 9. Fibonacci Heap (Decrease Key O(1) Amortized)
- Example: Fibonacci Heap Concepts
- 1. Union Find (Disjoint Set, Path Compression)
- Example: Pairing Heap Implementation
- 1. Union Find (Disjoint Set, Path Compression)
- Example: Van Emde Boas Concepts
- 1. Union Find (Disjoint Set, Path Compression)
- Example: Suffix Tree Applications
- Suffix Tree Applications
- 1. Union Find (Disjoint Set, Path Compression)
- Example: Cartesian Tree for RMQ
- 1. Union Find (Disjoint Set, Path Compression)
- Example: Segment Tree with Lazy Propagation
- 1. Union Find (Disjoint Set, Path Compression)
- Example: Persistent Segment Tree
- Persistent Segment Tree Applications
- 1. Union Find (Disjoint Set, Path Compression)
- Example: Sparse Table for RMQ
- 1. Union Find (Disjoint Set, Path Compression)
- Example: Wavelet Tree Concepts
- Wavelet Tree Applications
- 1. Union Find (Disjoint Set, Path Compression)
- Example: Link-Cut Tree Concepts
- Advanced Data Structures Summary
- 1. Brute Force (Exhaustive Search, Try All Solutions)
- Example: Generate All Subsets (Power Set)
- 2. Divide and Conquer (Merge Sort, Quick Sort)
- Example: Merge Sort - Classic Divide and Conquer
- Example: Maximum Subarray (Divide and Conquer)
- 3. Greedy Algorithms (Activity Selection, Huffman Coding)
- Example: Activity Selection (Greedy)
- Example: Fractional Knapsack
- 4. Dynamic Programming (Memoization vs Tabulation)
- Memoization (Top-Down)
- Tabulation (Bottom-Up)
- Example: Longest Common Subsequence (LCS)
- 5. Backtracking (N-Queens, Sudoku Solver)
- Example: N-Queens Problem
- Example: Generate Parentheses
- 6. Branch and Bound (TSP Optimization)
- Example: 0/1 Knapsack Branch and Bound
- 7. Randomized Algorithms (Monte Carlo, Las Vegas)
- Example: Randomized QuickSort (Las Vegas)
- Example: Monte Carlo - Estimate Pi
- Example: Rabin-Karp with Random Hash (Monte Carlo)
- Algorithm Design Paradigms Summary
- 1. Bubble Sort and Selection Sort (O(n²) Algorithms)
- Bubble Sort Implementation
- Selection Sort Implementation
- 2. Insertion Sort (Adaptive, Online Sorting)
- Example: Insertion Sort
- Example: Binary Insertion Sort (Optimization)
- 3. Merge Sort (Stable, O(n log n) Guaranteed)
- Example: Merge Sort Implementation
- Example: In-place Merge Sort (Space Optimized)
- 4. Quick Sort (In-place, Randomized Pivot)
- Example: Quick Sort with Lomuto Partition
- Example: Randomized Quick Sort
- 5. Heap Sort (In-place, O(n log n) Worst Case)
- Example: Heap Sort Implementation
- 6. Counting Sort (Linear Time, Integer Sorting)
- Example: Counting Sort
- 7. Radix Sort (LSD, MSD, Non-comparative)
- Example: LSD Radix Sort
- Example: MSD Radix Sort
- 8. Bucket Sort (Distribution-based Sorting)
- Example: Bucket Sort
- 9. Tim Sort (Hybrid Merge-Insertion, Python Default)
- Example: TimSort (Simplified)
- 1. Bubble Sort and Selection Sort (O(n²) Algorithms)
- Example: External Merge Sort Simulation
- Sorting Algorithms Summary
- 1. Linear Search (Sequential, Unsorted Array)
- Example: Linear Search Implementations
- 2. Binary Search (Sorted Array, O(log n))
- Iterative Binary Search
- Recursive Binary Search
- Example: Binary Search Variants
- 3. Interpolation Search (Uniformly Distributed Data)
- Example: Interpolation Search
- 4. Exponential Search (Unbounded Binary Search)
- Example: Exponential Search
- Example: Unbounded Array Search
- 5. Ternary Search (Unimodal Function Optimization)
- Example: Ternary Search for Maximum
- Example: Ternary Search on Discrete Array
- 6. Jump Search (Block-based, O(√n))
- Example: Jump Search Implementation
- Example: Jump Search Comparison with Binary Search
- Search Algorithms Summary
- 1. Naive Pattern Matching (Brute Force O(mn))
- Example: Naive Pattern Matching
- 2. KMP Algorithm (Knuth-Morris-Pratt, Failure Function)
- Example: KMP Algorithm
- 3. Rabin-Karp Algorithm (Rolling Hash, Multiple Patterns)
- Example: Rabin-Karp Algorithm
- Example: Multiple Pattern Matching with Rabin-Karp
- 4. Z Algorithm (Linear Time Pattern Matching)
- Example: Z Algorithm
- 5. Boyer-Moore Algorithm (Bad Character, Good Suffix)
- Example: Boyer-Moore (Bad Character Heuristic)
- 6. Aho-Corasick Algorithm (Multiple Pattern Search)
- Example: Aho-Corasick Algorithm
- 7. Manacher's Algorithm (Longest Palindromic Substring O(n))
- Example: Manacher's Algorithm
- Example: Find All Palindromes with Manacher
- 8. Suffix Array (String Search, O(n log n) Construction)
- Example: Suffix Array (Simple Construction)
- Example: Pattern Search using Suffix Array
- 9. Edit Distance (Levenshtein Distance, Dynamic Programming)
- Example: Edit Distance (Levenshtein)
- Example: Edit Distance with Path Reconstruction
- 1. Naive Pattern Matching (Brute Force O(mn))
- Example: Trie with Autocomplete
- String Algorithms Summary
- 1. Prime Numbers (Sieve of Eratosthenes, Sieve of Atkin)
- Example: Sieve of Eratosthenes
- Example: Prime Factorization using Sieve
- 2. GCD and LCM (Euclidean Algorithm)
- GCD - Euclidean Algorithm
- LCM - Least Common Multiple
- Example: Extended Euclidean Algorithm
- 3. Modular Arithmetic (Fast Exponentiation, Power Mod)
- Example: Fast Modular Exponentiation
- Example: Recursive Fast Exponentiation
- 4. Matrix Exponentiation (Fibonacci, Linear Recurrence)
- Example: Matrix Multiplication and Exponentiation
- Example: Fibonacci using Matrix Exponentiation
- Example: Custom Recurrence with Matrix Exponentiation
- 5. Chinese Remainder Theorem (CRT, System of Congruences)
- Example: Chinese Remainder Theorem
- Example: Classic Puzzle - Sun Zi's Theorem
- 6. Combinatorics (Permutations, Combinations, nCr)
- Permutations
- Combinations
- Example: Pascal's Triangle for Combinations
- 7. Fermat's Little Theorem (Modular Inverse)
- Example: Modular Inverse using Fermat
- Example: Computing nCr Modulo Prime
- 8. Euler's Totient Function (φ(n), Coprime Count)
- Example: Computing Euler's Totient Function
- Example: Sieve for Multiple Phi Values
- Example: Applications of Euler's Totient
- 9. Catalan Numbers (Binary Trees, Parenthesis)
- Computing Catalan Numbers
- Catalan Applications
- Example: Generate All Valid Parentheses
- 1. Prime Numbers (Sieve of Eratosthenes, Sieve of Atkin)
- Example: Pascal's Triangle Properties
- Example: Binomial Theorem Applications
- 1. Prime Numbers (Sieve of Eratosthenes, Sieve of Atkin)
- Example: Stars and Bars Problems
- Example: Advanced Stars and Bars
- 1. Prime Numbers (Sieve of Eratosthenes, Sieve of Atkin)
- Example: Basic Inclusion-Exclusion
- Example: Coprime Counting
- 1. Prime Numbers (Sieve of Eratosthenes, Sieve of Atkin)
- Example: Computing Derangements
- Example: Hat-Check Problem
- 1. Prime Numbers (Sieve of Eratosthenes, Sieve of Atkin)
- Example: Computing Expected Values
- 1. Prime Numbers (Sieve of Eratosthenes, Sieve of Atkin)
- Example: Simple Markov Chain
- Example: Random Walk (Gambler's Ruin)
- Mathematical Algorithms Summary
- 1. Convex Hull (Graham Scan, Jarvis March)
- Example: Graham Scan Algorithm
- Example: Applications and Variants
- 2. Line Segment Intersection (Sweep Line Algorithm)
- Example: Line Segment Intersection
- Example: Find All Intersections (Brute Force)
- 3. Closest Pair of Points (Divide and Conquer O(n log n))
- Example: Closest Pair Divide and Conquer
- 4. Point in Polygon (Ray Casting, Winding Number)
- Example: Ray Casting Algorithm
- Example: Winding Number Algorithm
- 5. Voronoi Diagram and Delaunay Triangulation
- Example: Delaunay Triangulation (Bowyer-Watson)
- 6. Range Tree (Orthogonal Range Query 2D)
- Example: 1D Range Tree (Interval Query)
- Example: 2D Orthogonal Range Query
- Computational Geometry Summary
- 1. Memoization (Top-Down DP, Recursive)
- Example: Fibonacci with Memoization
- Example: Grid Paths with Memoization
- 2. Tabulation (Bottom-Up DP, Iterative)
- Example: Fibonacci with Tabulation
- 3. Knapsack Problem (0/1 Knapsack, Unbounded Knapsack)
- Example: 0/1 Knapsack
- Example: Unbounded Knapsack
- 4. Longest Common Subsequence (LCS DP)
- Example: LCS Implementation
- Example: LCS Variations
- 5. Longest Increasing Subsequence (LIS, O(n log n))
- Example: LIS Dynamic Programming O(n²)
- Example: LIS Binary Search O(n log n)
- 6. Matrix Chain Multiplication (MCM Optimization)
- Example: Matrix Chain Multiplication
- Example: Memoization Approach
- 7. Optimal Binary Search Tree (OBST DP)
- Example: Optimal BST
- 8. Coin Change Problem (Minimum Coins, Ways to Make Change)
- Example: Coin Change Variations
- 9. Convex Hull Trick (DP Optimization)
- Example: Convex Hull Trick
- 1. Memoization (Top-Down DP, Recursive)
- Example: Divide and Conquer DP
- 1. Memoization (Top-Down DP, Recursive)
- Example: Stone Merging with Knuth
- 1. Memoization (Top-Down DP, Recursive)
- Example: Sliding Window Maximum
- Example: DP with Monotone Queue
- 1. Memoization (Top-Down DP, Recursive)
- Example: Slope Trick Basics
- 1. Memoization (Top-Down DP, Recursive)
- Example: Maximum Independent Set on Tree
- Example: Binary Tree DP
- Dynamic Programming Summary
- 1. Cache-friendly Algorithms (Locality of Reference)
- Example: Matrix Multiplication Cache Optimization
- 2. Space Complexity Optimization (Auxiliary Space)
- Example: Space Optimization in DP
- 3. In-place Algorithms (O(1) Extra Space)
- Example: In-place Algorithms
- 4. Memory Pool (Pre-allocation Strategy)
- Example: Object Pool Implementation
- 5. Garbage Collection (GC-aware Programming)
- Example: GC-Aware Patterns
- 6. Space-Time Tradeoff (Trading Memory for Speed)
- Example: Space-Time Tradeoffs
- 7. Auxiliary Space vs Total Space Complexity
- Example: Auxiliary Space Analysis
- 8. Memory Hierarchy (Cache, RAM, Disk Optimization)
- Example: Cache Optimization Techniques
- Memory Optimization Summary
- 1. Fork-Join Parallelism (Divide and Conquer Parallel)
- Example: Parallel Merge Sort (Conceptual)
- 2. MapReduce (Distributed Computing Framework)
- Example: MapReduce Implementation
- 3. Lock-free Programming (CAS, Atomic Operations)
- Example: Lock-free Data Structures
- 4. Thread-safe Data Structures (Concurrent Collections)
- Example: Thread-safe Implementations
- 5. Work-stealing Queue (Load Balancing)
- Example: Work-stealing Deque
- Parallel Concurrent Algorithms Summary
- 1. Loop Unrolling (Reduce Loop Overhead)
- Example: Loop Unrolling Techniques
- 2. Branch Prediction (Minimize Mispredictions)
- Example: Branch Prediction Optimization
- 3. SIMD Vectorization (Parallel Data Processing)
- Example: Vectorization-friendly Code
- 4. Memory Access Patterns (Sequential vs Random)
- Example: Memory Access Optimization
- 5. Compiler Optimization (Inline, Constant Folding)
- Example: Optimization Hints in JavaScript
- Algorithm Optimization Summary
- 1. Consistent Hashing (Distributed Hash Table)
- Example: Consistent Hashing Implementation
- 2. Load Balancing (Round Robin, Weighted, Least Connections)
- Example: Load Balancer Implementations
- 3. Rate Limiting (Token Bucket, Leaky Bucket, Sliding Window)
- Example: Rate Limiting Implementations
- 4. Caching Strategies (LRU, LFU, TTL, Write-through)
- Example: Cache Implementations
- 5. Database Indexing (B+ Tree, Hash Index, Bitmap)
- Example: Database Index Structures
- 6. Message Queue Design (Kafka, RabbitMQ Patterns)
- Example: Message Queue Implementation
- System Design Data Structures Summary