Roadmaps › Placement
DSA Roadmap
Step-by-step path to crack coding interviews — from your first loop to graphs and dynamic programming.
Level: Beginner → Advanced · Duration: 4–6 months
Step 1: Learn one language well
Pick C++, Java or Python and get comfortable with its syntax before starting DSA.
DSA is about thinking, but you think faster when the language never gets in the way. Pick one of C++, Java or Python and get fluent enough that loops, functions and the standard collections come without looking anything up. C++ is fastest and most common in competitive programming, Java is popular in Indian service and product companies, and Python is the quickest to write.
- Input/output, variables, conditions and loops
- Functions and passing values vs references
- Arrays and strings in your language
- The standard library collections (lists, maps, sets, queues)
- Reading compiler/runtime errors calmly
Resources: C++ documentation · Java documentation · Python documentation · ▶ Striver's A2Z DSA Course
Variables, loops & functions
Input/output, conditions, loops and writing small functions.
Every algorithm is built from variables, conditions, loops and functions. Practise until you can write nested loops and small helper functions without hesitation, and know your language's integer limits.
- Data types and integer overflow (use long long / long when needed)
- for, while and nested loops
- Writing and calling functions with parameters and return values
- Solving simple number problems: digits, primes, GCD
Resources: Practice: Basics problems
Arrays & strings in your language
Declaring, traversing and modifying arrays and strings.
Arrays and strings appear in more than half of all interview problems. Learn how to create, traverse, modify and pass them around, and how strings behave in your language (mutable or not).
- Declaring 1D and 2D arrays
- Traversing forwards, backwards and with two indices
- String operations: length, substring, comparison, reversing
- Converting between characters and numbers
Built-in collections
vector/map/set in C++, ArrayList/HashMap in Java, list/dict/set in Python.
You do not need to write a hash map or priority queue from scratch in interviews — use the language's built-ins. Knowing them saves time and avoids bugs.
- C++: vector, map, unordered_map, set, stack, queue, priority_queue
- Java: ArrayList, HashMap, HashSet, ArrayDeque, PriorityQueue
- Python: list, dict, set, deque, heapq
- Time complexity of the common operations on each
Resources: Notes: C++ STL Cheat Sheet · Notes: Java Collections Framework
Fast input/output (optional)
Faster reading/printing for big inputs (sync_with_stdio, BufferedReader, sys.stdin).
On judges with big inputs, slow reading can cause Time Limit Exceeded even when the algorithm is correct. A couple of lines fix it.
- C++: ios::sync_with_stdio(false); cin.tie(nullptr);
- Java: BufferedReader / StreamTokenizer instead of Scanner
- Python: sys.stdin.read().split()
- Building output in one string instead of printing in a loop
Step 2: Time & Space Complexity
Big-O lets you judge if a solution is fast enough before you write it.
Complexity analysis tells you how running time and memory grow as the input grows — before you write any code. It is how you decide whether an idea is fast enough, and interviewers expect you to state the complexity of every solution you give.
- What Big-O measures and why constants are dropped
- Common complexities from O(1) to O(2ⁿ) and O(n!)
- Time vs space trade-offs
- Best, average and worst case
Resources: Notes: Time & Space Complexity (Big-O) · ▶ Algorithms
Big-O, Θ and Ω
Growth rates: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ).
Big-O is an upper bound on growth, Ω a lower bound and Θ a tight bound. In interviews "Big-O" usually means the worst-case growth of your solution.
- The formal idea of an upper bound
- Ranking: 1 < log n < n < n log n < n² < 2ⁿ < n!
- Why O(2n) is still O(n)
Analysing loops & recursion
Count operations in nested loops; recurrence trees for recursion.
For loops, multiply the number of iterations of nested loops; for recursion, count how many calls happen and how much work each does — a recursion tree helps.
- Nested loops and loops that halve (log n)
- Recursion trees and simple recurrences (T(n) = 2T(n/2) + n)
- Space used by the recursion stack
- Amortised cost (e.g. dynamic array push)
Constraints → complexity
n ≤ 10⁵ usually needs O(n log n) or better — read limits first.
The input limits in a problem quietly tell you which complexity is expected. A judge does roughly 10⁸ simple operations per second, so n ≤ 10⁵ rules out O(n²).
- n ≤ 10: O(n!) or O(2ⁿ) is fine
- n ≤ 10³–10⁴: O(n²) usually works
- n ≤ 10⁵–10⁶: aim for O(n log n) or O(n)
- n up to 10¹⁸: you need O(log n) or O(1) maths
Step 3: Arrays & Strings
The base of most interview questions: two pointers, sliding window, prefix sums and hashing.
Most interview questions start with an array or a string. A handful of patterns — two pointers, sliding window, prefix sums and hashing — turn naive O(n²) solutions into O(n) ones. Learn to recognise which pattern a problem is asking for.
- Traversal and in-place modification
- Two pointers and sliding window
- Prefix sums and hashing
- Sorting as a first step
- Common string tricks: frequency arrays, palindromes
Resources: ▶ Sliding Window · Practice: Arrays problems · Practice: Strings problems
Two pointers
Pair sums, reversing, partitioning in O(n).
Two indices move through the array — from both ends towards each other, or one fast and one slow. It solves pair-sum, reversal, partitioning and duplicate-removal problems in a single pass.
- Opposite-ends pointers on a sorted array (pair sum, container with most water)
- Slow/fast pointers for in-place removal
- Partitioning (Dutch national flag)
- Merging two sorted arrays
Resources: Notes: Arrays & Two Pointers · Practice: Hashing & Two Pointers problems
Sliding window
Fixed and variable windows for subarray/substring problems.
A window is a contiguous part of the array that slides forward. Instead of recomputing each window from scratch, add the element entering and remove the one leaving — O(n) instead of O(n·k).
- Fixed-size windows (max sum of size k)
- Variable-size windows that grow and shrink
- Using a hash map inside the window (distinct counts)
- Monotonic deque for window maximum
Resources: Practice: Sliding Window problems
Prefix sums
Answer range-sum queries in O(1) after O(n) preprocessing.
prefix[i] stores the sum of the first i elements, so any range sum becomes one subtraction. Combined with a hash map it also counts subarrays with a given sum.
- Building a prefix array in O(n)
- Range sum queries in O(1)
- Prefix sum + hash map (subarray sum equals k)
- 2D prefix sums for matrices
Resources: Solve: Range Sum Queries
Kadane's algorithm
Maximum subarray sum in one pass.
Kadane's algorithm finds the maximum subarray sum in one pass: at each index either extend the previous subarray or start fresh. It is a first taste of dynamic programming.
- The "extend or restart" idea
- Handling all-negative arrays
- Variants: max product subarray, circular subarray
Resources: Solve: Maximum Subarray Sum
Hashing
Hash maps and sets for counting and fast lookups.
Hash maps and sets give average O(1) lookups. Whenever you think "have I seen this before?" or "how many times does this appear?", reach for a hash map.
- Frequency counting
- Two Sum style "complement" lookups
- Detecting duplicates and grouping (anagrams)
- When a fixed-size array is faster than a hash map
Resources: Solve: Two Sum
Matrix problems (optional)
Spiral order, rotation, set-matrix-zeroes.
Matrices are just 2D arrays, but problems like spiral order, rotation and set-zeroes test careful index handling.
- Row/column traversal and boundaries
- Spiral order with four pointers
- Rotating by 90° (transpose + reverse)
- Marking rows/columns in place
Resources: Solve: Spiral Matrix
Step 4: Recursion & Backtracking
Solve a problem by solving a smaller version of itself; backtracking explores choices and undoes them.
Recursion solves a problem by solving smaller copies of the same problem. Backtracking builds a solution step by step, and when a choice leads nowhere it undoes it and tries the next. Both are the foundation for trees, graphs and dynamic programming.
- Thinking recursively: trust the smaller call
- The call stack and stack overflow
- Generating all choices (subsets, permutations)
- Pruning to make backtracking fast
Resources: ▶ Recursion · ▶ Recursion & Backtracking · Notes: Recursion Basics
Base case & recursive case
Every recursion needs a stopping point and a smaller sub-problem.
Every recursive function needs a base case that stops it and a recursive case that moves towards it. Missing or wrong base cases are the most common recursion bug.
- Writing the base case first
- Factorial, Fibonacci, power and sum-of-digits recursively
- Head vs tail recursion
- Drawing the recursion tree to understand calls
Subsets & permutations
Take / not-take and swapping patterns.
For each element choose "take" or "not take" to generate all 2ⁿ subsets; for permutations, choose which unused element goes next. These two templates solve a huge family of problems.
- Take / not-take recursion for subsets
- Permutations with a used[] array or swapping
- Handling duplicates without repeating answers
- Combination sum style problems
Resources: Solve: Subset Sums · Solve: Permutations of a String
Backtracking
N-Queens, rat in a maze, generating parentheses.
Backtracking = choose, explore, un-choose. Place a queen, recurse, remove it; step into a maze cell, recurse, step back. Checking validity early (pruning) is what keeps it fast.
- The choose → explore → undo template
- N-Queens with column and diagonal sets
- Rat in a maze / word search
- Generating valid parentheses
Resources: Solve: N-Queens · Practice: Recursion & Backtracking problems
Step 5: Searching & Sorting
Binary search on arrays and on answers, plus the classic sorting algorithms.
Binary search cuts the search space in half each step — on a sorted array, and more surprisingly on the answer itself. Sorting algorithms teach divide and conquer, and sorting first simplifies many problems.
- Linear vs binary search
- Lower/upper bound and first/last occurrence
- Binary search on the answer
- Merge sort, quick sort and their complexities
Resources: ▶ Binary Search · Notes: Binary Search · Practice: Binary Search problems
Binary search & bounds
Lower/upper bound, first and last occurrence.
Binary search finds an element in O(log n), but the real skill is finding boundaries — the first position where a condition becomes true. Getting the loop and mid calculation right avoids infinite loops.
- lo, hi and mid = lo + (hi − lo) / 2
- Lower bound and upper bound
- First and last occurrence of x
- Search in a rotated sorted array
Resources: Solve: First and Last Occurrence
Binary search on the answer
Minimise the maximum / maximise the minimum.
When the answer is a number and "can we do it with value X?" is monotonic (if X works, bigger X works too), binary search over X. This solves many "minimise the maximum" problems.
- Spotting a monotonic yes/no check
- Writing the feasibility function
- Koko eating bananas, aggressive cows, book allocation
- Choosing correct low and high bounds
Resources: Solve: Koko Eating Bananas · Solve: Aggressive Cows
Merge sort & quick sort
Divide and conquer; merge sort also counts inversions.
Merge sort splits the array, sorts halves and merges them — always O(n log n) and stable. Quick sort partitions around a pivot — fast in practice but O(n²) in the worst case.
- Divide and conquer
- Merging two sorted halves
- Partitioning around a pivot
- Counting inversions with merge sort
- Stable vs unstable sorting
Resources: Solve: Count Inversions
Counting & radix sort (optional)
Linear-time sorting for small value ranges.
When values are small integers, counting sort beats comparison sorts with O(n + k) time. Radix sort extends the idea digit by digit.
- Counting sort with a frequency array
- When the range k makes it worthwhile
- Radix sort idea
Step 6: Linked List, Stack & Queue
Pointer manipulation and the LIFO/FIFO structures behind many tricks.
Linked lists test pointer manipulation; stacks (last in, first out) and queues (first in, first out) power undo buttons, expression evaluation, BFS and many clever tricks like the monotonic stack.
- Singly and doubly linked lists
- Stack and queue operations and implementations
- Monotonic stack pattern
- Deque for sliding windows
Resources: ▶ Linked List Series · ▶ Stack · Practice: Linked List problems · Practice: Stack & Queue problems
Reverse, middle, cycle
Iterative reversal and slow/fast pointers.
Three classic linked-list skills: reverse a list by re-pointing each node, find the middle with slow and fast pointers, and detect a cycle with Floyd's algorithm.
- Iterative reversal with prev/curr/next
- Slow and fast pointers
- Floyd's cycle detection and finding the cycle start
- Dummy head nodes to simplify edge cases
Resources: Solve: Reverse a Linked List
Stack applications
Balanced brackets, postfix evaluation, min stack.
Whenever the most recent item matters first, think stack: matching brackets, undo, evaluating expressions, function calls.
- Valid parentheses
- Evaluating postfix expressions
- Min stack in O(1)
- Implementing a stack with an array or list
Resources: Solve: Valid Parentheses
Monotonic stack
Next greater element, stock span, largest rectangle.
A monotonic stack keeps elements in increasing or decreasing order. It finds the next/previous greater or smaller element for every position in O(n) total.
- Next greater element
- Stock span
- Largest rectangle in a histogram
- Why each element is pushed and popped only once
Resources: Solve: Next Greater Element
Queue & deque
BFS order and sliding window maximum.
Queues process items in arrival order — the heart of BFS. A deque (double-ended queue) allows pushes and pops at both ends and solves sliding window maximum.
- Queue operations and circular queues
- Deque operations
- Sliding window maximum
- Implementing a queue using two stacks
Resources: Solve: Sliding Window Maximum
Step 7: Trees & BST
Hierarchical data: traversals, heights, paths and binary search trees.
Trees model hierarchies — folders, HTML, organisation charts. Almost every tree problem is solved with recursion: ask what the left and right subtrees return, then combine. Binary search trees add ordering for fast search.
- Tree terminology and representations
- DFS traversals and BFS level order
- Height, diameter and balance
- BST search, insert, delete and validation
Resources: Practice: Trees problems · ▶ Striver Tree Series
Traversals
Inorder, preorder, postorder and level order.
Preorder, inorder and postorder visit nodes in different orders using recursion (or a stack); level order visits level by level using a queue.
- Preorder, inorder, postorder (recursive and iterative)
- Level order with a queue
- Building a tree from level-order input
- Left/right/top view problems
Resources: Solve: Level Order Traversal
Height, diameter, balance
Return values up the recursion.
These problems return a value up the recursion — the height of a subtree — and update a global answer along the way. Learn this pattern once and dozens of problems become easy.
- Height / max depth
- Diameter as left height + right height
- Checking if a tree is balanced in O(n)
- Maximum path sum
Resources: Solve: Diameter of a Binary Tree
Binary search trees
Insert, search, validate, LCA.
In a BST every left subtree is smaller and every right subtree larger than the node. That makes search, insert and delete O(height), and an inorder traversal gives sorted order.
- Search, insert and delete
- Validating a BST with min/max bounds
- Lowest common ancestor in a BST
- Kth smallest element using inorder
Resources: Solve: Validate BST
Advanced trees (optional)
Segment tree and Fenwick tree for range queries.
Segment trees and Fenwick (binary indexed) trees answer range queries with updates in O(log n). They are common in competitive programming and some product-company interviews.
- Segment tree build, query and update
- Fenwick tree for prefix sums
- Tries for prefix/word problems
Step 8: Heaps & Hashing
Priority queues for "top-K" and scheduling problems; hashing for fast lookups.
A heap always gives you the smallest (or largest) item quickly — perfect for scheduling, top-K and merging sorted lists. Hashing gives fast lookups and counting.
- Min-heap and max-heap
- Top-K and K-way merge patterns
- Hash map patterns for counting and grouping
Resources: ▶ Heap
Heap basics
Min-heap / max-heap, push and pop in O(log n).
A binary heap is a complete tree stored in an array where every parent is smaller (min-heap) than its children. Push and pop take O(log n); looking at the top is O(1).
- Heap property and array representation
- Push, pop and heapify
- Using priority_queue / PriorityQueue / heapq
- Heap sort idea
Top-K problems
Keep a heap of size K.
To find the K largest items, keep a min-heap of size K: push each item and pop when the heap grows beyond K. This runs in O(n log k).
- K largest / smallest elements
- K most frequent elements
- Merge K sorted lists
- Median of a data stream with two heaps
Hash map patterns
Frequency counts, grouping, prefix sum + map.
Most hashing problems are one of a few patterns: count frequencies, store "seen" values, map a key to its group, or map prefix sums to counts.
- Frequency maps
- Group anagrams
- Longest consecutive sequence with a set
- Prefix sum + hash map
Resources: Practice: Hashing & Two Pointers problems
Step 9: Graphs
Networks of nodes: BFS, DFS, shortest paths and more.
Graphs model anything with connections — cities and roads, friends, prerequisites, web pages. Learn to represent them, traverse them with BFS and DFS, and apply classic algorithms for cycles, ordering, shortest paths and connectivity.
- Adjacency list vs adjacency matrix
- BFS and DFS on graphs and grids
- Topological sort and cycle detection
- Shortest paths (BFS, Dijkstra)
- Disjoint Set Union and spanning trees
Resources: ▶ Graph Series · Practice: Graphs problems
BFS & DFS
Representation (adjacency list) and traversals.
BFS explores level by level with a queue and finds shortest paths in unweighted graphs; DFS goes deep with recursion or a stack and is great for connectivity and cycles. Grids are graphs too.
- Building an adjacency list
- BFS with a visited array
- DFS recursively and iteratively
- Connected components and number of islands
- Multi-source BFS (rotting oranges)
Resources: Solve: Number of Islands
Cycle detection & topological sort
Undirected cycles; Kahn's algorithm for DAGs.
In undirected graphs a cycle exists if DFS reaches a visited node that is not its parent. In directed graphs, topological sort orders tasks so every prerequisite comes first — possible only if there is no cycle.
- Cycle detection in undirected graphs (DFS / DSU)
- Cycle detection in directed graphs (colours / Kahn)
- Kahn's algorithm with indegrees
- Course schedule style problems
Resources: Solve: Course Schedule
Shortest paths
BFS for unweighted, Dijkstra for weighted graphs.
BFS gives shortest paths when every edge costs the same. Dijkstra handles non-negative weights using a min-heap; Bellman-Ford handles negative edges.
- BFS distances in unweighted graphs
- Dijkstra's algorithm with a priority queue
- Bellman-Ford and negative cycles
- Multi-state shortest paths (e.g. with a coupon)
Resources: Solve: Dijkstra's Shortest Paths
Disjoint Set Union
Union–find with path compression.
DSU (union–find) keeps track of which items are in the same group, with near-constant-time union and find thanks to path compression and union by size.
- find with path compression
- union by rank/size
- Detecting cycles and counting components
- Using DSU in Kruskal's algorithm
Resources: Solve: Detect Cycle (DSU)
Minimum spanning tree (optional)
Kruskal's and Prim's algorithms.
A minimum spanning tree connects all nodes with the least total edge weight. Kruskal adds the cheapest safe edges using DSU; Prim grows a tree with a heap.
- Kruskal's algorithm
- Prim's algorithm
- Applications: network design, clustering
Step 10: Dynamic Programming
Remember answers to sub-problems instead of recomputing them.
Dynamic programming solves problems with overlapping sub-problems by remembering answers instead of recomputing them. The hard part is defining the state — what dp[i] or dp[i][j] means — and the transition between states.
- Recognising DP problems (choices + overlapping sub-problems)
- Memoisation (top-down) vs tabulation (bottom-up)
- Defining state and transitions clearly
- Space optimisation by keeping only needed rows
Resources: ▶ Dynamic Programming · ▶ Dynamic Programming Series · Practice: Dynamic Programming problems
1D DP
Climbing stairs, house robber.
Start with problems where the state is a single index: the answer for i depends on a few earlier answers. Climbing stairs and house robber are the classic first steps.
- Fibonacci-style recurrences
- Climbing stairs, house robber, frog jump
- Converting recursion → memoisation → tabulation
- Reducing O(n) space to O(1)
Resources: Solve: House Robber
2D / grid DP
Grid paths, minimum path sum.
In grid problems the state is a cell (i, j) and you usually come from the cell above or to the left. Count paths, find minimum cost paths and handle obstacles.
- Unique paths with and without obstacles
- Minimum path sum
- Triangle and falling path problems
- Using one row instead of a full table
Resources: Solve: Minimum Path Sum
Knapsack family
0/1 knapsack, coin change, subset sum.
Knapsack problems pick items under a capacity. 0/1 knapsack uses each item once; unbounded knapsack (coin change) allows repeats. Many "subset" problems are knapsack in disguise.
- 0/1 knapsack and the reverse loop trick
- Subset sum and equal partition
- Coin change: minimum coins and number of ways
- Unbounded knapsack and rod cutting
Resources: Solve: 0/1 Knapsack
DP on strings
LCS, edit distance, palindromes.
Two-string problems use dp[i][j] for prefixes of both strings. Longest common subsequence and edit distance are the templates for most of them.
- Longest common subsequence / substring
- Edit distance
- Longest palindromic subsequence
- Printing the actual answer, not just its length
Resources: Solve: Edit Distance
LIS
O(n²) DP and the O(n log n) patience method.
Longest increasing subsequence has an O(n²) DP and a clever O(n log n) method that keeps the smallest possible tail for each length and uses binary search.
- O(n²) DP solution
- O(n log n) with tails + binary search
- Variants: largest divisible subset, Russian doll envelopes
Resources: Solve: LIS
DP on trees & bitmask DP (optional)
For harder interviews and contests.
Tree DP computes answers for each subtree in a DFS; bitmask DP uses the bits of an integer to represent a set of chosen items, for small n (≤ 20).
- DP on trees (e.g. house robber on a tree)
- Rerooting technique
- Bitmask DP (travelling salesman for small n)
Step 11: Greedy & Bit Manipulation (optional)
Locally best choices that are globally optimal, and tricks with bits.
Greedy algorithms make the locally best choice at each step — fast and simple, but only correct when you can argue the choice is safe. Bit manipulation solves some problems in O(1) using binary tricks.
- When greedy works and how to justify it
- Sorting first, then choosing
- Binary representation and bitwise operators
Resources: Practice: Greedy problems · Practice: Bit Manipulation problems
Interval scheduling
Sort by end time.
To fit the most meetings in one room, always pick the one that ends earliest. Interval problems often start by sorting by start or end time.
- Activity selection / N meetings
- Merge overlapping intervals
- Minimum platforms
- Jump game
Resources: Solve: N Meetings in One Room
Bit tricks
x & (x−1), XOR properties.
Bitwise operators work on the binary form of numbers. A few identities — x ^ x = 0, x & (x − 1) clears the lowest set bit — solve surprising problems.
- AND, OR, XOR, NOT and shifts
- Check, set and clear the i-th bit
- Count set bits and power-of-two check
- Single number with XOR
Resources: Solve: Single Number
Step 12: Interview practice
Mix all topics, time yourself and explain your approach out loud.
Knowing algorithms is not the same as passing interviews. Practise mixed problems under time pressure, explain your thinking out loud, and review mistakes until you see the patterns instantly.
- Solving mixed-topic sets with a timer
- Explaining approach and complexity before coding
- Testing with edge cases
- Keeping a revision list of problems you got wrong
Resources: Interview questions: DSA · Weekly contests · ▶ Striver's A2Z DSA Course
Company-wise sheets
Practise what your target companies ask.
Companies repeat their favourite problem types. Before an interview, practise the problems commonly reported for that company.
- Service companies: arrays, strings, basic maths and patterns
- Product companies: graphs, DP, trees and design
- Revising each company sheet a week before the interview
Resources: Company sheets
Weekly contests
Solve under time pressure every week.
Contests train you to read quickly, pick an approach and code it correctly under pressure — exactly what online assessments test. Always "upsolve" the problems you could not finish.
- Taking part every week
- Upsolving after the contest
- Tracking your rating or rank over time
Resources: Contests
Mock interviews
Explain approach → code → test with a friend.
A mock interview with a friend reveals gaps you will not notice alone: going silent, jumping into code too early, forgetting edge cases.
- Clarify → approach → code → test structure
- Thinking out loud
- Handling hints and getting unstuck
- Reviewing feedback after each mock