oneby7

The DSA roadmap

The roadmap covers 23 topics, in the order they build on each other. Each topic splits into patterns. Every pattern says how to spot it, teaches the idea in a lesson, then lists the problems that practise it.

01Foundationsstart here7 patterns · 18 lessons45

The language skills every later topic assumes: reading input, loops, functions, basic maths and how to measure how fast code runs.

Thinking like a programmerYou are new to code, or you freeze when a problem has no obvious first step.
  • What a program is and what the computer does with itVideo soonSoon
  • Breaking a problem into steps: flowcharts and pseudocodeVideo soonSoon
  • Dry runs, edge cases and debugging by handVideo soonSoon
  • Choosing a language for interviewsVideo soonSoon
Language basicsYou need to read input, branch on conditions and repeat work in your language.4
Time and space complexityYou need to say how the running time grows before you write any code.
  • Big-O: counting how work grows with inputVideo soonSoon
  • Reading complexity from code: loops, recursion and hidden costsVideo soonSoon
  • Using the constraints to guess the intended complexityVideo soonSoon
Loops through pattern printingYou want nested loops to feel automatic before you meet real problems.22
Working with digits and divisorsThe input is a number and you need to take it apart digit by digit or find what divides it.10
Recursion basicsA function needs to solve a smaller copy of the same problem.5
Counting with arrays and mapsYou need how often each value appears, and an array index or a map key can hold the count.4
02Arrays and Hashingafter Foundations7 patterns · 3 lessons43

Most problems start with an array and a hash map. This topic teaches the moves that every later topic reuses.

Array basicsYou need to scan an array once to find, count or move elements.12
Hash map lookupsYou need to know in one step whether you have seen a value before.9
Counting and votingThe answer depends on how often each value appears.4
One pass with running stateYou keep one or two values as you scan, and the answer is ready at the end.3
Prefix sumsThe question is about the sum of a subarray, and adding it up again for every range is too slow.10
Walking a matrixThe input is a grid, and the work is moving through it in a fixed order.3
Counting during merge sortYou must count pairs where an earlier value is larger than a later one.2
03Mathafter Foundations4 patterns · 3 lessons14

A few problems test arithmetic more than data structures. Each one has a single idea to learn.

Number tricksThe input is a number, or digits stored in a string or an array.8
Primes and the sieveYou need primes or prime factors for many numbers at once.2
Fast power and modular arithmeticThe answer is huge, so you work modulo a prime and square as you go.1
Pascal's triangle and combinationsYou need nCr, or the rows of Pascal's triangle.3
04Bit Manipulationafter Arrays and Hashing4 patterns · 2 lessons20

Integers are rows of bits. A few operators, mostly XOR and shifts, solve problems that seem to need extra memory.

Bit basicsYou need to read, set or clear one bit of a number.7
XOR tricksEvery value appears twice except one or two, or one value is missing.6
Counting and shifting bitsThe question is about the bits of a number.6
BitmasksThe input is small enough that every subset fits in an integer.1
05Stringsafter Arrays and Hashing4 patterns · 1 lesson20

Strings are arrays of characters with a few traps: they are often immutable, and building one in a loop can be quadratic.

String basicsYou need to reverse, compare or rebuild a string character by character.10
Parentheses and nestingThe string is made of brackets and you track how deep you are.4
Parsing and conversionYou turn text into a number or a number into text, with every edge case handled.3
Counting over substringsYou need a statistic for every substring, and there are O(n²) of them.3
06Sortingafter Arrays and Hashing2 patterns · 3 lessons9

Knowing how the sorts work tells you what a sort costs, when order is kept, and when a problem is really a sorting problem.

Simple sortsYou need to understand O(n²) sorting well enough to write it without thinking.5
Divide-and-conquer sortsYou need O(n log n), and splitting the array in half is the way in.4
07Two Pointersafter Arrays and Hashing3 patterns · 1 lesson18

Two indexes move through the same array. One pass then does the work of two nested loops.

Pointers from both endsThe array is sorted, or can be, and you are looking for a pair.9
Rearranging in placeYou must reorder the array without making a second one.5
Merging sorted arraysYou have two sorted sequences and need their union, intersection or merge.4
08Sliding Windowafter Two Pointers3 patterns · 2 lessons16

A window over a range grows on one side and shrinks on the other. Each element enters once and leaves once.

Longest or shortest windowThe question asks for the longest or shortest substring or subarray that meets a condition.8
Fixed-size windowThe window size is given, so each step adds one element and removes one.4
Counting windowsThe question asks how many subarrays meet a condition, not which one is longest.4
09Stacks and Queuesafter Arrays and Hashing5 patterns · 3 lessons39

A stack remembers what is still open. The last thing you pushed is the first thing you need.

Building stacks and queuesYou need to implement a stack or queue yourself, or build one from the other.8
Matching and cancellingEach new item either cancels the most recent open item or waits on top of it.10
Infix, prefix and postfixYou need to convert or evaluate an expression written in another notation.6
Monotonic stackFor each element you need the next or previous element that is larger or smaller.13
Monotonic queueYou need the largest or smallest value of every window as it slides.2
10Binary Searchafter Arrays and Hashing5 patterns · 2 lessons36

Each step throws away half of what is left. It works on sorted arrays, and on any answer you can check with a yes or no.

Lower and upper boundsYou need the first position where a condition becomes true.8
Searching a sorted arrayThe input is sorted, or sorted and then rotated.7
Searching the answerYou cannot compute the answer directly, but you can quickly check whether a given value works.13
Searching a matrixThe input is a sorted matrix, and you search rows, columns or values.6
Partition searchYou need the median or the k-th element of two sorted arrays.2
11Linked Listsafter Two Pointers5 patterns · 4 lessons52

