Algorithms Roadmap: What Problems Test and What to Learn First
Coding problems look endless, but almost all of them are built from about twenty patterns. This page explains what the problems really test, how to read their limits, and the order to learn the 21 topics on this site, with the problems to solve first in each.
What an Algorithm Problem Really Tests
An interview problem is not a memory test. Two people who have seen the same problem before can still get very different results, because the interviewer is watching how you get to the answer. Most problems check the same five skills:
- Recognizing the pattern. Seeing that "longest substring with no repeats" is a sliding window, or that "shortest path in a grid" is breadth-first search. This is the skill this roadmap trains.
- Choosing the data structure. A hash map for instant lookups, a heap for "the smallest so far", a stack for "the nearest larger value". The right structure often is the solution.
- Reasoning about cost. Saying how the time and memory grow with the input, and whether that fits the limits in the problem.
- Handling edge cases. Empty input, one element, duplicates, negative numbers, values near
. Most wrong answers fail here, not in the main idea.Integer.MAX_VALUE - Writing correct code and explaining it. Clear names, no off-by-one errors, and a short explanation of why it works.
Each problem page on this site follows that order: how to think about it, a walkthrough on an example, the Java solution with its edge cases and a common mistake, and the complexity with the reason behind it.
Read the Limits First
The input limits tell you which solutions can pass before you write any code. A typical judge runs on the order of 108 simple steps per second, so the size of n rules out whole families of solutions. This is a rule of thumb, not a law, but it is right far more often than not:
| Largest n | Complexity that fits | Typical approach |
|---|---|---|
| up to about 10 | O(n!) | Try every ordering: permutations, backtracking |
| up to about 20 | O(2n) | Try every subset: backtracking, bitmask search |
| up to about 500 | O(n3) | Three nested loops, interval DP |
| up to about 5,000 | O(n2) | Two nested loops, 2D dynamic programming |
| up to about 106 | O(n log n) | Sorting, a heap, binary search inside a loop |
| up to about 108 | O(n) | One pass: hash map, two pointers, sliding window |
| larger than that | O(log n) or O(1) | Binary search on the answer, a math formula |
Start by saying the simplest correct solution and its cost, even if it is too slow. It proves you understand the problem, gives you something to test the fast version against, and the limits table then tells you exactly how much faster you need to be.
The Roadmap at a Glance
The 21 topics fall into five phases. Each phase uses the ideas of the one before it: you cannot do graphs comfortably without hash maps and queues, and dynamic programming is much easier once recursion from trees and backtracking feels natural.
For each topic below, the "start here" link goes to an introduction where one exists, and the three problems are a ladder: an easy one to learn the pattern, a medium one to use it, and a harder one to stretch it.
The Five Phases
Almost every harder problem is built on these. The common thread is turning an O(n2) "check every pair" solution into an O(n) or O(n log n) one, by remembering what you have seen (hashing), moving two indexes cleverly (pointers and windows), or using order (sorting and binary search).
Arrays & Hashing
Signal: "have I seen this before?", counting, grouping.
Sliding Window
Signal: "longest" or "shortest" contiguous subarray or substring.
Best Time to Buy and Sell Stock Longest Substring Without Repeating Characters Minimum Window Substring
Binary Search
Signal: sorted data, or "find the smallest value that works".
Sorting
Signal: order makes the rest easy; know how the sorts work.
- You reach for a hash map without thinking whenever a nested loop is only there to look something up.
- You can write a sliding window that grows on the right and shrinks on the left, and say why it is O(n).
- You can write binary search without an off-by-one error, including "find the first index where the condition is true".
Here the solution is mostly picking the right container. A stack remembers things in reverse order, a linked list makes inserts and removals cheap once you hold the node, and a heap always hands you the smallest (or largest) item in O(log n).
Linked List
Signal: pointer rewiring, cycles, the middle of a list.
Heap / Priority Queue
Signal: "top k", "k-th largest", merging sorted streams.
- You can reverse a linked list iteratively and draw the pointers at each step.
- You know when a monotonic stack applies: "for each element, find the nearest larger or smaller one".
- You can say the cost of heap operations and why "top k" with a heap of size k is O(n log k).
Trees teach recursion: solve the problem for the children, then combine. Graphs add cycles, so you also need to remember what you have visited. Breadth-first search finds shortest paths in unweighted graphs, depth-first search explores and detects cycles, and union-find answers "are these connected?" as edges arrive.
Trie
Signal: prefixes, autocomplete, many words at once.
Union Find
Signal: connected groups, merging sets, redundant edges.
- You can write BFS and DFS from memory, on a grid and on an adjacency list, with a visited set.
- You can solve a tree problem by deciding what each recursive call returns to its parent.
- You know why recursion can overflow the stack on a deep tree or a big grid, and how an explicit stack avoids it.
These are ways of searching through choices. Backtracking tries every option and undoes the ones that fail. Greedy commits to the locally best choice, which only works when you can argue it never hurts. Dynamic programming notices that the same sub-problems repeat and stores their answers. Interval problems usually start with sorting by start or end time.
Backtracking
Signal: "all combinations", "all arrangements", small n.
Dynamic Programming
Signal: "number of ways", "minimum cost", overlapping choices.
- You can write the backtracking template (choose, explore, undo) and say why it is exponential.
- You can define a DP state in one sentence, such as "
is the fewest coins that make amount i", and write the transition from it.dp[i] - Before using greedy, you can say why the local choice never blocks a better answer, or find the input where it does.
Smaller topics that show up less often but are easy marks once you know the trick: number properties and overflow, bit operations, walking a 2D grid in place, and designing a class with several operations at the right cost.
Bit Manipulation
Signal: "every element appears twice except one", powers of two.
Design
Signal: "implement a class" with several fast operations.
Recognize the Pattern From the Question
The fastest way to start a new problem is to look for the words that point to a pattern. These are the strongest signals:
| If the problem says | Try first |
|---|---|
| the input is sorted, or "find a pair that sums to" | Two pointers, or binary search |
| "longest" or "shortest" contiguous subarray or substring | Sliding window |
| "the minimum value that still works" (speed, capacity, days) | Binary search on the answer |
| "top k", "k-th largest", "closest k" | Heap of size k |
| "next greater" or "previous smaller" element | Monotonic stack |
| grid or network, "shortest path" with equal steps | Breadth-first search |
| dependencies, "can all tasks finish", ordering | Topological sort (BFS or DFS) |
| "are these connected", groups that merge | Union-find |
| "all combinations", "all permutations", n up to about 20 | Backtracking |
| "number of ways", "minimum cost", "maximum profit" with choices that repeat | Dynamic programming |
| meetings, ranges, overlaps | Sort by start or end, then sweep |
| words sharing prefixes | Trie |
A signal is a starting point, not a rule. Some problems match two patterns, and the limits table above usually tells you which one is fast enough.
How to Practice
- Spend 15 to 20 minutes on your own first. Write the brute force and its cost before looking at anything.
- If stuck, read only "How to Think About It" on the problem page, then try again before reading the solution.
- Trace the walkthrough by hand on paper. If you cannot predict the next step, you do not understand the idea yet.
- Write the solution yourself, then check it against the edge cases and the common mistake listed on the page.
- Say the complexity and why, in one sentence each for time and space, as you would in an interview.
- Come back after a week and solve it again from a blank file. Solving it twice is what makes the pattern stick.
Interviewers change one detail and a memorized answer falls apart. Learn why each step of the solution is there; then a new variation is just the same pattern with a different twist.
Every topic, with all 497 problems, is on the
Recap
- Problems test five skills: recognizing the pattern, choosing the data structure, reasoning about cost, handling edge cases, and writing and explaining correct code.
- Read the limits first: the size of n tells you which complexity can pass before you write any code.
- Follow the phases in order: foundations, data structures, trees and graphs, then techniques. Special topics fit in any time after phase 1.
- In each topic, start with the introduction, then climb the three-problem ladder from easy to hard.
- Practice for understanding: brute force first, trace by hand, and solve each problem twice.