1.
Basics of Programming
Before jumping into DSA, make sure you’re solid on:
• Input/Output handling (fast I/O in C++/Python)
• Time complexity & Big O notation
• Space complexity
• Modulo arithmetic ((a + b) % m, (a * b) % m, etc.)
• Type conversions and overflow handling
• Recursion basics
2. Mathematics for CP
Math is core in competitive programming.
• Prime numbers & Sieve of Eratosthenes
• GCD, LCM (Euclidean algorithm)
• Modular arithmetic
• Modular exponentiation (fast power)
• Factorials and nCr (combinations)
• Modular inverse (Fermat’s Little Theorem)
• Prefix sums and difference arrays
• Bit manipulation:
o Counting bits
o Checking even/odd
o Power of 2 check
o Subset generation
• Number theory basics:
o Divisors of a number
o Euler’s Totient Function
o Chinese Remainder Theorem (advanced)
• Matrix exponentiation (for Fibonacci-type problems)
3. Data Structures
Basic Structures
• Arrays
• Strings
• Linked Lists (singly & doubly)
• Stacks
• Queues
• Deque (double-ended queue)
Advanced Structures
• Priority Queue / Heap (min-heap, max-heap)
• HashMap / HashSet (unordered_map in C++, dict/set in Python)
• Trees:
o Binary Tree
o Binary Search Tree (BST)
o Tree traversals (DFS, BFS, Inorder, Preorder, Postorder)
• Graphs:
o Adjacency list vs matrix
o BFS / DFS traversal
o Topological sort
o Dijkstra, Bellman-Ford, Floyd-Warshall
o Union-Find (Disjoint Set Union)
o Minimum Spanning Tree (Kruskal, Prim)
• Tries (Prefix Trees)
• Segment Tree (for range queries)
• Fenwick Tree (Binary Indexed Tree)
• Sparse Table
• Ordered Set / Policy-Based DS (C++)
4. Algorithms
Sorting
• Bubble / Selection / Insertion (basic)
• Merge sort / Quick sort (divide and conquer)
• Counting / Radix / Bucket sort
• Custom comparator sorting
Searching
• Linear search
• Binary search
o On sorted arrays
o On answer (parametric search)
• Ternary search (for unimodal functions)
Greedy Algorithms
• Activity selection problem
• Huffman encoding
• Fractional knapsack
• Minimum coins
• Job sequencing
• Interval problems
Divide and Conquer
• Binary search (again)
• Merge sort, Quick sort
• Matrix exponentiation
• Fast exponentiation
Dynamic Programming (DP)
• 1D DP:
o Fibonacci
o Climbing stairs
• 2D DP:
o Knapsack problems
o Subset sum
o Coin change
o Matrix path
• String DP:
o Longest Common Subsequence (LCS)
o Longest Common Substring
o Edit distance
o Palindrome partitioning
• DP on Trees
• DP with Bitmasking
• DP Optimization (Divide and Conquer DP, Convex Hull Trick)
5. Graph Algorithms (Advanced)
• DFS/BFS applications
• Shortest path algorithms:
o Dijkstra
o Bellman-Ford
o Floyd-Warshall
• Minimum Spanning Tree:
o Kruskal’s algorithm
o Prim’s algorithm
• Topological Sort
• Strongly Connected Components (Kosaraju, Tarjan)
• Bridges and Articulation Points
• Euler Path & Circuit
• Hamiltonian Path (backtracking)
• Flow Algorithms:
o Ford-Fulkerson
o Edmonds-Karp
o Dinic’s Algorithm
6. Advanced Topics
• Binary Search on Answer
• Sliding Window Technique
• Two Pointers Technique
• Meet in the Middle
• Bitmasking problems
• String Algorithms:
o KMP algorithm
o Z-algorithm
o Rabin-Karp
o Trie and Aho-Corasick
o Manacher’s Algorithm (longest palindrome substring)
• Geometry:
o Orientation and cross product
o Convex Hull (Graham scan / Jarvis march)
o Line intersection
• Game Theory:
o Grundy numbers
o Nim game
7. Practice Patterns
• Prefix sum / Suffix sum
• Difference array
• Frequency array
• Cumulative frequency
• Coordinate compression
• Offline queries (Mo’s Algorithm)
• Binary lifting (for LCA in trees)
• Range queries (RMQ, Range update)
8. Problem-Solving Strategy
• Brute force → Optimize gradually
• Try smaller inputs manually
• Analyze constraints (decide O(n), O(n log n), etc.)
• Learn pattern recognition
• Participate in contests regularly (Codeforces, AtCoder, LeetCode, CodeChef)
9. Recommended Progress Order
1. Arrays, Strings, Sorting, Searching
2. Recursion & Backtracking
3. Stack, Queue, Linked List
4. Trees, Binary Search Tree
5. Graphs (BFS, DFS, Dijkstra, MST)
6. Dynamic Programming (basic → advanced)
7. Segment Tree, Fenwick Tree
8. Advanced Math & Geometry
9. Bitmasking, DP optimizations