DSA & DAA — Complete Roadmap

Every Topic, Algorithm & Technique for BTech Students · Job & Interview Preparation Guide

🔥 HOT — Asked in every interview ✅ MUST KNOW — Essential for placements 🎯 IMPORTANT — Frequently tested
HOT = Every company asks
MUST = Core essential
IMP = Frequently tested
LC = LeetCode Practice Link
01

Algorithm Analysis

  • Asymptotic Notations MUST
    • Big-O (Upper Bound)
    • Big-Ω (Lower Bound)
    • Big-Θ (Tight Bound)
    • Little-o & Little-ω
  • Time Complexity HOT
    • Best / Avg / Worst Case
    • O(1) O(log n) O(n) O(n log n) O(n²) O(2ⁿ)
  • Space Complexity MUST
    • Auxiliary vs Total Space
    • In-place Algorithms
  • Recurrence Relations IMP
    • Master Theorem
    • Substitution Method
    • Recursion Tree Method
    • Akra-Bazzi Method
  • Amortized Analysis
    • Aggregate Method
    • Accounting Method
    • Potential Method
02

Linear Data Structures

  • Arrays HOT LC Practice
    • Static & Dynamic Arrays
    • Multi-dimensional Arrays
    • Prefix Sum / Diff Array LC
    • Kadane's Algorithm HOT LC #53
    • Two Pointers HOT LC Practice
    • Sliding Window HOT LC Practice
  • Linked Lists HOT LC Practice
    • Singly Linked List
    • Doubly Linked List
    • Circular Linked List
    • Skip List
    • Reverse LL HOT LC #206
    • Detect Cycle HOT LC #141
  • Stacks HOT LC Practice
    • Array / LL-based
    • Min/Max Stack LC #155
    • Monotonic Stack IMP LC
    • Next Greater Element HOT LC #496
    • Valid Parentheses HOT LC #20
  • Queues MUST LC Practice
    • Simple & Circular Queue
    • Deque (Double-Ended)
    • Priority Queue HOT LC
    • Monotonic Queue
03

Trees HOT LC Practice

  • Binary Tree HOT LC Practice
  • Binary Search Tree HOT LC Practice
    • Insert / Delete / Search
    • Validate BST HOT LC #98
    • Kth Smallest LC #230
  • Self-Balancing BSTs MUST
    • AVL Tree (Rotations)
    • Red-Black Tree
    • Splay Tree
    • Treap
  • B-Tree / B+ Tree IMP
  • Segment Tree IMP
    • Range Query / Point Update LC #307
    • Lazy Propagation
  • Fenwick Tree (BIT) IMP LC
  • Trie (Prefix Tree) HOT LC #208
    • Insert / Search / Autocomplete
    • Compressed (Radix Tree)
  • N-ary Tree / K-D Tree
04

Heaps, Hashing & Union-Find

  • Heaps HOT LC Practice
    • Min Heap / Max Heap
    • Heapify & Heap Sort
    • Top K Elements HOT LC #347
    • Merge K Lists HOT LC #23
    • Median in Stream HOT LC #295
    • Fibonacci Heap
    • Binomial Heap
  • Hashing HOT LC Practice
    • Hash Functions
    • HashMap / HashSet HOT LC #1
    • Collision Resolution
      • Separate Chaining
      • Open Addressing
      • Linear / Quadratic Probing
      • Double Hashing
      • Cuckoo Hashing
    • Bloom Filter
  • Union-Find IMP LC Practice
    • Union by Rank / Size
    • Path Compression
    • Redundant Connection LC #684
  • Sparse Table (RMQ)
05

Sorting Algorithms HOT LC Practice

  • Comparison-Based
    • Bubble Sort O(n²)
    • Selection Sort O(n²)
    • Insertion Sort O(n²) LC #147
    • Merge Sort O(n log n) HOT LC #912
    • Quick Sort O(n log n) HOT LC #75
    • Heap Sort O(n log n)
    • Shell Sort
    • Tim Sort O(n log n)
  • Non-Comparison-Based
    • Counting Sort O(n+k)
    • Radix Sort O(nk)
    • Bucket Sort O(n+k)
  • Hybrid / Special
    • Introsort
    • Cycle Sort
    • Topological Sort IMP LC
06

Searching HOT LC Practice

  • Linear Search O(n)
  • Binary Search O(log n) HOT LC #704
  • Ternary Search O(log₃ n)
  • Jump Search O(√n)
  • Interpolation Search
  • Exponential Search
  • Two Pointers HOT LC #15
  • Sliding Window HOT LC #76
07

Graph Algorithms HOT LC Practice

Traversal HOT

  • BFS HOT LC
    • Level-order
    • Shortest Path (Unweighted)
    • Multi-source BFS LC #994
    • 0-1 BFS
  • DFS HOT LC
    • Connected Components
    • Cycle Detection HOT LC #207
    • Path Finding
    • Flood Fill LC #733
    • No. of Islands HOT LC #200

Shortest Path HOT

  • Dijkstra's HOT LC #743
    • Non-negative Weights
  • Bellman-Ford MUST LC #787
    • Negative Weights
    • Negative Cycle Detection
  • Floyd-Warshall MUST
    • All-Pairs Shortest Path
  • Johnson's Algorithm
  • A* Search (Heuristic)

MST & Connectivity

  • Prim's MST MUST LC #1584
  • Kruskal's MST MUST
  • Topological Sort HOT LC #210
    • Kahn's (BFS)
    • DFS-based
  • SCC
    • Kosaraju's
    • Tarjan's
  • Articulation Points
  • Bridges LC #1192

