DSA Roadmap
Two tracks in one order. Data structures start at Arrays & Strings; algorithms start at Sorting, right after the shared Complexity foundation. Every stage lists what it needs first, so you can follow one track and cross over only when a stage asks you to. Progress is stored locally in your browser.
Where to start
Data structures
11 stages · 0/55 topicsWhat you store, what each operation costs, and which structure a problem is asking for.
Algorithms
11 stages · 0/94 topicsWhat you do with the data: the techniques, in the order each one unlocks the next.
Both tracks assume the Complexity foundation. If you are undecided, follow the suggested order: it alternates between the tracks so each stage has what it needs.
- 1
Complexity
FoundationUse the Complexity Explorer to get a feel for how
O(1),O(log n),O(n),O(n log n),O(n^2)andO(2^n)scale. Every data structure page and every algorithm page states its cost in this language, so learn to read it first.Before moving on: Read a constraint like
Open the Complexity Explorer →n <= 10^5, say which complexities are acceptable, and derive the complexity of a nested loop or a halving recursion. - 20/4
Arrays & Strings
Data structuresStart hereThe first data structure. Contiguous memory gives
O(1)indexing, appending to a dynamic array is amortizedO(1), and strings and matrices are arrays in disguise. Almost every later structure is built on top of an array or contrasted with one.Before moving on: Explain why an index is
O(1)and an insert in the middle isO(n), resize a dynamic array by hand, and treat a matrix as an array of rows.Needs first:Complexity - 30/8
Sorting
AlgorithmsStart hereThe first algorithms. The simple sorts teach you to reason about loops and invariants; merge sort and quick sort teach recursion and
O(n log n); counting and radix sort show that comparison is not the only way. Sorted input is the precondition for binary search and two pointers, so this stage unlocks the next two.Before moving on: Write insertion, merge and quick sort from memory, state their stability and complexity, and pick counting or radix sort when keys are small integers.
Needs first:Arrays & Strings· data structures track - 40/6
Hashing
Data structuresA hash function plus a collision strategy gives expected
O(1)insert and lookup. Understand what happens when the load factor grows and why the worst case is stillO(n). From here on, every "have I seen this before" scan should become a set.Before moving on: Solve two-sum, anagram grouping and frequency counting without hesitation, and explain chaining versus open addressing.
Needs first:Arrays & Strings - 50/6
Linked Lists
Data structuresPointer manipulation with
prev/curr/nextand a dummy head. Know when a list beats an array (O(1)splice at a known node) and when it does not (no random access). The LRU cache shows a list and a hash map working together.Before moving on: Reverse, merge, find the middle and detect a cycle in one pass and constant space.
Needs first:Arrays & Strings - 60/6
Stack & Queue
Data structuresLIFO and FIFO are the two orders every later algorithm builds on: DFS and expression parsing use a stack, BFS uses a queue. Implement both on arrays and on lists, then meet the monotonic variants that turn
O(n^2)next-greater scans intoO(n).Before moving on: Implement a stack and a queue on an array and on a list, solve bracket matching and min-stack, and use a monotonic stack for next-greater-element.
- 70/5
Binary Search
AlgorithmsBeyond finding a value in a sorted array, binary search works on any monotonic predicate, including the answer space of an optimization problem. Quickselect is the same idea applied to partitioning.
Before moving on: Write both templates (
lo <= hiandlo < hi) without off-by-one bugs and solve rotated-array and "minimum speed" style problems.Needs first:Sorting - 80/4
Two Pointers
AlgorithmsTurn
O(n^2)pair scans intoO(n)by exploiting order: opposite ends for sorted sums and palindromes, same direction for in-place compaction and partitioning, fast and slow on linked lists.Before moving on: Justify which pointer moves and why the skipped pairs cannot be the answer.
- 90/7
Sliding Window & Prefix Sums
AlgorithmsSolve contiguous subarray and substring problems by maintaining a window that grows and shrinks monotonically, with a frequency map when characters matter. Prefix sums answer range-sum questions in
O(1)afterO(n)preparation and are the static half of the range trees later on.Before moving on: State the window invariant, handle "at most k" versus "exactly k", and answer range-sum queries with a prefix array.
- 100/5
Recursion & Divide and Conquer
AlgorithmsTrust the recursive call: define the base case, make progress, combine. The call stack is a stack, so this comes right after Stack & Queue. Trees, graphs, backtracking and dynamic programming all assume you are comfortable here.
Before moving on: Trace the call stack for a small input, convert simple recursion to iteration, and explain why divide-and-conquer recurrences give
O(n log n). - 110/6
Trees / BST
Data structuresThe first recursive data structure. Learn the three depth-first orders and level order, and how the BST invariant makes inorder traversal sorted. Balancing (AVL, red-black) keeps operations
O(log n); B-trees are the same idea with fat nodes for disks.Before moving on: Validate a BST, find a lowest common ancestor, compute heights and path sums recursively, and explain why balancing matters.
- 120/6
Heap & Priority Queue
Data structuresAn array-backed complete binary tree with sift-up and sift-down and
O(n)heapify. The priority queue built on it drives heap sort, top-k, k-way merge, running median and Dijkstra.Before moving on: Implement a priority queue, solve top-k and k-way merge in
O(n log k), keep a running median with two heaps, and know when quickselect is the better choice.Needs first:Trees / BST - 130/7
Graphs
Data structuresNodes and edges: directed or undirected, weighted or not, with or without cycles. Adjacency lists are the default; adjacency matrices pay
O(V^2)space forO(1)edge lookup; edge lists suit sorting-based algorithms like Kruskal.Before moving on: Build an adjacency list from an edge list, say which representation a problem wants, and recognise a DAG when you see one.
- 140/10
Graph Traversal & Shortest Paths
AlgorithmsBFS for shortest unweighted paths, DFS for components and cycles, both orders of topological sort for a DAG. Then Dijkstra with a heap, why it fails on negative edges, and when Bellman-Ford or Floyd-Warshall applies instead.
Before moving on: Run BFS and DFS from memory, topologically sort a DAG both ways, and pick the right shortest-path algorithm from the edge weights.
- 150/7
Backtracking
AlgorithmsEnumerate subsets, permutations and combinations with choose / recurse / un-choose, and prune early. The search tree is the mental model that dynamic programming later collapses.
Before moving on: Write N-Queens and word search cleanly, handle duplicates in the input, and estimate the size of the search tree from the constraints.
Needs first:Recursion & Divide and Conquer - 160/8
Greedy
AlgorithmsSpot when a locally optimal choice is globally safe, and argue it with an exchange argument. Most greedy solutions start by sorting or by pulling from a heap.
Before moving on: Solve interval scheduling by earliest finish, merge intervals after sorting, and recognise when a greedy attempt fails and DP is required.
- 170/15
Dynamic Programming
AlgorithmsDefine a state, write the recurrence, then decide between memoization and tabulation. Start with the 1D family, then grids, knapsack and subsequences; each is a backtracking search with the repeated subproblems cached.
Before moving on: Derive the 1D, grid, knapsack and subsequence families from scratch, reconstruct an optimal solution from the table, and reduce space when only the previous row is needed.
- 180/12
Bit Manipulation & Math
AlgorithmsMasks, XOR tricks and subset enumeration over bits, then the number theory that shows up in constraints: GCD, primes with a sieve, fast exponentiation and modular arithmetic. Bitmask DP joins the two.
Before moving on: Enumerate all subsets of a small set with a bitmask, compute
a^b mod minO(log b), and sieve primes up to10^6. - 190/2
Trie
Data structuresStore strings character by character so prefix queries cost
O(L)regardless of dictionary size. A trie prunes the grid DFS of Word Search (Grid DFS) when there are many words, and Aho-Corasick adds failure links for multi-pattern matching.Before moving on: Implement insert / search / startsWith, use a trie to prune a backtracking search, and know when a hash set of prefixes is simpler.
- 200/2
Union-Find
Data structuresDisjoint sets with path compression and union by rank, and why the amortized cost is effectively constant. It answers connectivity questions as edges arrive, which DFS cannot do cheaply, and it is the engine under Kruskal's Algorithm in the next algorithm stage.
Before moving on: Count components as edges arrive, detect the redundant edge in a graph, and explain why path compression makes find nearly
O(1). - 210/6
Segment / Fenwick Trees
Data structuresMove from static prefix sums to structures that support updates: Fenwick trees for sums, segment trees for any associative operation, sparse tables for static idempotent queries.
Before moving on: Build each, explain the
O(log n)bound, and choose between them from the problem statement. - 220/5
Caches & Specialized Structures
Data structuresStructures you meet in systems work more than in interviews: LRU and LFU caches (a hash map plus ordered lists), Bloom filters (probabilistic membership in constant space), skip lists (a probabilistic balanced tree) and B+ trees (what databases index with).
Before moving on: Implement an LRU cache in
O(1)per operation, explain a Bloom filter's false-positive rate, and say why databases pick B+ trees over binary search trees. - 230/15
Advanced Graph & String Algorithms
AlgorithmsRound out the toolkit with minimum spanning trees (Kruskal on top of union-find, Prim on top of a heap), SCCs, bridges and articulation points via DFS low-link, Euler paths, bipartite checks, 0-1 BFS and A*, and linear-time string matching with KMP, Z, rolling hashes and Manacher.
Before moving on: Explain the failure function of KMP, the low-link invariant of Tarjan, why Kruskal needs union-find, and pick 0-1 BFS or A* over Dijkstra when the graph allows it.