Coding Questions to Memorise: The Pattern Templates That Crack the Coding Interview
Coding questions to memorise for interviews: the pattern templates — two pointers, sliding window, binary search, backtracking, DP — that solve most coding interview questions from memory.
It’s the night before the round and you’ve got a spreadsheet of two hundred problems open, that quiet dread rising: there’s no way you memorise two hundred solutions by morning. Here’s the secret the spreadsheet hides — you don’t have to. Those two hundred problems are really about fifteen ideas wearing two hundred costumes. Learn to see the idea under the costume and to write it down without thinking, and the whole list collapses into something you can hold in your head tonight.
That’s what this page is: the muscle-memory sheet. Not two hundred answers — a short shelf of patterns, each with a template you can reproduce cold and a tell that screams "use me." By the end you and I will have gone through the shelf, and you’ll be able to (a) read a fresh question and name the pattern it wants in about ten seconds, and (b) write that pattern’s skeleton from memory before you’ve even finished reading the examples.
Let’s start nowhere near a computer
Ask a jazz pianist how they improvise a solo they’ve never played and they’ll shrug: scales. They drilled a dozen scales until the fingers own them, and every solo is those scales recombined on the fly. Ask a chef how they invent a sauce and you’ll hear the same shape of answer: the mother sauces. French kitchens teach five — béchamel, velouté, espagnole, tomato, hollandaise — and every one of the hundreds of sauces on the menu is a mother sauce with something stirred in. Nobody memorises hundreds of recipes. They memorise five foundations and derive the rest at the stove.
Coding rounds work exactly like the kitchen. There’s a small pantry of foundational patterns — a way to walk an array from both ends, a way to slide a window, a way to halve a search space, a way to try every combination and back out of dead ends. Each one is a mother sauce. The problem on the whiteboard is the plated dish. Your job isn’t to have cooked that exact dish before; it’s to taste it, recognise which foundation it’s built on, and reach for the base you already know by heart.
The mental shift that makes interviews stop feeling like a memory contest: stop collecting problems, start collecting patterns. A pattern is a template plus a tell — the reusable code and the signal in the question that says "this one." Ten templates you can write blindfolded beat a hundred solutions you half-remember.
Where you already meet this
You lean on these patterns every day without naming them. The autocomplete in your search bar is a binary search into a sorted word list. The "you have 3 unread in 2 chats" badge is a frequency count over a stream. Undo/redo is a pair of stacks. The "people you may know" suggestions are a breadth-first walk two hops out in a friend graph. A build system deciding what to recompile first is a topological sort of the dependency graph.
The one worth pausing on is your music app’s "skip to the next song louder than this one" — or, less whimsically, the stock ticker that flags "the next day the price went up." Both are the monotonic stack pattern: you keep a shrinking pile of "still waiting for something bigger," and each new value resolves everyone it beats in one sweep. You’ve met the pattern; you just hadn’t been introduced. The rest of this page is the introductions — and the templates that come with them.
What it actually looks like
Before any code, here’s the whole shelf on one wall: the pattern on the left, the questions it unlocks on the right. This is the map you’re building toward — read a new problem, find the row it belongs to, and the template comes for free.
Two hundred problems, a dozen-ish rows. The art of the coding round is almost entirely routing — getting from the question to the right row fast — and only then writing, which is easy once you’re in the right row because the template is already in your fingers. So let’s learn the routing first, then fill the shelf.
How to read a question in ten seconds
Before you reach for a pattern, let the shape of the input tell you which one it wants. Almost every question leaks its pattern in the first sentence, if you know the tells.
You don’t run down this list consciously for long — after fifty problems it’s a reflex, the way the pianist doesn’t "decide" which scale. But while it’s still deliberate, this strip is the fastest triage you own. Now the shelf itself, one jar at a time. Each entry is the same three things: the tell, the template, and the questions it cracks.
Two pointers
The tell. A sorted array (or one you can sort), and you’re hunting for a pair or comparing the two ends — "find two numbers that sum to X," "is this a palindrome," "most water between two walls." Whenever the brute force is a double loop over pairs, ask whether one finger at each end can do it in a single pass.
static int[] twoSumSorted(int[] a, int target) {
int l = 0, r = a.length - 1;
while (l < r) {
int sum = a[l] + a[r];
if (sum == target) return new int[] {l, r};
if (sum < target) l++; // need bigger → raise the low end
else r--; // need smaller → lower the high end
}
return new int[] {-1, -1};
}The rule in plain words: each comparison throws away one end, because sortedness means the discarded end can’t be part of any better pair. That’s the whole O(n) win over the O(n²) double loop.
- Cracks: two-sum on a sorted array, valid palindrome, reverse a string in place, merge two sorted arrays, container with most water, 3-sum (sort, then fix one and two-pointer the rest).
- Deep dive: the two-pointers technique.
Sliding window
The tell. A contiguous subarray or substring, and a phrase like "longest," "shortest," "at most K," or "sum equals." The word contiguous is the giveaway — you’re not choosing scattered elements, you’re sliding a frame along the line.
static int lengthOfLongestSubstring(String s) {
Map<Character, Integer> last = new HashMap<>();
int best = 0, left = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (last.containsKey(c) && last.get(c) >= left) {
left = last.get(c) + 1; // jump the window past the repeat
}
last.put(c, right);
best = Math.max(best, right - left + 1);
}
return best;
}The rule: the right edge always moves forward; the left edge only catches up when the window breaks its rule. Both edges travel the array once, so it’s O(n), not the O(n²) of re-checking every substring.
- Cracks: longest substring without repeating characters, minimum window substring, longest substring with at most K distinct, max sum of a size-K subarray, permutation-in-string.
- Deep dive: the sliding window.
Binary search (including on the answer)
The tell. Anything sorted, or anything where you can ask a yes/no question whose answers are all "no" and then all "yes." That second half is the sneaky, high-value one — binary search on the answer — where the array isn’t sorted but the feasibility is.
static int lowerBound(int[] a, int target) {
int lo = 0, hi = a.length; // half-open range [lo, hi)
while (lo < hi) {
int mid = lo + (hi - lo) / 2; // never lo + hi — that can overflow
if (a[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo; // first index with a[i] >= target
}When the answer is a number you’re minimising — the smallest ship that clears the cargo in D days, the slowest eating speed — binary-search the number and write a feasible(guess) check instead of comparing array cells:
static int shipWithinDays(int[] weights, int days) {
int lo = 0, hi = 0;
for (int w : weights) { lo = Math.max(lo, w); hi += w; }
while (lo < hi) {
int cap = lo + (hi - lo) / 2;
if (feasible(weights, days, cap)) hi = cap; // works → try smaller
else lo = cap + 1; // fails → need bigger
}
return lo;
}
static boolean feasible(int[] weights, int days, int cap) {
int need = 1, load = 0;
for (int w : weights) {
if (load + w > cap) { need++; load = 0; }
load += w;
}
return need <= days;
}The rule: each step halves the search space, so a billion possibilities cost about thirty checks — O(log n). The half-open [lo, hi) convention and lo + (hi - lo) / 2 are the two habits that kill the off-by-one and overflow bugs that fail this pattern.
- Cracks: search in a rotated sorted array, first/last position of a target, find peak element, Koko eating bananas, capacity to ship packages in D days, split array largest sum.
- Deep dive: binary search.
Fast and slow pointers (cycle detection)
The tell. A linked list, or any "next" relationship where you must detect a loop or find the middle without knowing the length — and you’re told not to use extra space.
static int findDuplicate(int[] nums) {
int slow = nums[0], fast = nums[0];
do { // phase 1: find a meeting point
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
slow = nums[0]; // phase 2: walk to the cycle entrance
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}The rule: one pointer moves twice as fast; if there’s a loop, they must meet inside it. Restarting one pointer at the head and stepping both one-at-a-time lands them exactly on the loop’s entrance — the trick behind "find the duplicate number" and "linked-list cycle II." O(n) time, O(1) space.
- Cracks: detect a cycle in a linked list, find where the cycle starts, find the middle node, is a number "happy," find the duplicate in an array of n+1 numbers.
- Deep dive: the linked list.
Prefix sums
The tell. Repeated range-sum questions, or "count the subarrays that sum to K." A running total you can subtract turns an O(n) re-scan per query into one lookup.
static int subarraySum(int[] nums, int k) {
Map<Integer, Integer> seen = new HashMap<>();
seen.put(0, 1); // the empty prefix
int sum = 0, count = 0;
for (int n : nums) {
sum += n;
count += seen.getOrDefault(sum - k, 0); // a past prefix completes a window
seen.merge(sum, 1, Integer::sum);
}
return count;
}The rule: the sum of nums[i..j] is prefix[j] - prefix[i-1]. Store prefixes in a map and every "does some subarray sum to K?" becomes "have I seen sum - k before?" — O(n).
- Cracks: range sum query (immutable), subarray sum equals K, contiguous array (equal 0s and 1s), pivot index, product of array except self (prefix/suffix products).
- Related: hash tables.
Frequency counting and hashing
The tell. "Anagram," "duplicate," "seen before," "count of each," "first unique." Any time membership or a tally is the real question, a HashMap (or a 26-slot array for letters) is the answer.
static Map<String, List<String>> groupAnagrams(String[] words) {
Map<String, List<String>> groups = new HashMap<>();
for (String w : words) {
char[] key = w.toCharArray();
Arrays.sort(key); // sorted letters = a shared fingerprint
groups.computeIfAbsent(new String(key), z -> new ArrayList<>()).add(w);
}
return groups;
}The rule: turn each item into a key that collides exactly when they’re "the same," then let the map do the grouping in O(1) per item. The unsorted two-sum lives here too — remember each number’s complement as you go.
- Cracks: two-sum (unsorted), group anagrams, valid anagram, first unique character, longest consecutive sequence, contains duplicate.
- Deep dive: hash tables.
Monotonic stack and valid parentheses
The tell. "Next greater element," "how many days until a warmer temperature," "largest rectangle," or anything with nested brackets. You need a pile that remembers "still waiting for its match."
static int[] nextGreater(int[] a) {
int[] res = new int[a.length];
Arrays.fill(res, -1);
Deque<Integer> stack = new ArrayDeque<>(); // indices, values decreasing
for (int i = 0; i < a.length; i++) {
while (!stack.isEmpty() && a[stack.peek()] < a[i]) {
res[stack.pop()] = a[i]; // a[i] answers everyone it beats
}
stack.push(i);
}
return res;
}Brackets are the same pile with a simpler match rule — push openers, pop and check on each closer:
static boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
Map<Character, Character> match = Map.of(')', '(', ']', '[', '}', '{');
for (char c : s.toCharArray()) {
if (match.containsKey(c)) {
if (stack.isEmpty() || stack.pop() != match.get(c)) return false;
} else {
stack.push(c);
}
}
return stack.isEmpty();
}The rule: each element is pushed and popped at most once, so the whole sweep is O(n) even though it looks nested. The stack holds exactly the unresolved items.
- Cracks: valid parentheses, next greater element, daily temperatures, largest rectangle in histogram, min stack, evaluate reverse-Polish notation.
- Deep dive: the stack.
Heap and top-K
The tell. "K largest," "K most frequent," "K closest," "median of a stream," "merge K sorted lists." You want the extreme few, not a full sort — a heap gives you the running best in O(log k).
static int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int n : nums) freq.merge(n, 1, Integer::sum);
// min-heap of size k, keyed by frequency: the smallest sits on top to be evicted
PriorityQueue<Integer> heap = new PriorityQueue<>((x, y) -> freq.get(x) - freq.get(y));
for (int key : freq.keySet()) {
heap.offer(key);
if (heap.size() > k) heap.poll(); // drop the least frequent so far
}
int[] res = new int[k];
for (int i = 0; i < k; i++) res[i] = heap.poll();
Arrays.sort(res);
return res;
}The rule: keep a heap of size K, evict the weakest each time — total O(n log k), which beats the O(n log n) of sorting everything when K is small. For a stream, that heap is the only state you carry.
- Cracks: kth largest element, top-K frequent, K closest points to origin, merge K sorted lists, find median from a data stream (two heaps).
- Deep dive: heaps and priority queues.
Interval merge
The tell. A list of [start, end] ranges and words like "overlap," "merge," "insert," "meeting rooms." The universal first move is sort by start, then sweep once.
static int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0]));
List<int[]> out = new ArrayList<>();
for (int[] iv : intervals) {
int last = out.size() - 1;
if (out.isEmpty() || out.get(last)[1] < iv[0]) {
out.add(iv); // no overlap → new block
} else {
out.get(last)[1] = Math.max(out.get(last)[1], iv[1]); // extend the block
}
}
return out.toArray(new int[0][]);
}The rule: once sorted by start, an interval either extends the current block or begins a new one — a single O(n log n) pass (the sort dominates).
- Cracks: merge intervals, insert interval, non-overlapping intervals (min removals), meeting rooms I and II, interval list intersections.
Trees: BFS and DFS (including inorder)
The tell. A binary tree and "level order" (that’s BFS, a queue) versus "path," "depth," "validate," or "sum" (that’s DFS, recursion). And the special one: inorder traversal of a binary search tree visits the values in sorted order — the answer to a whole family of BST questions.
static void inorder(TreeNode node, List<Integer> out) {
if (node == null) return;
inorder(node.left, out); // left subtree first
out.add(node.val); // then the node
inorder(node.right, out); // then the right subtree
}static List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> levels = new ArrayList<>();
if (root == null) return levels;
Queue<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size(); // freeze this level's width
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode n = q.poll();
level.add(n.val);
if (n.left != null) q.offer(n.left);
if (n.right != null) q.offer(n.right);
}
levels.add(level);
}
return levels;
}The rule: DFS recurses (the call stack is your stack); BFS uses an explicit queue and processes one full level per outer loop. Inorder on a BST is your go-to whenever a question smells like "sorted order" over a tree.
- Cracks: inorder/preorder/postorder traversal, level-order & zigzag, max depth, validate a BST (inorder is strictly increasing), kth smallest in a BST, lowest common ancestor.
- Deep dive: binary trees, breadth-first search.
The backtracking template
The tell. "All permutations," "all subsets," "all combinations," "generate every valid…," "N-queens," "word search." You must enumerate possibilities, not optimise one number — and you build a candidate, recurse, then undo.
static List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> out = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), out);
return out;
}
static void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> out) {
out.add(new ArrayList<>(path)); // every node is a valid subset
for (int i = start; i < nums.length; i++) {
path.add(nums[i]); // choose
backtrack(nums, i + 1, path, out); // explore
path.remove(path.size() - 1); // un-choose (the whole trick)
}
}The rule: choose, recurse, un-choose — and the moment a partial candidate can’t possibly succeed, return early to prune that branch. That one memorised skeleton, with the loop and the base case swapped, is every "generate all" question there is.
- Cracks: subsets, permutations, combination sum, generate parentheses, N-queens, word search, palindrome partitioning.
- Deep dive: recursion and backtracking.
Graphs: BFS, DFS, topological sort, union-find
The tell. "Grid," "islands," "connected," "shortest path in unweighted steps," "course schedule," "can these merge." A graph question is usually one of four moves.
Flood a region (DFS) — count islands, fill enclosed areas:
static int numIslands(char[][] grid) {
int count = 0;
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
if (grid[r][c] == '1') { count++; sink(grid, r, c); }
}
}
return count;
}
static void sink(char[][] grid, int r, int c) {
if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] != '1') return;
grid[r][c] = '0'; // mark visited by sinking it
sink(grid, r + 1, c); sink(grid, r - 1, c);
sink(grid, r, c + 1); sink(grid, r, c - 1);
}Order a dependency graph (topological sort, Kahn’s way) — course schedule, build order:
static int[] topoSort(int n, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
int[] indeg = new int[n];
for (int[] e : edges) { adj.get(e[0]).add(e[1]); indeg[e[1]]++; }
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i); // no prerequisites
int[] order = new int[n];
int idx = 0;
while (!q.isEmpty()) {
int u = q.poll();
order[idx++] = u;
for (int v : adj.get(u)) if (--indeg[v] == 0) q.offer(v);
}
return order; // idx < n at the end would mean a cycle
}The fourth move is union-find for "are these two connected / how many groups," whose entire heart is a three-line find:
static int find(int[] parent, int x) {
if (parent[x] != x) parent[x] = find(parent, parent[x]); // flatten on the way up
return parent[x];
}The rule: BFS for fewest-steps, DFS for reach-everything, Kahn’s indegree loop for ordering, union-find for merging groups. Name the move and the template is on the page.
- Cracks: number of islands, rotting oranges (multi-source BFS), course schedule I/II, clone graph, number of connected components, redundant connection.
- Deep dives: graphs, depth-first search, topological sort, union-find.
Dynamic programming (1-D and the knapsack shape)
The tell. "Count the ways," "minimum/maximum cost to," "can you reach," "longest/shortest such that" — and the brute force branches into overlapping subproblems. Define a table, fill it in dependency order.
The 1-D shape — one index of state, like coin change:
static int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1); // "infinity"
dp[0] = 0;
for (int a = 1; a <= amount; a++) {
for (int coin : coins) {
if (coin <= a) dp[a] = Math.min(dp[a], dp[a - coin] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}The 2-D / knapsack shape — two axes of state (items × capacity), collapsed to one row and swept high to low so each item is used once:
static int knapsack(int[] weight, int[] value, int capacity) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < weight.length; i++) {
for (int c = capacity; c >= weight[i]; c--) { // high → low = each item once
dp[c] = Math.max(dp[c], value[i] + dp[c - weight[i]]);
}
}
return dp[capacity];
}The rule: name the state, write the transition, seed the base case, fill in order. Once you can classify a DP as "1-D like coin change" or "2-D like knapsack," the code is muscle memory.
- Cracks: climbing stairs, coin change, house robber, longest increasing subsequence, 0/1 knapsack, edit distance, unique paths.
- Deep dive: dynamic programming.
Greedy
The tell. "Maximum number of non-overlapping," "minimum to remove," "can you reach the end," "assign / schedule to fit the most." A greedy works when a locally-best choice is provably globally-best — usually after you sort by the right key (finish time, gap, ratio).
static int maxNonOverlapping(int[][] intervals) {
Arrays.sort(intervals, (x, y) -> Integer.compare(x[1], y[1])); // by finish time
int count = 0, end = Integer.MIN_VALUE;
for (int[] iv : intervals) {
if (iv[0] >= end) { count++; end = iv[1]; } // fits → take it, never reconsider
}
return count;
}The rule: sort, then take the choice that keeps the most room, and never look back. If you can’t prove the local choice is safe, it’s a dynamic-programming problem in disguise, not a greedy one.
- Cracks: activity selection, jump game I/II, gas station, task scheduler, partition labels, assign cookies.
- Deep dive: greedy algorithms.
A few bit tricks
The tell. "Without extra space," "appears once/twice," "count set bits," "power of two," or a constraint whispering that the state is a small set you can pack into an int.
static int singleNumber(int[] nums) { // every value twice except one
int x = 0;
for (int n : nums) x ^= n; // pairs cancel; the loner survives
return x;
}
// Handy one-liners to keep in the fingers:
// x & (x - 1) clears the lowest set bit (loop it to count bits)
// x & -x isolates the lowest set bit
// x > 0 && (x & (x - 1)) == 0 → x is a power of twoThe rule: XOR cancels pairs, and x & (x - 1) peels one bit at a time — the backbone of "single number," bit counting, and subset enumeration by bitmask.
- Cracks: single number I/II, number of 1 bits, counting bits, power of two, subsets via bitmask, missing number.
The pocket cheat sheet
The whole shelf on one card — the last thing to skim before you walk in:
| Pattern | The tell (spot it by this) | Canonical questions |
|---|---|---|
| Two pointers | sorted array, a pair or both ends | two-sum sorted, palindrome, most water |
| Sliding window | contiguous subarray/substring, "longest/at most K" | longest substring, min window, max sum of K |
| Binary search | sorted, or a monotone yes/no on the answer | rotated search, first/last, Koko / ship in D days |
| Fast/slow pointers | linked list, find a cycle or the middle, O(1) space | cycle II, find duplicate, middle node |
| Prefix sums | repeated range sums, "subarrays summing to K" | subarray sum = K, range sum, product except self |
| Frequency / hashing | anagram, duplicate, "seen before," count of each | group anagrams, two-sum, first unique |
| Monotonic stack | "next greater," nested brackets | daily temperatures, valid parens, largest rectangle |
| Heap / top-K | "K largest/closest/frequent," stream median | kth largest, top-K frequent, merge K lists |
| Interval merge | list of [start, end], "overlap/merge" | merge intervals, meeting rooms, insert interval |
| Tree BFS / DFS | "level order" vs "path/depth"; BST → inorder | level order, validate BST, LCA, kth smallest |
| Backtracking | "all subsets/permutations/combos," "generate every" | subsets, permutations, N-queens, word search |
| Graph BFS/DFS/topo | grid/islands, connected, "course schedule" | number of islands, course schedule, components |
| Dynamic programming | "count ways / min-max cost," overlapping choices | coin change, LIS, knapsack, edit distance |
| Greedy | "max non-overlapping / min to remove," sort-then-take | activity selection, jump game, gas station |
| Bit tricks | "once/twice," "count bits," pack a small set | single number, counting bits, power of two |
What each template buys you over brute force
Every pattern here is a foundation precisely because it turns an obvious-but-slow approach into a fast one. That’s why it’s worth the memory — and it’s the sentence to say out loud in the room.
| Pattern | The obvious approach & its cost | With the template |
|---|---|---|
| Two pointers | check every pair, O(n²) | one pass, O(n) |
| Sliding window | re-scan every substring, O(n²) | both edges move once, O(n) |
| Binary search | scan the whole range, O(n) | halve each step, O(log n) |
| Prefix sums | re-sum each query, O(n) per query | one lookup, O(1) per query |
| Hashing | nested search for a match, O(n²) | map lookup, O(n) total |
| Monotonic stack | look ahead for each element, O(n²) | each item pushed/popped once, O(n) |
| Heap / top-K | sort everything, O(n log n) | size-K heap, O(n log k) |
| Dynamic programming | recompute overlapping subproblems, O(2ⁿ) | fill each state once, O(states) |
If asymptotic notation feels shaky, the big-O guide is the prerequisite for reading this table — the whole point of a pattern is the column you just jumped to.
The complete implementation
Every template above, assembled into one toolkit class plus a demo whose comments are the exact printed output:
package dev.fiveyear.cheatsheet;
import java.util.*;
public final class Patterns {
private Patterns() {}
// --- two pointers ---
static int[] twoSumSorted(int[] a, int target) {
int l = 0, r = a.length - 1;
while (l < r) {
int sum = a[l] + a[r];
if (sum == target) return new int[] {l, r};
if (sum < target) l++;
else r--;
}
return new int[] {-1, -1};
}
// --- sliding window ---
static int lengthOfLongestSubstring(String s) {
Map<Character, Integer> last = new HashMap<>();
int best = 0, left = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (last.containsKey(c) && last.get(c) >= left) left = last.get(c) + 1;
last.put(c, right);
best = Math.max(best, right - left + 1);
}
return best;
}
// --- binary search ---
static int lowerBound(int[] a, int target) {
int lo = 0, hi = a.length;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
static int shipWithinDays(int[] weights, int days) {
int lo = 0, hi = 0;
for (int w : weights) { lo = Math.max(lo, w); hi += w; }
while (lo < hi) {
int cap = lo + (hi - lo) / 2;
if (feasible(weights, days, cap)) hi = cap;
else lo = cap + 1;
}
return lo;
}
private static boolean feasible(int[] weights, int days, int cap) {
int need = 1, load = 0;
for (int w : weights) {
if (load + w > cap) { need++; load = 0; }
load += w;
}
return need <= days;
}
// --- fast / slow pointers ---
static int findDuplicate(int[] nums) {
int slow = nums[0], fast = nums[0];
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
slow = nums[0];
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
// --- prefix sums ---
static int subarraySum(int[] nums, int k) {
Map<Integer, Integer> seen = new HashMap<>();
seen.put(0, 1);
int sum = 0, count = 0;
for (int n : nums) {
sum += n;
count += seen.getOrDefault(sum - k, 0);
seen.merge(sum, 1, Integer::sum);
}
return count;
}
// --- monotonic stack ---
static int[] nextGreater(int[] a) {
int[] res = new int[a.length];
Arrays.fill(res, -1);
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < a.length; i++) {
while (!stack.isEmpty() && a[stack.peek()] < a[i]) res[stack.pop()] = a[i];
stack.push(i);
}
return res;
}
// --- valid parentheses ---
static boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
Map<Character, Character> match = Map.of(')', '(', ']', '[', '}', '{');
for (char c : s.toCharArray()) {
if (match.containsKey(c)) {
if (stack.isEmpty() || stack.pop() != match.get(c)) return false;
} else {
stack.push(c);
}
}
return stack.isEmpty();
}
// --- heap / top-k ---
static int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int n : nums) freq.merge(n, 1, Integer::sum);
PriorityQueue<Integer> heap = new PriorityQueue<>((x, y) -> freq.get(x) - freq.get(y));
for (int key : freq.keySet()) {
heap.offer(key);
if (heap.size() > k) heap.poll();
}
int[] res = new int[k];
for (int i = 0; i < k; i++) res[i] = heap.poll();
Arrays.sort(res);
return res;
}
// --- interval merge ---
static int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0]));
List<int[]> out = new ArrayList<>();
for (int[] iv : intervals) {
int last = out.size() - 1;
if (out.isEmpty() || out.get(last)[1] < iv[0]) out.add(iv);
else out.get(last)[1] = Math.max(out.get(last)[1], iv[1]);
}
return out.toArray(new int[0][]);
}
// --- trees ---
static final class TreeNode {
int val;
TreeNode left, right;
TreeNode(int v) { val = v; }
}
static TreeNode insert(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
if (val < root.val) root.left = insert(root.left, val);
else root.right = insert(root.right, val);
return root;
}
static void inorder(TreeNode node, List<Integer> out) {
if (node == null) return;
inorder(node.left, out);
out.add(node.val);
inorder(node.right, out);
}
// --- backtracking ---
static List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> out = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), out);
return out;
}
private static void backtrack(int[] nums, int start, List<Integer> path,
List<List<Integer>> out) {
out.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
backtrack(nums, i + 1, path, out);
path.remove(path.size() - 1);
}
}
// --- graph: flood fill ---
static int numIslands(char[][] grid) {
int count = 0;
for (int r = 0; r < grid.length; r++)
for (int c = 0; c < grid[0].length; c++)
if (grid[r][c] == '1') { count++; sink(grid, r, c); }
return count;
}
private static void sink(char[][] grid, int r, int c) {
if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] != '1')
return;
grid[r][c] = '0';
sink(grid, r + 1, c);
sink(grid, r - 1, c);
sink(grid, r, c + 1);
sink(grid, r, c - 1);
}
// --- graph: topological sort ---
static int[] topoSort(int n, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
int[] indeg = new int[n];
for (int[] e : edges) { adj.get(e[0]).add(e[1]); indeg[e[1]]++; }
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i);
int[] order = new int[n];
int idx = 0;
while (!q.isEmpty()) {
int u = q.poll();
order[idx++] = u;
for (int v : adj.get(u)) if (--indeg[v] == 0) q.offer(v);
}
return order;
}
// --- dynamic programming ---
static int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int a = 1; a <= amount; a++)
for (int coin : coins)
if (coin <= a) dp[a] = Math.min(dp[a], dp[a - coin] + 1);
return dp[amount] > amount ? -1 : dp[amount];
}
// --- bit trick ---
static int singleNumber(int[] nums) {
int x = 0;
for (int n : nums) x ^= n;
return x;
}
}And the demo, with every printed line spelled out:
import java.util.*;
import static dev.fiveyear.cheatsheet.Patterns.*;
int[] pair = twoSumSorted(new int[] {2, 4, 6, 8, 11, 15}, 14);
System.out.println(Arrays.toString(pair)); // [2, 3]
System.out.println(lengthOfLongestSubstring("abcabcbb")); // 3
System.out.println(lowerBound(new int[] {1, 3, 5, 7, 9, 11, 13, 15}, 7)); // 3
System.out.println(shipWithinDays(new int[] {1,2,3,4,5,6,7,8,9,10}, 5)); // 15
System.out.println(findDuplicate(new int[] {1, 3, 4, 2, 2})); // 2
System.out.println(subarraySum(new int[] {1, 1, 1}, 2)); // 2
System.out.println(Arrays.toString(nextGreater(new int[] {2, 1, 2, 4, 3}))); // [4, 2, 4, -1, -1]
System.out.println(isValid("()[]{}")); // true
System.out.println(Arrays.toString(topKFrequent(new int[] {1,1,1,2,2,3}, 2))); // [1, 2]
int[][] merged = merge(new int[][] {{1, 3}, {2, 6}, {8, 10}, {15, 18}});
System.out.println(Arrays.deepToString(merged)); // [[1, 6], [8, 10], [15, 18]]
Patterns.TreeNode bst = null;
for (int v : new int[] {5, 3, 7, 2, 4}) bst = insert(bst, v);
List<Integer> in = new ArrayList<>();
inorder(bst, in);
System.out.println(in); // [2, 3, 4, 5, 7]
System.out.println(subsets(new int[] {1, 2, 3}));
// [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
char[][] grid = {
{'1','1','0','0','0'},
{'1','1','0','0','0'},
{'0','0','1','0','0'},
{'0','0','0','1','1'}
};
System.out.println(numIslands(grid)); // 3
System.out.println(coinChange(new int[] {1, 2, 5}, 11)); // 3
System.out.println(Arrays.toString(
topoSort(4, new int[][] {{0, 1}, {0, 2}, {1, 3}, {2, 3}}))); // [0, 1, 2, 3]
System.out.println(singleNumber(new int[] {4, 1, 2, 1, 2})); // 4Sixteen problems, fifteen patterns, one file you could reconstruct from memory tonight. That’s the entire bet of this page: the templates are few and short enough to own, and owning them is what turns a two-hundred-problem spreadsheet into a good night’s sleep.
The interview corner
The patterns get you writing fast — but the round is won in the ninety seconds before you write, when you name the pattern out loud and defend the choice. That narration is what separates "memorised it" from "understands it."
Ask these before you write a line:
- "Is the input sorted, or may I sort it?" Sorting is the key that unlocks two pointers and binary search; it costs
O(n log n)up front but often buys a far cheaper main loop. Knowing whether it’s already sorted decides your whole approach. - "How big do
nand the values get?" The constraints are the hint.n ≤ 20whispers backtracking or bitmask;nup to a million rules outO(n²)and points at a single-pass window or alog nsearch; a huge value range warns you off a table sized by it. - "Do you want the value, the indices, or all the answers?" "The count" vs "one example" vs "every combination" is the difference between a DP, a two-pointer, and a backtracking search — the same-sounding question routes to three different rows.
The follow-up ladder — where a strong candidate keeps climbing:
- "Now do it in one pass / in place." The sign to drop a sort or a second array for a pointer trick — two pointers for dedup, fast/slow for the middle, XOR for the loner. Space is the axis they’re testing now.
- "The input arrives as a stream — you can’t see it all at once." Streaming kills anything needing the whole array. Reach for a size-K heap (running top-K), two heaps (running median), or a rolling window.
- "The obvious pattern is too slow at these constraints." The escalation ladder: nested loop → sort + two pointers → hashing → binary search on the answer → DP. Each rung trades a factor of
nfor alog nor a clever state. - "Combine two patterns." The hard questions stack them: sort then two-pointer (3-sum), binary-search then greedy-check (ship in D days), BFS over a DP state. Recognising the seam between two familiar rows is the senior signal.
- "When does this pattern give the wrong answer?" Greedy that isn’t provably safe, a sliding window when negatives break monotonicity, binary search when the predicate isn’t actually monotone. Knowing a pattern’s failure boundary is what proves you didn’t just memorise it. (The greedy-vs-DP line is drawn in greedy algorithms.)
Three mistakes that fail the round:
- Pattern-matching on the surface, not the structure. "It has a tree, so DFS" — when the real ask was a level-by-level BFS. Read what the question optimises, not just the nouns it mentions.
- Binary-search boundary bugs.
lo + hioverflowing,lo <= hivslo < hi, updatinglo = midinstead ofmid + 1and looping forever. Memorise one correct half-open template and never improvise the boundaries under pressure. - Forgetting to un-choose in backtracking. Skip the
path.remove(...)and every branch pollutes the next; you’ll get duplicated or corrupted results that pass the tiny example and fail the real one. The undo is the algorithm.
Where to go from here
You now own the shelf: a handful of patterns, each a tell plus a template, cover the overwhelming majority of coding rounds — recognise the row, then write the skeleton you drilled. Three ways to make it stick:
- Drill for recognition, not recall. Take twenty random problems and only name the pattern for each — don’t solve them. Speed at routing is worth more than any single solution, because routing is the part the clock punishes.
- Go one level deeper on the two that carry the most weight. The sliding window and dynamic programming show up more than anything else and have the most variations; the returns on mastering them are outsized.
- Learn each pattern’s failure boundary. The deep-dive articles linked from every family above don’t just show the template — they show where it breaks and what you graduate to next, from two pointers to union-find to topological sort. Knowing the edge of a tool is what lets you pick it with confidence.
Next time that spreadsheet of two hundred problems glares at you the night before, you’ll see it for what it is — fifteen mother sauces and a lot of plating — and you’ll close the laptop and get some sleep.