--- title: DSA Patterns description: Work out which pattern a problem wants from its constraints, input shape, output shape and wording, then write it from a Java template short enough to memorise. tags: [dsa, patterns, algorithms, java, interview] --- 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](https://brain.narayann.dev/notes/engineering/java/collections). For the wider checklist of what to learn, and which named patterns map to which section here, see [topics](https://brain.narayann.dev/notes/engineering/problem-solving/topics). ## Read the signal | The problem says | Reach for | Cost | | ----------------------------------------------------------------------------- | -------------------------------------------------------------------------------------------- | --------------------------------------- | | Contiguous subarray or substring, longest or shortest, at most k of something | [Sliding window](/notes/engineering/problem-solving/patterns#sliding-window) | O(n) | | Sorted array, find a pair or triple that hits a target | [Two pointers](/notes/engineering/problem-solving/patterns#two-pointers) | O(n) after sorting | | Detect a cycle, find the middle, no extra space allowed | [Fast and slow pointers](/notes/engineering/problem-solving/patterns#fast-and-slow-pointers) | O(n) time, O(1) space | | Sorted input, or "smallest value that still works" | [Binary search](/notes/engineering/problem-solving/patterns#binary-search) | O(log n), or O(n log max) on the answer | | Shortest path on an unweighted graph or grid | [BFS](/notes/engineering/problem-solving/patterns#bfs) | O(V + E) | | Reachability, connected components, fill a region | [DFS](/notes/engineering/problem-solving/patterns#dfs) | O(V + E) | | Visit tree nodes in an order, or rebuild a tree from traversals | [Binary tree traversal](/notes/engineering/problem-solving/patterns#binary-tree-traversal) | O(n) | | Reverse, merge, or find a position in a linked list | [Linked list pointers](/notes/engineering/problem-solving/patterns#linked-list-surgery) | O(n) | | Matching brackets, evaluating an expression, undo history | [Stack](/notes/engineering/problem-solving/patterns#stack) | O(n) | | Prerequisites, build order, finish A before B | [Topological sort](/notes/engineering/problem-solving/patterns#topological-sort) | O(V + E) | | Merge groups, ask whether two things are connected | [Union-Find](/notes/engineering/problem-solving/patterns#union-find) | Near O(1) per operation | | Every permutation, combination, subset, or board filling | [Backtracking](/notes/engineering/problem-solving/patterns#backtracking) | Exponential | | Count the ways, or best over a sequence of choices, with repeated subproblems | [Dynamic programming](/notes/engineering/problem-solving/patterns#dynamic-programming) | O(states x transitions) | | Take the locally best option and never look back | [Greedy](/notes/engineering/problem-solving/patterns#greedy) | O(n log n) with a sort | | Many range sum queries, array never changes | [Prefix sum](/notes/engineering/problem-solving/patterns#prefix-sum) | O(n) build, O(1) query | | Many range updates, read the array once at the end | [Difference array](/notes/engineering/problem-solving/patterns#difference-array) | O(1) per update | | Range queries mixed with updates | [Fenwick or segment tree](/notes/engineering/problem-solving/patterns#fenwick-tree) | O(log n) per operation | | Next greater or smaller element, spans, histogram bars | [Monotonic stack](/notes/engineering/problem-solving/patterns#monotonic-stack) | O(n) | | Maximum or minimum of every window | [Monotonic deque](/notes/engineering/problem-solving/patterns#monotonic-deque) | O(n) | | Top k, kth largest, merge k sorted lists | [Heap](/notes/engineering/problem-solving/patterns#heap) | O(n log k) | | Prefix lookups, autocomplete, word search on a board | [Trie](/notes/engineering/problem-solving/patterns#trie) | O(length) per word | | Seen before, frequency, grouping by a key | [HashMap or HashSet](/notes/engineering/problem-solving/patterns#hashing) | O(1) average | | Pairs that cancel, subsets as masks, counting set bits | [Bit manipulation](/notes/engineering/problem-solving/patterns#bit-manipulation) | O(n) or O(2^n) | | Islands, spiral order, walking a grid | [Matrix traversal](/notes/engineering/problem-solving/patterns#matrix-traversal) | O(rows x cols) | | Divisors, primes, powers of two | [Math](/notes/engineering/problem-solving/patterns#math-and-geometry) | Varies | | Points, angles, distances on a plane | [Geometry](/notes/engineering/problem-solving/patterns#math-and-geometry) | O(n) or O(n log n) | | Two players alternating, both playing perfectly | [Game theory](/notes/engineering/problem-solving/patterns#game-theory) | O(states) | | Overlapping ranges, meeting rooms, calendars | [Merge intervals](/notes/engineering/problem-solving/patterns#merge-intervals) | O(n log n) | | Array holds 1 to n, one value missing or repeated | [Cyclic sort](/notes/engineering/problem-solving/patterns#cyclic-sort) | O(n), O(1) space | | Running median, or keeping two halves balanced | [Two heaps](/notes/engineering/problem-solving/patterns#two-heaps) | O(log n) per add | | Merge k sorted lists or arrays | [K-way merge](/notes/engineering/problem-solving/patterns#k-way-merge) | O(n log k) | | Build a cache, a stack with extras, a flattening iterator | [Design](/notes/engineering/problem-solving/patterns#design) | Varies | | Threads sharing a buffer, producer and consumer | [Concurrency](/notes/engineering/problem-solving/patterns#concurrency) | n/a | ## 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. | The problem says | Reach for | | ----------------------------------------------- | -------------------------------------------------------------------------------------------------------- | | "number of ways", "count the ways" | [Dynamic programming](/notes/engineering/problem-solving/patterns#dynamic-programming) | | "maximum" or "minimum" of a sum, profit or cost | [Dynamic programming](/notes/engineering/problem-solving/patterns#dynamic-programming), sometimes greedy | | "can you reach" | [Dynamic programming](/notes/engineering/problem-solving/patterns#dynamic-programming) | | "longest" or "shortest subsequence" | [Dynamic programming](/notes/engineering/problem-solving/patterns#dynamic-programming) | | "optimal" or "best" | [Dynamic programming](/notes/engineering/problem-solving/patterns#dynamic-programming) | | "palindrome" | [Two pointers](/notes/engineering/problem-solving/patterns#two-pointers) | | "sorted array" | [Two pointers](/notes/engineering/problem-solving/patterns#two-pointers) or binary search | | "target sum" | [Two pointers](/notes/engineering/problem-solving/patterns#two-pointers) if sorted, a hash map if not | | "remove duplicates" in place | [Two pointers](/notes/engineering/problem-solving/patterns#two-pointers) | | "k largest", "k smallest", "top k" | [Heap](/notes/engineering/problem-solving/patterns#heap) | | "median", especially from a stream | [Two heaps](/notes/engineering/problem-solving/patterns#two-heaps) | | "priority" | [Heap](/notes/engineering/problem-solving/patterns#heap) | | "parentheses" or "brackets" | [Stack](/notes/engineering/problem-solving/patterns#stack) | | "valid expression" | [Stack](/notes/engineering/problem-solving/patterns#stack) | | "nested structure" | [Stack](/notes/engineering/problem-solving/patterns#stack) | | "undo operations" | [Stack](/notes/engineering/problem-solving/patterns#stack) | | "next greater element", "next smaller element" | [Monotonic stack](/notes/engineering/problem-solving/patterns#monotonic-stack) | | "count frequency" | [HashMap](/notes/engineering/problem-solving/patterns#hashing) | | "find duplicates" | [HashMap or HashSet](/notes/engineering/problem-solving/patterns#hashing) | | "anagram" | [HashMap](/notes/engineering/problem-solving/patterns#hashing), or a sorted string as the key | | "word search", "word prefixes" | [Trie](/notes/engineering/problem-solving/patterns#trie) | | "minimum operations" | [Greedy](/notes/engineering/problem-solving/patterns#greedy) | | "connected components", "number of groups" | [Union-Find](/notes/engineering/problem-solving/patterns#union-find) | | "kth element" | [Binary search](/notes/engineering/problem-solving/patterns#binary-search) or a heap | | "search in sorted" | [Binary search](/notes/engineering/problem-solving/patterns#binary-search) | | "minimize the maximum", "maximize the minimum" | [Binary search](/notes/engineering/problem-solving/patterns#binary-search) on the answer | | "first or last occurrence" | [Binary search](/notes/engineering/problem-solving/patterns#binary-search) | | "XOR" | [Bit manipulation](/notes/engineering/problem-solving/patterns#bit-manipulation) | | "single number" | [Bit manipulation](/notes/engineering/problem-solving/patterns#bit-manipulation) | | "power of two" | [Bit manipulation](/notes/engineering/problem-solving/patterns#bit-manipulation) | | "greatest common divisor", "prime numbers" | [Math](/notes/engineering/problem-solving/patterns#math-and-geometry) | | "angle", "coordinate" | [Geometry](/notes/engineering/problem-solving/patterns#math-and-geometry) | | "optimal strategy", "win or lose", "minimax" | [Game theory](/notes/engineering/problem-solving/patterns#game-theory) | | "substring" with a condition attached | [Sliding window](/notes/engineering/problem-solving/patterns#sliding-window) | | "subarray" of fixed or variable size | [Sliding window](/notes/engineering/problem-solving/patterns#sliding-window) | | "maximum window" or "minimum window" | [Sliding window](/notes/engineering/problem-solving/patterns#sliding-window) | | "contains all" of something | [Sliding window](/notes/engineering/problem-solving/patterns#sliding-window) | ## Input shape The type of the input narrows the field before you have read the question properly. | Input | Try | | ------------------------ | ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | Binary tree or BST | DFS for all paths and any recursive walk, in preorder, inorder or postorder. BFS when the question is level by level or asks for the shallowest depth. On a BST, inorder comes out sorted, and the ordering property often removes a whole branch of the search. | | Graph as nodes and edges | BFS for the shortest path, DFS for reachability and connected components, Union-Find when the wording is connected components or number of groups, topological sort when there are dependencies. | | 2D grid or matrix | DFS or BFS for islands and regions, Union-Find for connected regions, dynamic programming for path counting and path cost. Check whether movement is 4 directional or 8 directional before you write the direction array. | | Sorted array | Two pointers, binary search, sometimes greedy. Sortedness is given for a reason. | | String | Two pointers for palindromes, sliding window for substrings, a trie for prefix and dictionary work, a stack for brackets. | | Linked list | Fast and slow pointers, a dummy head node to kill the empty and first node cases, cycle detection. | ## Output shape What the answer looks like is as strong a hint as the input. | The answer is | Try | | ---------------------------------------------------------------------- | -------------------------------------------------------------------------------------------------------------------------- | | A list of lists: subsets, combinations, permutations, all paths | Backtracking, almost always. Recurse with a take branch and a skip branch. | | A single number: max or min profit, cost, number of ways, fewest jumps | Dynamic programming for optimisation, greedy when a local choice is provably safe, a closed form when it is pure counting. | | The input modified in place | Two pointers, one reading ahead and one writing behind. | | An ordered list: a sorted sequence, a valid task order | Sort with a custom comparator, topological sort for dependencies, a heap when the order has to hold as items arrive. | ## 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. | n up to | You can afford | What that looks like | | ---------- | ---------------- | --------------------------------------------------------------------- | | 12 | O(n!) | Try every permutation | | 20 | O(2^n) | Brute force, backtracking, subset masks. Exponential is expected here | | 500 | O(n^3) | Triple nested loop, interval DP | | 5,000 | O(n^2) | Nested loop, 2D DP | | 1,000,000 | O(n log n) | Sorting, heap, binary search, two pointers, greedy, most DP | | 10,000,000 | O(n) | One pass, hash map, prefix sum | | Above that | O(log n) or O(1) | Binary search, or a closed form formula | ## 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. | Group | What it teaches | Weight | | -------------------------------------------------------------------------------------- | ------------------------------------------------------------------------ | -------------- | | [Arrays and hashing](/notes/engineering/problem-solving/patterns#hashing) | Frequency counting, hash maps and sets, prefix sum, basic sliding window | Very high | | [Two pointers](/notes/engineering/problem-solving/patterns#two-pointers) | Opposite direction, same direction, fast and slow | Very high | | [Sliding window](/notes/engineering/problem-solving/patterns#sliding-window) | Fixed size, variable size, window plus a hash map | Very high | | [Binary trees](/notes/engineering/problem-solving/patterns#binary-tree-traversal) | DFS in preorder, inorder and postorder, BFS by level, tree construction | Very high | | [Linked list](/notes/engineering/problem-solving/patterns#linked-list-surgery) | Fast and slow pointers, reversal, merging | High | | [Stack](/notes/engineering/problem-solving/patterns#stack) | Monotonic stack, bracket matching, infix to postfix | High | | [Graphs](/notes/engineering/problem-solving/patterns#dfs) | BFS and DFS, topological sort, union find | High | | [Dynamic programming](/notes/engineering/problem-solving/patterns#dynamic-programming) | 1D, 2D, and DP over subsequences | Medium to high | | Advanced | Backtracking, binary search, greedy, tries | Medium | ## 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. Fixed size: ```java int sum = 0, best = Integer.MIN_VALUE; for (int i = 0; i < nums.length; i++) { sum += nums[i]; if (i >= k) sum -= nums[i - k]; // drop what fell out if (i >= k - 1) best = Math.max(best, sum); } ``` Variable size, shrink until valid again: ```java Map window = new HashMap<>(); int left = 0, best = 0; for (int right = 0; right < s.length(); right++) { window.merge(s.charAt(right), 1, Integer::sum); while (window.size() > k) { // whatever "invalid" means here char c = s.charAt(left++); if (window.merge(c, -1, Integer::sum) == 0) window.remove(c); } best = Math.max(best, right - left + 1); } ``` 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. ```java int lo = 0, hi = nums.length - 1; while (lo < hi) { int sum = nums[lo] + nums[hi]; if (sum == target) return new int[]{lo, hi}; if (sum < target) lo++; // need bigger else hi--; // need smaller } ``` For 3Sum, sort first, fix one index, then run the two pointer scan on the rest and skip duplicates. The other shape is same direction rather than opposite: a read pointer scanning ahead and a write pointer trailing behind, which edits the array in place with no extra storage. ```java int write = 0; for (int read = 0; read < nums.length; read++) { if (read == 0 || nums[read] != nums[read - 1]) { nums[write++] = nums[read]; // keep it } } return write; // new length ``` When the two pointers walk two different arrays instead of one, the main loop stops as soon as either side runs out. Whatever is left in the other array still has to be drained, so follow the loop with the two catch-up loops. Forgetting them silently drops the tail. ```java while (i < l1 && j < l2) { if (nums1[i] <= nums2[j]) list.add(nums1[i++]); else list.add(nums2[j++]); } while (i < l1) { // rest of the first array list.add(nums1[i]); i++; } while (j < l2) { // rest of the second list.add(nums2[j]); j++; } ``` Whether the pointers are indices or values matters more than it looks. A problem asking for positions wants the index, and returning the value there is a wrong answer that still compiles. Watch the bounds too: `hi` starts at `length - 1`, the opposite ends loop uses `lo < hi` and not `lo <= hi`, and any `read - 1` or `hi + 1` needs a guard at the edges. 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. ```java ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) break; // cycle found } ``` To find where the cycle starts, reset one pointer to the head and advance both one step at a time. They meet at the entry node. When there is no cycle, the loop ends with `slow` sitting on the middle node. 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. ```java int i = 0; while (i < nums.length) { int correct = nums[i] - 1; // where this value belongs if (nums[i] > 0 && nums[i] <= nums.length && nums[i] != nums[correct]) { int tmp = nums[i]; // swap it home, do not advance nums[i] = nums[correct]; nums[correct] = tmp; } else { i++; } } for (int j = 0; j < nums.length; j++) { if (nums[j] != j + 1) return j + 1; // first gap is the missing number } ``` The loop only advances on the `else` branch, because after a swap the freshly arrived value still has to be placed. Comparing `nums[i] != nums[correct]` rather than `i != correct` is what stops duplicates from swapping back and forth forever. 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. Reversal: ```java ListNode prev = null, cur = head; while (cur != null) { ListNode next = cur.next; // save it before you clobber it cur.next = prev; prev = cur; cur = next; } return prev; // prev is the new head ``` Merging two sorted lists: ```java ListNode dummy = new ListNode(0), tail = dummy; while (a != null && b != null) { if (a.val <= b.val) { tail.next = a; a = a.next; } else { tail.next = b; b = b.next; } tail = tail.next; } tail.next = (a != null) ? a : b; // one list still has nodes left return dummy.next; ``` To remove the nth node from the end, advance one pointer n steps first, then move both until the leading one falls off. The trailing pointer is sitting just before the target. 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. On an index: ```java int lo = 0, hi = nums.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; // not (lo + hi) / 2, that overflows if (nums[mid] == target) return mid; if (nums[mid] < target) lo = mid + 1; else hi = mid - 1; } return -1; ``` On the answer, when the question is "what is the smallest value that works": ```java int lo = 1, hi = maxPossible; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (feasible(mid)) hi = mid; // keep mid, it might be the answer else lo = mid + 1; } return lo; ``` The second form never uses `lo <= hi` and never does `hi = mid - 1`. Mixing the two forms is where off by one bugs come from. 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. ```java void dfs(char[][] grid, int r, int c) { if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) return; if (grid[r][c] != '1') return; grid[r][c] = '0'; // mark visited dfs(grid, r + 1, c); dfs(grid, r - 1, c); dfs(grid, r, c + 1); dfs(grid, r, c - 1); } ``` Recursion depth is the grid size in the worst case. On very large inputs, swap to an explicit `ArrayDeque` stack to avoid a stack overflow. DFS is also the tool for enumerating every path rather than the shortest one, since the call stack already holds the path you are on. Add the current node on the way down and remove it on the way back up, the same undo step backtracking uses. 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. ```java int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; Queue q = new ArrayDeque<>(); boolean[][] seen = new boolean[rows][cols]; q.offer(new int[]{0, 0}); seen[0][0] = true; int steps = 0; while (!q.isEmpty()) { for (int i = q.size(); i > 0; i--) { // one whole level per outer pass int[] cur = q.poll(); if (cur[0] == rows - 1 && cur[1] == cols - 1) return steps; for (int[] d : DIRS) { int nr = cur[0] + d[0], nc = cur[1] + d[1]; if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue; if (seen[nr][nc] || grid[nr][nc] == 1) continue; seen[nr][nc] = true; // mark on push, not on pop q.offer(new int[]{nr, nc}); } } steps++; } ``` Marking on pop instead of on push lets the same cell enter the queue many times and turns a linear traversal into a slow one. 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. ```java void traverse(TreeNode node, List out) { if (node == null) return; // out.add(node.val); preorder here traverse(node.left, out); // out.add(node.val); inorder here traverse(node.right, out); // out.add(node.val); postorder here } ``` Iterative inorder, when recursion is off the table: ```java Deque stack = new ArrayDeque<>(); TreeNode cur = root; while (cur != null || !stack.isEmpty()) { while (cur != null) { // run down the left spine stack.push(cur); cur = cur.left; } cur = stack.pop(); out.add(cur.val); cur = cur.right; } ``` Level order is BFS with the level boundary captured by reading the queue size once per round: ```java Queue q = new ArrayDeque<>(); if (root != null) q.offer(root); while (!q.isEmpty()) { List level = new ArrayList<>(); for (int i = q.size(); i > 0; i--) { TreeNode node = q.poll(); level.add(node.val); if (node.left != null) q.offer(node.left); if (node.right != null) q.offer(node.right); } out.add(level); } ``` To rebuild a tree from preorder and inorder, take the root from the front of the preorder list, find it in the inorder list, and everything left of it is the left subtree. Put the inorder values in a `HashMap` first so that lookup is O(1) instead of a scan, which drops the build from O(n^2) to O(n). 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. ```java List> adj = new ArrayList<>(); for (int i = 0; i < n; i++) adj.add(new ArrayList<>()); int[] indegree = new int[n]; for (int[] e : prerequisites) { // e = {course, needs} adj.get(e[1]).add(e[0]); indegree[e[0]]++; } Queue q = new ArrayDeque<>(); for (int i = 0; i < n; i++) if (indegree[i] == 0) q.offer(i); List order = new ArrayList<>(); while (!q.isEmpty()) { int u = q.poll(); order.add(u); for (int v : adj.get(u)) { if (--indegree[v] == 0) q.offer(v); } } // order.size() < n means a cycle exists, so no valid ordering ``` That last line is also how you detect a cycle, which is often the real question. 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. ```java class DSU { private final int[] parent, rank; DSU(int n) { parent = new int[n]; rank = new int[n]; for (int i = 0; i < n; i++) parent[i] = i; } int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); // path compression return parent[x]; } boolean union(int a, int b) { int ra = find(a), rb = find(b); if (ra == rb) return false; // already together if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; } parent[rb] = ra; if (rank[ra] == rank[rb]) rank[ra]++; return true; } } ``` `union` returning false is the cycle detector in an undirected graph. 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. ```java void backtrack(int start, int[] nums, List path, List> out) { out.add(new ArrayList<>(path)); // copy, path keeps mutating for (int i = start; i < nums.length; i++) { if (i > start && nums[i] == nums[i - 1]) continue; // skip duplicates path.add(nums[i]); backtrack(i + 1, nums, path, out); path.remove(path.size() - 1); // undo } } ``` Forgetting the copy on `out.add` is the classic bug: you end up with a list of references to one list that is empty by the end. Pass `i + 1` for combinations where each element is used once, and `i` where elements can repeat. 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. Top down is closer to how you thought about it: ```java Integer[] memo = new Integer[n + 1]; int rob(int i, int[] nums) { if (i < 0) return 0; if (memo[i] != null) return memo[i]; return memo[i] = Math.max(rob(i - 1, nums), nums[i] + rob(i - 2, nums)); } ``` Bottom up avoids recursion depth and is usually faster: ```java int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = nums[0]; for (int i = 2; i <= n; i++) { dp[i] = Math.max(dp[i - 1], nums[i - 1] + dp[i - 2]); } return dp[n]; ``` When `dp[i]` only reads the last one or two entries, drop the array and keep two variables. That turns O(n) space into O(1) and interviewers usually ask for it. 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. ```java Arrays.sort(intervals, Comparator.comparingInt(a -> a[1])); // earliest end first int count = 0, end = Integer.MIN_VALUE; for (int[] iv : intervals) { if (iv[0] >= end) { count++; end = iv[1]; } } ``` Choosing the sort key is most of the work. Before you commit, argue why a locally best choice cannot block a better global answer. If you cannot, the problem probably needs dynamic programming instead. 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. ```java Arrays.sort(intervals, Comparator.comparingInt(a -> a[0])); // by start List merged = new ArrayList<>(); for (int[] iv : intervals) { int[] last = merged.isEmpty() ? null : merged.get(merged.size() - 1); if (last != null && iv[0] <= last[1]) { last[1] = Math.max(last[1], iv[1]); // overlap, extend in place } else { merged.add(new int[]{iv[0], iv[1]}); // copy, do not alias the input } } return merged.toArray(new int[0][]); ``` Take `Math.max` on the end rather than the incoming end, since one interval can sit entirely inside another. Sorting by end time instead is a different problem: that is the greedy interval scheduling above, where you want the most non overlapping intervals. 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. ```java int[] prefix = new int[n + 1]; for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i]; int rangeSum = prefix[r + 1] - prefix[l]; // inclusive l..r ``` The same idea with a hash map counts subarrays that hit a target sum: ```java Map seen = new HashMap<>(); seen.put(0, 1); // empty prefix int sum = 0, count = 0; for (int x : nums) { sum += x; count += seen.getOrDefault(sum - k, 0); seen.merge(sum, 1, Integer::sum); } ``` 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. ```java int[] diff = new int[n + 1]; // add val across [l, r] diff[l] += val; diff[r + 1] -= val; // rebuild once, after all updates int running = 0; for (int i = 0; i < n; i++) { running += diff[i]; nums[i] = running; } ``` 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. ```java Deque stack = new ArrayDeque<>(); Map pairs = Map.of(')', '(', ']', '[', '}', '{'); for (char c : s.toCharArray()) { if (pairs.containsValue(c)) { stack.push(c); // an opener } else if (pairs.containsKey(c)) { if (stack.isEmpty() || stack.pop() != pairs.get(c)) return false; } } return stack.isEmpty(); // leftovers mean unclosed brackets ``` Evaluating reverse Polish notation is the same shape: push operands, and on an operator pop two, apply, push the result. Watch the order, since the second pop is the left operand, which matters for subtraction and division. For a stack that reports its minimum in O(1), push a pair of the value and the smallest value seen so far, rather than trying to recompute after a pop. Converting infix to postfix uses one stack for operators, popping anything of higher or equal precedence before pushing the current one. 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. ```java int[] nextGreater = new int[n]; Arrays.fill(nextGreater, -1); Deque stack = new ArrayDeque<>(); // indices, values decreasing for (int i = 0; i < n; i++) { while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) { nextGreater[stack.pop()] = nums[i]; } stack.push(i); } ``` Store indices rather than values when the answer needs a distance, such as how many days until a warmer temperature. 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. ```java Deque dq = new ArrayDeque<>(); // indices, values decreasing int[] out = new int[n - k + 1]; for (int i = 0; i < n; i++) { if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst(); // left the window while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast(); dq.offerLast(i); if (i >= k - 1) out[i - k + 1] = nums[dq.peekFirst()]; } ``` 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. ```java PriorityQueue pq = new PriorityQueue<>(); // min heap for (int x : nums) { pq.offer(x); if (pq.size() > k) pq.poll(); // drop the smallest } return pq.peek(); // kth largest ``` O(n log k) instead of O(n log n) for a full sort. Comparator forms are in [collections](https://brain.narayann.dev/notes/engineering/java/collections). 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. ```java PriorityQueue lower = new PriorityQueue<>(Collections.reverseOrder()); // max PriorityQueue upper = new PriorityQueue<>(); // min void add(int num) { lower.offer(num); // always enter through the low side upper.offer(lower.poll()); // pass the largest of them up if (upper.size() > lower.size()) { lower.offer(upper.poll()); // lower keeps the extra when odd } } double median() { return lower.size() > upper.size() ? lower.peek() : (lower.peek() + upper.peek()) / 2.0; } ``` Pushing into `lower` and immediately funnelling the top into `upper` is what keeps every value in `lower` below every value in `upper` without comparing against both heaps by hand. Add is O(log n), reading the median is O(1). 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). ```java PriorityQueue pq = new PriorityQueue<>((a, b) -> a.val - b.val); for (ListNode head : lists) { if (head != null) pq.offer(head); // one seed per list } ListNode dummy = new ListNode(0), tail = dummy; while (!pq.isEmpty()) { ListNode node = pq.poll(); tail.next = node; tail = node; if (node.next != null) pq.offer(node.next); // refill from the same list } return dummy.next; ``` The heap never holds more than k nodes, one per list, so the space is O(k) regardless of how long the lists are. For arrays rather than linked lists, push `{value, listIndex, elementIndex}` triples instead of nodes. 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. ```java class TrieNode { TrieNode[] next = new TrieNode[26]; boolean isWord; } void insert(TrieNode root, String word) { TrieNode cur = root; for (char c : word.toCharArray()) { int i = c - 'a'; if (cur.next[i] == null) cur.next[i] = new TrieNode(); cur = cur.next[i]; } cur.isWord = true; } ``` On a board search, walking the trie alongside the DFS prunes whole branches the moment the prefix stops existing. 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. ```java int[] bit = new int[n + 1]; // 1-based void update(int i, int delta) { for (; i <= n; i += i & -i) bit[i] += delta; } int query(int i) { // sum of 1..i int sum = 0; for (; i > 0; i -= i & -i) sum += bit[i]; return sum; } ``` `i & -i` isolates the lowest set bit, which is how the tree jumps between ranges. Use a segment tree instead when the operation is min, max, or anything that is not subtractable. 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. ```java n & 1 // lowest bit, so n & 1 == 0 means even n >> 1 // halve n & (n - 1) // clear the lowest set bit n & -n // isolate the lowest set bit 1 << i // mask for bit i mask | (1 << i) // set bit i mask & ~(1 << i) // clear bit i (mask >> i) & 1 // read bit i Integer.bitCount(n) // popcount // every subset of n items for (int mask = 0; mask < (1 << n); mask++) { for (int i = 0; i < n; i++) { if ((mask & (1 << i)) != 0) { /* item i is in this subset */ } } } ``` XOR cancels equal values, so xoring a whole array leaves the element that appears an odd number of times. Repeatedly clearing the lowest set bit counts set bits in as many steps as there are ones. 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. ```java int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; for (int[] d : DIRS) { int nr = r + d[0], nc = c + d[1]; if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue; // visit } ``` Read the question for whether movement is 4 directional or 8 directional before writing the array. For 8 directional, add the four diagonal offsets. For spiral order, hold four boundaries and shrink one after each pass. For rotation in place, transpose the matrix and then reverse each row. Grid path counting and minimum path cost are dynamic programming rather than traversal. Union-Find is the better fit when regions merge as you go instead of being explored one at a time. 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. ```java int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } int lcm(int a, int b) { return a / gcd(a, b) * b; // divide first, or it overflows } ``` Primes up to n with a sieve, which is O(n log log n) and far better than testing each number on its own: ```java boolean[] composite = new boolean[n + 1]; for (int i = 2; (long) i * i <= n; i++) { if (!composite[i]) { for (int j = i * i; j <= n; j += i) composite[j] = true; } } ``` Start the inner loop at `i * i` because every smaller multiple already got crossed off by a smaller prime. A number is a power of two when it has exactly one set bit, so `n > 0 && (n & (n - 1)) == 0`. For coordinates, compare squared distances instead of calling `Math.sqrt`, which keeps the arithmetic in integers and avoids floating point error. The sign of the cross product `(b - a) x (c - a)` tells you whether three points turn left, turn right, or lie on one line. 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. ```java boolean canWin(int state, Map memo) { if (memo.containsKey(state)) return memo.get(state); for (int move : movesFrom(state)) { if (!canWin(next(state, move), memo)) { // opponent is stuck memo.put(state, true); return true; } } memo.put(state, false); // every move hands them a win return false; } ``` When the answer is a score rather than a winner, it becomes minimax: you maximise on your turn, your opponent minimises on theirs, and the same memo keyed by state keeps it from re-exploring. This is dynamic programming with the state including whose turn it is. 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. ```java Map> groups = new HashMap<>(); for (String s : words) { char[] c = s.toCharArray(); Arrays.sort(c); groups.computeIfAbsent(new String(c), k -> new ArrayList<>()).add(s); } ``` Full API in [collections](https://brain.narayann.dev/notes/engineering/java/collections). 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. An LRU cache, using the fact that `LinkedHashMap` can order by access rather than insertion: ```java class LRUCache { private final int capacity; private final LinkedHashMap map; LRUCache(int capacity) { this.capacity = capacity; this.map = new LinkedHashMap<>(16, 0.75f, true) { // true = access order @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > LRUCache.this.capacity; } }; } int get(int key) { return map.getOrDefault(key, -1); } void put(int key, int value) { map.put(key, value); } } ``` Interviewers usually want the version built by hand: a `HashMap` from key to node, plus a doubly linked list with sentinel head and tail nodes. On `get`, unlink the node and move it to the front. On `put` past capacity, drop the node before the tail sentinel. A stack that reports its minimum in O(1), by storing the running minimum alongside each value instead of recomputing after a pop: ```java Deque stack = new ArrayDeque<>(); // {value, min at or below this point} void push(int x) { int min = stack.isEmpty() ? x : Math.min(x, stack.peek()[1]); stack.push(new int[]{x, min}); } void pop() { stack.pop(); } int top() { return stack.peek()[0]; } int getMin() { return stack.peek()[1]; } ``` Flattening iterators follow the same idea: hold a stack of iterators, and in `hasNext` keep unwrapping the top one until you find a real element or run out. 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. The library already solves it. `BlockingQueue` parks the caller for you: ```java BlockingQueue queue = new ArrayBlockingQueue<>(10); queue.put(item); // blocks while the buffer is full int item = queue.take(); // blocks while the buffer is empty ``` By hand, with a monitor: ```java synchronized (lock) { while (!ready) { // while, never if lock.wait(); // releases the lock while parked } // do the work ready = false; lock.notifyAll(); } ``` The `while` matters. A thread can return from `wait` without anyone having signalled it, so the condition has to be rechecked rather than assumed. `notifyAll` over `notify` for the same reason: `notify` wakes one arbitrary thread, which may not be one that can actually make progress. Problems: print in order, print FooBar alternately, building H2O, the dining philosophers, bounded blocking queue.