DSA Roadmap
A well-designed DSA roadmap begins with foundations that every subsequent topic builds upon. In the first two weeks, solidify your understanding of arrays,...
Phase One: Foundations and Core Data Structures (Weeks 1 to 6)
A well-designed DSA roadmap begins with foundations that every subsequent topic builds upon. In the first two weeks, solidify your understanding of arrays, strings, and basic sorting algorithms (bubble sort, selection sort, insertion sort — understand why they are O(n^2) and when insertion sort outperforms the others). Implement a dynamic array (ArrayList equivalent) from scratch to understand amortized analysis. Learn Big-O notation rigorously: be able to analyze loops, nested loops, and recursive functions by counting operations as a function of input size.
Weeks three and four should focus on linked lists, stacks, and queues. Implement singly and doubly linked lists with insert, delete, and reversal operations. Understand the recursive structure of linked list problems — many can be elegantly solved by thinking in terms of "what should I do with the head node, given that the rest of the list is already processed correctly?" Implement a stack using an array and using a linked list. Implement a queue using two stacks (amortized O(1) dequeue) and using a circular buffer.
Weeks five and six introduce trees and hash tables. Implement a binary search tree with insert, search, delete, and all four traversals. Understand that deletion from a BST has three cases (leaf, one child, two children) and that the two-child case uses the inorder successor or predecessor. Study hash table internals: hash functions, separate chaining, open addressing with linear/quadratic probing, and the load factor threshold that triggers resizing. A concrete tip: implement a hash map from scratch using separate chaining before using the built-in one — this exercise reveals why hash map operations are amortized O(1), not guaranteed O(1).
Phase Two: Algorithm Design Paradigms (Weeks 7 to 14)
After building foundational data structure fluency, phase two focuses on the major algorithm design paradigms that unlock solutions to a vast range of problems. Week seven covers binary search — not just on sorted arrays, but as a general technique for searching over a monotone answer space. Practice problems where you binary search on the answer itself: minimum maximum element in array partition, capacity to ship packages within D days, kth smallest in a sorted matrix. The unifying pattern is: identify what you are binary searching on, write a feasibility check function, then apply standard binary search.
Weeks eight and nine introduce graphs comprehensively. Study adjacency list versus adjacency matrix representations, then implement BFS (shortest path in unweighted graphs, level-order traversal), DFS (cycle detection, topological sort, strongly connected components with Kosaraju's or Tarjan's algorithm), and Dijkstra's algorithm (single-source shortest path in weighted graphs). Week ten covers heaps and priority queues: heap sort, the heap property, and applications like Kth largest element, merge K sorted lists, and task scheduling.
Weeks eleven through fourteen tackle dynamic programming systematically. Start with memoized recursion to make the recursive structure explicit, then convert to tabulation (bottom-up DP) for better constant factors. Solve problems in this order: Fibonacci and climbing stairs (1D DP), 0/1 knapsack and subset sum (1D DP with subset reasoning), longest common subsequence (2D DP), and finally interval DP with matrix chain multiplication. At the end of each week in this phase, revisit problems from the previous week under timed conditions to reinforce retention while adding new material.
Phase Three: Advanced Topics and Continuous Improvement (Weeks 15 Onward)
Phase three develops the advanced algorithmic toolkit needed for senior engineering roles and competitive programming. Key topics include segment trees with lazy propagation (range sum/min/max queries with range updates), Fenwick trees (prefix sums with point updates, simpler to implement than segment trees for this use case), advanced graph algorithms (Floyd-Warshall for all-pairs shortest paths, Bellman-Ford for negative edges, minimum spanning tree with Prim's and Kruskal's), and string algorithms (KMP for pattern matching, Z-algorithm, Aho-Corasick for multi-pattern matching).
Trie data structures deserve focused attention. A trie stores strings character by character, supporting prefix search in O(L) time where L is the string length. Applications include autocomplete systems, IP routing tables, and the XOR maximization trick (storing binary representations in a trie to find the pair of numbers with maximum XOR in O(n log max_value) time). The XOR trie problem is a concrete example that combines bit manipulation and trie concepts in a non-obvious way — practicing this problem is highly recommended.
Continuous improvement after completing the roadmap requires exposure to diverse problem types and regular competition participation. Participate in Codeforces Div. 2 or Div. 3 contests weekly — the time pressure and competitive environment are irreplaceable for developing instinct. Review your submissions after each contest, including problems you solved correctly, to find more elegant or efficient approaches. Set a personal target of solving at least three new medium or hard problems per week indefinitely. The roadmap provides structure for the foundation, but long-term mastery comes from sustained curiosity and consistent practice.