Linked list problems are about moving pointers without losing the rest of the list.

Singly linked list basicsYou need to walk, insert into or delete from a linked list by hand.14
Doubly linked listsEach node also points back, so you must keep two links right on every change.13
Fast and slow pointersYou need the middle, a cycle, or a node counted from the end.9
Reversing and rewiringThe answer is the same nodes, connected in a different order.14
A list and a map togetherYou must find any item in one step and also keep the items in order of use.2
12Recursion and Backtrackingafter Arrays and Hashing4 patterns · 3 lessons25

Recursion tries one choice and explores everything after it. Then it undoes the choice and tries the next one.

Pick or skipEach element is either in or out, and you need every choice or a count of them.3
Recursion on a stackYou may use only the stack's own push and pop, so the call stack holds the rest.2
Generating every choiceThe question asks for all subsets, combinations or permutations.12
Searching with constraintsMost choices break a rule, so you check each one early and stop exploring it.8
13Binary Treesafter Recursion and Backtracking4 patterns · 7 lessons44

Almost every tree problem is one recursive function. The skill is deciding what each call returns to its parent.

TraversalsYou need to visit every node in a set order: pre, in, post or level.6
Depth first: return a value upThe answer for a node depends on the answers for its children.23
Breadth first: level by levelThe question mentions levels, a view from one side, or a distance from a node.12
Building and serializingYou must turn traversal orders, or a string, back into a tree.3
14Binary Search Treesafter Binary Trees, Binary Search2 patterns · 1 lesson18

In a BST, everything on the left is smaller and everything on the right is larger. Most problems use this to skip half the tree.

BST basicsYou need to search, find the smallest or largest, or find the nearest value in a BST.5
Using the orderingThe tree is a BST, so an in-order walk visits the values in sorted order.13
15Heapsafter Binary Trees5 patterns · 2 lessons22

A heap gives you the smallest or largest item in log time. Use it when you keep needing the current best.

Building a heapYou need to implement a heap yourself, or use one to sort.6
Top KYou need the k largest, smallest or closest items, and a full sort does more work than that.8
Simulating with a heapEach step takes the best item, changes it, and puts it back.6
Two heapsYou need the median of numbers that keep arriving.1
Merging k sorted listsYou have k sorted sequences and need one sorted output.1
16Triesafter Binary Trees2 patterns · 2 lessons9

A trie stores strings by their prefixes, so words that start the same way share a path.

Prefix treesYou search many words by prefix, or match them one letter at a time.7
Tries over bitsYou want the pair of numbers with the largest XOR.2
17Graphsafter Binary Trees7 patterns · 6 lessons40

A graph is a tree that can have cycles. The same DFS and BFS apply, with a visited set so you do not loop forever.

Graph basicsYou need to store a graph and visit every node.3
Grids as graphsThe input is a grid, and each cell connects to its neighbours.8
Fewest steps with BFSEvery move costs the same and you want the fewest moves, often from many starting points at once.6
Traversing a graphThe input is a list of edges or neighbours, not a grid.5
Cycle detectionYou need to know whether a path leads back to where it started.2
Topological sortSome tasks must come before others, and you need a valid order or proof that none exists.7
Union-findEdges arrive one at a time, and you keep asking whether two nodes are already connected.9
18Advanced Graphsafter Graphs, Heaps3 patterns · 6 lessons20

When edges have weights, plain BFS no longer finds the shortest path. These algorithms handle weights.

Weighted shortest pathsEdges have different costs and you want the cheapest route.14
Minimum spanning treesYou must connect every node at the lowest total cost.2
Special edges and pathsYou must use every edge once, or find the edges whose removal splits the graph.4
19Greedyafter Sorting1 pattern · 1 lesson15

A greedy solution takes the best-looking choice at each step and never goes back. The hard part is proving that this is safe.

The best choice nowA choice that looks best now can never hurt you later.15
20Intervalsafter Greedy1 pattern · 1 lesson8

Sort the intervals by start or by end first. After that, most interval problems take one pass.

Merging and schedulingThe input is a list of start and end times.8
211-D Dynamic Programmingafter Recursion and Backtracking4 patterns · 3 lessons24

Dynamic programming is recursion that remembers answers it has already worked out. In 1-D problems, each answer depends on a few earlier ones.

Take it or skip itAt each position you either use it or skip it, and the best answer builds on the ones before.11
PalindromesThe question asks about palindromic substrings.2
Increasing subsequencesThe answer is a subsequence that must keep going up.6
Buying and selling with statesYou either hold a stock or you do not, and the rules limit how you switch.5
222-D Dynamic Programmingafter 1-D Dynamic Programming4 patterns · 4 lessons40

Here each answer depends on two indexes, such as a row and a column, or a position in each of two strings.

Paths in a gridYou move through a grid and count the paths or find the best one.8
KnapsackYou pick items to reach a target sum or fill a capacity.12
Two stringsYou compare two strings one character at a time.14
Splitting a rangeYou choose where to split a range, and each side becomes a smaller problem.6
23String Matchingafter Strings1 pattern · 3 lessons6

These algorithms find a pattern inside a text faster than checking every starting position.

Pattern matchingYou must find a pattern inside a longer string, and checking every start is too slow.6

Sign in to oneby7

Keep your progress, your streak and your code, on any device.

New here? This creates your account too.