Network Flow & More

  • Max Flow / Min Cut
    • Ford-Fulkerson
    • Edmonds-Karp
    • Dinic's Algorithm
  • Bipartite Check IMP LC #785
  • Bipartite Matching
    • Hungarian Algorithm
    • Hopcroft-Karp
  • Euler Path / Circuit
  • Graph Coloring
08

Dynamic Programming HOT — #1 Interview Topic LC Practice

Techniques

  • Memoization (Top-Down) HOT
  • Tabulation (Bottom-Up) HOT
  • Space Optimization IMP
  • Bitmask DP
  • Digit DP
  • DP on Trees
  • DP on Graphs
  • DP on Intervals
  • State Machine DP

Classic Problems (Must Solve)

Graph DP & Advanced

  • Floyd-Warshall MUST
  • Bellman-Ford
  • TSP (DP + Bitmask)
  • Stock Buy/Sell HOT LC #121
  • House Robber HOT LC #198
  • Longest Palindromic Subseq LC #516
  • Wildcard Match LC #44
  • Unique Paths HOT LC #62
  • Partition Equal Subset IMP LC #416
  • Climbing Stairs HOT LC #70
09

Greedy & Divide-Conquer

  • Greedy HOT LC Practice
    • Activity Selection MUST LC #435
    • Huffman Coding MUST
    • Fractional Knapsack MUST
    • Job Sequencing IMP
    • Optimal Merge Pattern
    • Dijkstra / Prim / Kruskal
    • Jump Game HOT LC #55
    • Min Platforms HOT LC #253
  • Divide & Conquer MUST LC Practice
    • Merge Sort / Quick Sort
    • Binary Search
    • Strassen's Matrix Mult.
    • Closest Pair of Points
    • Karatsuba Multiplication
    • FFT
    • Count Inversions IMP LC #315
10

Backtracking & B&B LC Practice

  • Backtracking HOT
    • N-Queens HOT LC #51
    • Sudoku Solver IMP LC #37
    • Permutations HOT LC #46
    • Combinations HOT LC #77
    • Subsets HOT LC #78
    • Word Search HOT LC #79
    • Rat in a Maze
    • Graph Coloring MUST
    • Hamiltonian Path
    • Knight's Tour
    • Palindrome Partition LC #131
    • Combination Sum HOT LC #39
    • Letter Combos Phone LC #17
  • Branch & Bound
    • 0/1 Knapsack
    • Travelling Salesman
    • Job Assignment
    • 15-Puzzle
11

String Algorithms HOT LC Practice

Pattern Matching

  • Naive O(nm)
  • KMP O(n+m) HOT LC #28
    • Prefix/Failure Function
  • Rabin-Karp O(n+m) MUST LC #187
    • Rolling Hash
  • Boyer-Moore
  • Z-Algorithm IMP
  • Aho-Corasick

String Structures

  • Suffix Array IMP
  • Suffix Tree (Ukkonen's)
  • Suffix Automaton
  • Trie-based

String Problems HOT

  • Longest Palindromic Substr HOT LC #5
  • Manacher's Algorithm
  • Valid Anagram HOT LC #242
  • Longest Substr No Repeat HOT LC #3
  • String to Integer IMP LC #8
  • Reverse Words IMP LC #151
  • Group Anagrams HOT LC #49
12

Math & Number Theory LC Practice

  • GCD / LCM MUST
    • Euclidean Algorithm
    • Extended Euclidean
  • Primality MUST
    • Sieve of Eratosthenes HOT LC #204
    • Segmented Sieve
    • Miller-Rabin Test
  • Modular Arithmetic IMP
    • Fast Power HOT LC #50
    • Modular Inverse
    • Chinese Remainder Thm
    • Fermat's Little Theorem
  • Combinatorics IMP
    • nCr, nPr, Pascal's Triangle LC #118
    • Catalan Numbers LC #96
    • Inclusion-Exclusion
  • Matrix Exponentiation
  • FFT
13

Computational Geometry LC Practice

  • Convex Hull MUST LC #587
    • Graham Scan
    • Jarvis March
    • Andrew's Monotone Chain
  • Line Intersection
  • Closest Pair O(n log n)
  • Sweep Line
  • Polygon Area (Shoelace)
  • Point in Polygon
    • Ray Casting
    • Winding Number
  • Voronoi Diagrams
  • Delaunay Triangulation
14

Advanced Topics & Complexity Theory

Complexity Classes MUST

  • P (Polynomial)
  • NP
  • NP-Complete MUST
    • SAT / 3-SAT
    • Clique / Vertex Cover
    • Hamiltonian Cycle
    • Subset Sum
  • NP-Hard
  • P vs NP Problem

Approximation

  • Vertex Cover (2-approx)
  • TSP (Christofides)
  • Set Cover
  • PTAS / FPTAS

Randomized Algorithms

  • Las Vegas
    • Randomized QuickSort
    • Randomized Select
  • Monte Carlo
    • Miller-Rabin
    • Karger's Min-Cut
  • Reservoir Sampling LC

Game Theory LC

  • Minimax IMP
  • Alpha-Beta Pruning
  • Sprague-Grundy
  • Nim Game LC #292

Misc Advanced

  • Online Algorithms
  • Streaming Algorithms
  • Linear Programming
    • Simplex Method
  • Parallel Algorithms
    • Bitonic Sort
    • PRAM Model

DSA & DAA — Complete Roadmap for BTech Placements & Job Interviews • All Topics · Subtopics · Algorithms · Techniques • 100+ LeetCode Links • 2025