■ Complete DSA Topics Roadmap
1. BASICS OF DSA
- What is DSA?
- Time Complexity & Big-O Notation
- Space Complexity
- Recursion (basic & advanced)
- Mathematical Functions (GCD, LCM, Prime Numbers, Factorials, Fibonacci)
- Bit Manipulation (AND, OR, XOR, Shift, Subsets using bits)
2. ARRAYS
- Introduction & Operations
- Traversal, Insertion, Deletion
- Searching (Linear Search, Binary Search, Ternary Search)
- Sorting Algorithms: Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, Heap Sort,
Counting Sort, Radix Sort, Bucket Sort
- Two Pointers Technique
- Prefix Sum / Suffix Sum
- Sliding Window Technique
- Kadane’s Algorithm (Maximum Subarray)
- Matrix Problems (Spiral Traversal, Rotate Matrix, Transpose, Search in Sorted Matrix)
3. STRINGS
- Basics of Strings & Operations
- Palindrome Check
- String Reversal
- Anagrams
- Substrings & Subsequences
- Pattern Matching (Naive, KMP, Rabin-Karp, Z Algorithm)
- Trie (Prefix Tree)
- String Hashing (Rolling Hash)
4. RECURSION & BACKTRACKING
- Factorial, Fibonacci using Recursion
- Tower of Hanoi
- N-Queens Problem
- Rat in a Maze
- Sudoku Solver
- Word Search Problem
- Generating Permutations & Combinations
- Subset Generation
5. LINKED LIST
- Singly, Doubly, Circular Linked List
- Reverse Linked List (Iterative & Recursive)
- Detect Loop (Floyd’s Cycle Detection)
- Intersection of Linked Lists
- Merge Two Sorted Lists
- Copy List with Random Pointer
6. STACK
- Implementation (Array & Linked List)
- Infix, Prefix, Postfix Expressions
- Balanced Parentheses
- Next Greater Element
- Min/Max Stack
- Stock Span Problem
- Histogram Maximum Area
- Celebrity Problem
7. QUEUE
- Simple Queue, Circular Queue
- Deque (Double Ended Queue)
- Priority Queue (Heap-based)
- Queue using Stacks
- Sliding Window Maximum (Deque based)
8. TREES
- Binary Tree Traversals (Inorder, Preorder, Postorder)
- Binary Search Tree (BST)
- AVL Tree
- Segment Tree (Range Queries, Lazy Propagation)
- Fenwick Tree (Binary Indexed Tree)
- Trie (Prefix Tree)
- Heap (Min-Heap, Max-Heap)
9. GRAPHS
- Representation (Adjacency Matrix, List)
- BFS, DFS
- Topological Sort
- Dijkstra, Bellman-Ford, Floyd-Warshall
- Kruskal & Prim’s (MST)
- Union-Find (DSU)
- Tarjan’s Algorithm (Bridges & Articulation Points)
- Kosaraju’s Algorithm (SCC)
- Bipartite Graph Check
- Cycle Detection
10. HASHING
- Hash Table Implementation
- Collision Handling
- Hash Maps & Hash Sets
- Frequency Counting
- Subarray with Sum K
- Longest Consecutive Sequence
11. GREEDY ALGORITHMS
- Activity Selection
- Fractional Knapsack
- Huffman Coding
- Minimum Spanning Tree
- Job Scheduling
12. DYNAMIC PROGRAMMING
- Basics (Memoization & Tabulation)
- Fibonacci, LCS, LIS
- Matrix Chain Multiplication
- 0/1 Knapsack, Unbounded Knapsack
- Coin Change, Subset Sum
- Minimum Edit Distance
- DP on Grids & Strings
- DP with Bitmasking
- DP on Trees
- Advanced DP (Digit DP, SOS DP)
13. ADVANCED DATA STRUCTURES
- Disjoint Set Union (DSU)
- Segment Tree with Lazy Propagation
- Binary Indexed Tree (Fenwick Tree)
- Suffix Array & Tree
- LRU Cache
14. IMPORTANT ALGORITHMS
- Divide & Conquer (Merge Sort, Quick Sort, Binary Search)
- Binary Exponentiation
- Fast Fourier Transform (FFT)
- KMP & Rabin-Karp (String Matching)
- Manacher’s Algorithm
- Boyer-Moore Voting Algorithm
- Moore’s Majority Element Algorithm
15. PROBLEM-SOLVING PATTERNS
- Sliding Window
- Two Pointers
- Fast & Slow Pointer
- Divide & Conquer
- Greedy Choice
- Backtracking
- Dynamic Programming Patterns
