DSA Patterns

Most interview problems are one of about twenty shapes wearing a costume. Spotting the shape is harder than writing the code, so each entry below leads with the signal that gives the pattern away and follows with a template short enough to reproduce under pressure.

When nothing jumps out, work through four questions in order: what do the constraints allow, what shape is the input, what shape is the answer, and what words does the problem use. The tables below answer them one at a time. Any one of the four can be enough on its own, and two agreeing is usually conclusive.

Java API details live in collections. For the wider checklist of what to learn, and which named patterns map to which section here, see topics.

Read the signal

Words that give it away

Problem statements reuse the same phrases. When you see one of these, it is worth checking the matching pattern before anything else.

Input shape

The type of the input narrows the field before you have read the question properly.

Output shape

What the answer looks like is as strong a hint as the input.

Budget by input size

The constraint tells you the intended complexity, which usually tells you the pattern. If n is small the expensive answer is the intended one, and if n is large anything with a nested loop is already wrong.

Study order

If you are starting from nothing, work down this list rather than across the page. The right column is how often the group shows up in interviews, so the top four earn most of your practice time.

Sliding window

A window over a contiguous run. The right edge always moves forward, the left edge follows when the window breaks a rule. Both pointers only move right, which is why it stays linear.

Problems: longest substring without repeats, minimum window substring, max sum subarray of size k, fruit into baskets.

Two pointers

Two indices walking a sorted structure. Each comparison lets you throw away one end, so you never need the nested loop.

Problems: two sum on a sorted array, 3Sum, container with most water, palindrome check, squares of a sorted array.

Fast and slow pointers

One pointer moves one step, the other moves two. If there is a cycle they eventually meet. Constant space, which is the whole reason to use it.

Problems: linked list cycle, find the duplicate number, happy number, middle of a list, palindrome linked list.

Cyclic sort

When an array holds the numbers 1 to n in some order, every value has one correct home: value v belongs at index v - 1. Walk the array putting each value where it belongs, and whatever is left out of place is the missing or duplicated number. O(n) time, O(1) space, no hash set.

Problems: missing number, find all numbers disappeared in an array, find the duplicate number, first missing positive, set mismatch.

Linked list surgery

Rewiring a list is pointer bookkeeping. Save the next node before you overwrite the link, and use a dummy head so the first node needs no special case.

Problems: reverse linked list, merge two sorted lists, remove nth node from end, reorder list, add two numbers.

Binary search

Halve the search space each step. It applies whenever you can ask a yes or no question whose answer flips exactly once across the range, so the input does not have to be a sorted array.

Problems: search in a rotated array, find minimum in a rotated sorted array, first and last position, Koko eating bananas, split array largest sum, capacity to ship packages.

DFS

Go as deep as possible, then unwind. Recursion gives you the stack for free. On a grid, overwrite the cell as you visit it so you do not need a separate seen array.

Problems: number of islands, flood fill, clone graph, path sum, surrounded regions.

BFS

Explore level by level, so the first time you reach a node you reached it in the fewest steps. That is the only reason to prefer it over DFS for shortest paths on unweighted edges.

Problems: word ladder, rotting oranges, shortest path in a binary matrix, level order traversal, open the lock.

Binary tree traversal

Three depth first orders, separated only by where you touch the node relative to the recursive calls. Preorder reads the root first, which is what you want when copying or serialising a tree. Inorder on a binary search tree emits sorted values. Postorder finishes the children first, which is what you want when a node's answer depends on its subtrees, such as height or diameter.

Problems: invert binary tree, maximum depth, lowest common ancestor, validate BST, construct tree from preorder and inorder, serialize and deserialize binary tree.

Topological sort

An ordering of a directed acyclic graph where every edge points forward. Kahn's algorithm repeatedly takes a node with no remaining prerequisites.

Problems: course schedule I and II, alien dictionary, minimum height trees, parallel courses.

Union-Find

Keeps track of which elements are in the same group. Two operations: find the representative of a group, and merge two groups. Path compression plus union by rank makes both effectively constant time.

Problems: number of provinces, redundant connection, detect a cycle in an undirected graph, accounts merge, Kruskal's minimum spanning tree.

Backtracking

Build a candidate one choice at a time, and undo the choice when you come back. It is brute force with early exits, so the interesting work is in the pruning.

Problems: subsets, permutations, combination sum, N-Queens, word search, Sudoku solver.

Dynamic programming

Use it when the problem has overlapping subproblems and an optimal answer built from optimal smaller answers. Write the recurrence first in words, then pick a direction.

Problems: climbing stairs, house robber, coin change, longest increasing subsequence, edit distance, 0/1 knapsack, unique paths.

Greedy

