Patterns
- 1 Hash Maps and Prefix Sums Many array questions hide a nested loop: for each element, search the rest for something that fits. This pattern removes the inner loop. You walk the array once and keep a hash map of what you have already seen, so the "search" becomes a single O(1) lookup. Add a running total (a prefix sum) and ...
- 2 Two Pointers Two pointers is what you do when a pair search would be O(n²) but the data has an order you can exploit. Two indexes move through the array, and every move rules out a whole set of candidates at once, so the total work is O(n). It needs O(1) extra space, which makes it the answer when an intervie...
- 3 Sliding Window A sliding window looks at a contiguous range [left, right] and updates its state as the range moves, instead of recomputing every subarray from scratch. The right edge moves forward every step. The left edge moves forward only when the window breaks a rule. Because neither edge ever goes back, ea...
- 4 Binary Search Binary search is not only "find x in a sorted array". The general version is: you have a yes/no question ok(x) whose answers go no, no, …, no, yes, yes, …, yes as x grows, and you want the first yes. Each step checks the middle and throws away half the range, so it takes O(log n) checks.
- 5 Intervals Interval questions give you pairs like [start, end]: meetings, bookings, time ranges, IP ranges. Comparing every pair is O(n²). The fix is almost always the same first move: sort by start. After that, any interval can only overlap the ones right before it, and one pass is enough.
- 6 Stacks and Monotonic Stacks A stack fits any problem where the most recent unfinished thing is the first one you can finish. Brackets are the classic case: the last bracket you opened is the first one that may close. A monotonic stack adds one rule, that values on the stack stay in sorted order, and it solves a whole family...
- 7 Linked List Techniques Linked list questions rarely need clever algorithms. They need careful pointer moves without losing the rest of the list. Four techniques cover nearly every interview question, and they combine: "reorder list" is find the middle, reverse the second half, then merge.
- 8 Heaps and Top-K A heap gives you the smallest (or largest) item in O(1) and lets you add or remove items in O(log n). That makes it the tool for "best so far" questions: the k largest values, the k closest points, the next event in time order, the median of a stream. You never sort everything, you only keep what...
- 9 Tree DFS Depth-first search on a tree is recursion: solve the problem for the left subtree, solve it for the right subtree, combine. The hard part is not the traversal but deciding which way information flows. Bottom-up, a node needs its children's answers (height, sum, "is this subtree balanced?"). Top-d...
- 10 Tree BFS Breadth-first search uses a queue: take a node from the front, add its children to the back. Nodes come out in order of depth, so BFS is the natural tool whenever a question talks about levels, or wants the node closest to the root. One small trick turns the plain traversal into a level-by-level ...
- 11 Graph BFS and DFS Graph search is tree search plus one rule: remember where you have been, because a graph can lead you back to a node you already saw. With a visited set, both DFS and BFS visit every node and edge once, O(V + E). DFS is the simplest way to explore everything reachable (count islands, clone a grap...
- 12 Topological Sort Some problems are about order under constraints: course B needs course A, package X needs package Y, letter t comes before f in an alien alphabet. Draw an arrow from "must happen first" to "happens after", and you have a directed graph. A topological order lists the nodes so that every arrow poin...
- 13 Backtracking When a question asks for all subsets, permutations, combinations, board placements or word paths, there is usually no shortcut: you have to generate them. Backtracking does that with one recursive shape. Keep a partial answer, try each possible next choice, recurse, then undo the choice and try t...
- 14 Dynamic Programming: 1D Dynamic programming is recursion that remembers. If the brute-force recursion solves the same smaller problem many times, store each answer the first time and reuse it. In one-dimensional DP, a smaller problem is described by one number: a prefix of the array, an amount of money, a position in a ...
- 15 Dynamic Programming: 2D Two-dimensional DP is the same method as DP 1D, with one more number in the state. A subproblem is now "the first i characters of one string and the first j of the other", or "the cell at row r, column c", or "the substring from i to j". The table is a grid, and each cell is filled from a few nei...
- 16 Greedy A greedy algorithm builds the answer one step at a time and always takes the choice that looks best right now: the meeting that ends first, the farthest reachable index, the largest coin. It never revisits a choice. When it works, it is usually one pass after a sort: O(n) or O(n log n), with very...
- 17 Matrix and Simulation Some problems have no clever trick. A grid has to be rotated, walked in a spiral, or moved forward one step by fixed rules, and the whole difficulty is doing exactly what the statement says without an off-by-one. Interviewers like them because they show whether you can keep indices straight under...
- 18 Data Structure Design "Design a class that supports these operations" is its own kind of coding question. LRU Cache is the famous one, and many companies now run whole rounds this way: build a small key-value store, a bank, a rate limiter or a spreadsheet, then add a new requirement every fifteen minutes. No single al...