Take the best looking option at each step and never revisit it. That gives short, fast code on the problems where it is valid, and confidently wrong answers on the ones where it is not.

Almost every greedy solution starts with a sort. If you have decided the problem is greedy, sorting is the first line to write, and the only real question is what to sort by.

Problems: activity selection, jump game, gas station, non-overlapping intervals, task scheduler.

Merge intervals

Sort by start time, then walk the list. Each interval either overlaps the one you are holding, in which case you stretch it, or it does not, in which case you close the current one and start a new one. Sorting is what makes a single pass enough.

Problems: merge intervals, insert interval, non-overlapping intervals, meeting rooms I and II, interval list intersections.

Prefix sum

Precompute running totals so any range sum is one subtraction. Only works when the array does not change between queries.

Problems: range sum query, subarray sum equals k, contiguous array, product of array except self.

Difference array

The mirror of prefix sum. Cheap range updates, one rebuild at the end. Use it when updates far outnumber reads.

Problems: range addition, corporate flight bookings, car pooling.

Stack

Last in, first out. Reach for it whenever the most recent unresolved thing is the one you need next, which is exactly what nested brackets and postfix expressions are.

Problems: valid parentheses, evaluate reverse Polish notation, min stack, simplify path, basic calculator.

Monotonic stack

A stack whose values stay sorted. Each element is pushed and popped at most once, so a scan that looks quadratic runs in linear time.

Problems: next greater element, daily temperatures, largest rectangle in histogram, trapping rain water, remove k digits.

Monotonic deque

Same idea, but you also drop elements that have slid out of the window, so it answers maximum or minimum for every window position.

Problems: sliding window maximum, shortest subarray with sum at least k, constrained subsequence sum.

Heap

A partial order, cheaper than sorting when you only need the extremes. For the kth largest, keep a min heap of size k and evict the head whenever it overflows.

Problems: kth largest element, top k frequent elements, merge k sorted lists, find median from a data stream, task scheduler.

Two heaps

Split the data down the middle and hold each half in its own heap: a max heap over the smaller values and a min heap over the larger ones. Keep their sizes within one of each other and the median is always sitting on top.

Problems: find median from a data stream, sliding window median, IPO, longest continuous subarray with absolute diff within a limit.

K-way merge

Merging k sorted sequences pairwise costs O(nk). Put one candidate from each sequence in a min heap instead, and every step picks the global smallest in O(log k).

Problems: merge k sorted lists, kth smallest element in a sorted matrix, smallest range covering elements from k lists, find k pairs with smallest sums.

Trie

A tree keyed by characters, so lookup costs the length of the word rather than the size of the dictionary. Worth it when you query by prefix.

Problems: implement trie, word search II, replace words, design add and search words.

Fenwick tree

Prefix sums that survive updates, in O(log n) each. Shorter to write than a segment tree, which is why it wins when you only need sums.

Problems: range sum query mutable, count of smaller numbers after self, reverse pairs.

Bit manipulation

Integers as sets of flags. Useful for subset enumeration and for tricks where pairs cancel out.

Problems: single number, counting bits, subsets, maximum XOR of two numbers, bitwise AND of a range.

Matrix traversal

A grid is a graph where the neighbours are implicit. Keep one direction array and reuse it everywhere.

Problems: number of islands, spiral matrix, rotate image, set matrix zeroes, diagonal traverse, word search.

Math and geometry

Some problems reduce to plain arithmetic once you see past the framing. Euclid's algorithm is the one to have memorised.

Problems: greatest common divisor of strings, count primes, power of two, happy number, max points on a line, k closest points to the origin.

Game theory

Two players alternate, both play perfectly, and you are asked who wins or what the best score is. A position is winning for you exactly when some move leaves your opponent in a losing position.

Problems: Nim game, stone game, predict the winner, can I win.

Hashing

The default answer for "have I seen this before" and "how many times". Group by choosing the right key: a sorted string for anagrams, a canonical shape for patterns, a running sum for subarrays.

Problems: two sum, group anagrams, longest consecutive sequence, LRU cache, first unique character.

Design

Some questions ask you to build a structure rather than answer a question about one. The move is almost always to combine two structures so that each covers the other's weak operation: a hash map gives O(1) lookup but no order, a linked list gives O(1) reordering but no lookup, so together they give both.

Problems: LRU cache, LFU cache, min stack, implement queue using stacks, flatten nested list iterator, insert delete getRandom in O(1), design Twitter.

Concurrency

Rare in most interview loops and standard in a few. The recurring shape is producer and consumer: one thread fills a buffer, another drains it, and neither may proceed when the buffer is in the wrong state.

Problems: print in order, print FooBar alternately, building H2O, the dining philosophers, bounded blocking queue.