The base template. Divide array in half, recursively sort, merge two sorted halves. Get the merge() helper muscle-memory clean — it's reused in every other pattern.

During the merge step, whenever a right-half element is placed before a left-half element, it contributes (mid - left_ptr + 1) inversions. Classic divide-and-conquer counting trick.

Generalise 2-way merge to K sorted lists/arrays. Use a min-heap of size K — always extract the global minimum. O(N log K) total. This pattern recurs constantly in stream and external-sort problems.

Split the problem at mid, solve left and right independently, combine results. Maximum subarray is the canonical example — the cross-mid case is a merge-like combination step.

Conceptual pattern tested in system design + coding hybrids. Chunk → sort chunks → k-way merge. Understand why merge sort is cache-friendly and used in databases.

Advanced: build a segment tree where each node holds a sorted array (merge sort tree). Enables O(log² n) range frequency / order-statistic queries. Comes up in competitive programming and senior-level interviews.

The entry point. dp[i] represents the answer for the first i elements. Transition looks back a fixed number of steps. Covers climbing stairs, house robber, and their variants. Nail the recurrence + base case ritual here — it's the same skeleton for everything that follows.

dp[i] = max subarray ending exactly at i. Classic Kadane is O(n). Variants extend to products, circular arrays, and k-partitions. Every variant tweaks what "ending at i" tracks.

dp[i] = length of LIS ending at index i. O(n²) DP is the interview bar; O(n log n) patience sorting is the follow-up flex. Subsequence ≠ subarray — elements don't need to be contiguous.

dp[i][j] is defined on prefixes of two strings. Transition considers match (diagonal) vs mismatch (up/left). LCS, Edit Distance, and Shortest Common Supersequence all live here. Draw the 2D table for every new problem until the transitions feel automatic.

dp[r][c] = answer for reaching cell (r,c). Moves are typically right/down. Variants add obstacles, variable costs, or multiple trips. Space can be reduced to O(n) with rolling array.

Each item can be taken at most once. dp[i][w] = best value using first i items with capacity w. Subset sum, partition equal subset, and target sum are all disguised 0/1 knapsacks. Key optimization: 1D dp array iterated in reverse.

Items can be reused unlimited times. dp iterated forward (unlike 0/1). Coin change is the canonical example. Rod cutting and integer break are structural twins.

dp[i][j] = answer for the subarray/substring from i to j. Fill by increasing length. A pivot k splits [i,j] into [i,k] and [k+1,j]. Classic for matrix chain multiplication, burst balloons, and stone merge. O(n³) typical — flag for interviewers upfront.

Expand-around-center for detection; interval DP for counting/partitioning. LPS (Longest Palindromic Subsequence) = LCS(s, reverse(s)). Palindrome partitioning combines interval DP with linear DP.

dp defined on subtrees; computed via post-order DFS. Each node aggregates answers from children. House Robber III is the entry point. Diameter and max-path-sum require tracking two return values per node.

State includes a bitmask representing which elements have been used. dp[mask] or dp[mask][i]. Fits when n ≤ 20. TSP and assignment problems are canonical. Enumerate submasks in O(3ⁿ) when needed.

Model the problem as transitions between explicit states (e.g., holding/not holding stock, cooldown, at most k transactions). Each dp state is (day, machine_state). Stock problems are the canonical interview set — know all 6 variants cold.

Pick 2 random DP problems per pattern from above. No notes. Within 2 min of reading, name the pattern and write the state definition. That's the interview reflex you're building.

The base template for both. BFS uses a queue and gives shortest path in unweighted graphs. DFS uses a stack (or recursion) and is simpler for reachability. Build both from scratch until they're automatic — every other pattern is a modification of one of these two.

Kahn's BFS-based approach: track in-degrees, repeatedly remove nodes with in-degree 0. DFS-based: post-order traversal, push to stack on exit. If you can't process all nodes → cycle exists. Course Schedule is the canonical interview problem for this.

Directed: DFS with 3-color marking (white/grey/black) or Kahn's leftover nodes. Undirected: DFS with parent tracking, or DSU. These are different problems with different approaches — know both.

Two operations: find(x) with path compression, union(x,y) by rank. Near O(1) amortized per operation. Solves connected components, cycle detection in undirected graphs, and dynamic connectivity. Build the template once — it's copy-paste for every problem in this pattern.

Sort edges by weight, greedily add edge if it doesn't form a cycle (DSU check). Kruskal's is just DSU + sorting — you get it nearly free. Prim's is the BFS/heap alternative; good to know but Kruskal's is cleaner to code under pressure.

Min-heap + greedy relaxation. O((V+E) log V). Only works with non-negative weights. The heap stores (cost, node) — always process the minimum cost node next. Network Delay Time is the purest Dijkstra problem on LeetCode.

Bellman-Ford: relax all edges V-1 times. O(VE). Handles negative weights; detects negative cycles. For unweighted graphs, plain BFS gives shortest path in O(V+E) — don't reach for Dijkstra when edges are unweighted. Know when each applies.

BFS or DFS — assign alternating colors to nodes. If a neighbor has the same color as the current node, not bipartite. Equivalent to: does an odd-length cycle exist? Comes up more than you'd expect in disguised forms (e.g. "can we divide into two groups with no internal conflict").

BFS/DFS where the state is more than just the node — e.g. (node, steps_remaining), (node, keys_collected), (node, visited_bitmask). These are the hardest interview graph problems and require combining two patterns cleanly.

Tarjan's: single DFS pass, tracks discovery time and low-link values, uses a stack. Kosaraju's: two DFS passes — one on original graph, one on reversed. Both O(V+E). SCCs collapse a directed graph into a DAG — useful for condensation problems.

For each problem below, before reading any solution: name the pattern, state whether BFS or DFS, and write the key data structure. This is the graph equivalent of the DP identification drill.

The classic greedy template: sort intervals by end time, greedily pick the earliest-ending non-overlapping interval. Maximises the number of intervals selected. Variations sort by start time or require tracking overlap count — Meeting Rooms II needs a min-heap, not just sorting.

The greedy choice is made by sorting with a non-obvious comparator. Largest Number sorts by string concatenation order. Task scheduler sorts by frequency. The hard part is proving your sort order is globally optimal — be ready to justify in interviews.

Track the maximum reachable index as you scan left to right. At each position, update the furthest you can reach. If current index exceeds max reach, you're stuck. Jump Game II extends this to counting minimum jumps by tracking the current "frontier".

Make one greedy pass left-to-right, then another right-to-left, combining both results. Candy is the textbook example. Trapping Rain Water also fits this shape. The insight: one pass can only satisfy one direction of constraint.

Use a max or min heap to always greedily pick the current best option. IPO, Find Median from Data Stream, and meeting room variants all use heaps to maintain the greedy choice efficiently as the input evolves.

Build or reduce a string by making locally optimal character choices. Remove K Digits uses a monotonic stack to greedily maintain the smallest result. Greedy string problems often combine with stacks or two-pointer scanning.

Some problems look greedy but require DP (coin change with arbitrary denominations, 0/1 knapsack). The test: does a greedy choice ever need to be reconsidered? If yes → DP. If a locally optimal choice is always globally safe → greedy. Train this instinct by solving the same problem both ways where possible.

1. Can I sort the input to make the greedy choice obvious? 2. Is there a "always take the current best" argument? 3. Can I prove by exchange argument that my choice never loses? 4. If not — switch to DP. If yes to all three — code the greedy.

Left pointer at start, right pointer at end. Move them inward based on a condition. Works on sorted arrays for pair/triplet sum problems. Two Sum II is the purest form. 3Sum adds a sort + outer loop wrapper around the same idea.

One pointer moves 1 step, another moves 2 steps. Detects cycles, finds midpoints, and finds the k-th node from end. The slow pointer is always at the midpoint when fast reaches the end on a linear list.

Window size k is given. Slide right by adding nums[r] and removing nums[r-k]. Max sum subarray of size k is the simplest form. Extend to averages, max, character frequency tracking.

Expand right pointer freely, shrink left pointer when a constraint is violated. Template: while(invalid) { remove left; left++ }. Longest substring without repeating characters is the canonical form. The constraint can be character count, sum, distinct elements — same template.

Both pointers move left to right, at different speeds or conditions. Used for in-place removal, deduplication, and Dutch National Flag (3-way partition). Remove Duplicates and Move Zeroes are the entry points.

Exact(K) = AtMost(K) - AtMost(K-1). Converts "exactly K" subarray counting problems into two variable window passes. Subarrays with K Different Integers is the canonical hard problem for this.

Push opening brackets, pop and match on closing. Extended to nested structures, decode strings, and expression evaluation. The stack maintains "pending" state waiting to be resolved.

Maintain a stack that is always increasing or always decreasing. When a new element violates the property, pop and record. Next Greater Element, Daily Temperatures, and Largest Rectangle in Histogram all use this. One of the highest signal patterns for medium/hard interviews.

A deque that maintains the max (or min) of a sliding window in O(1) per step. Add to back (remove smaller elements first), remove from front if outside window. Sliding Window Maximum is the canonical problem.

Implement stack using queues, implement queue using stacks — classic design problems that test understanding of both data structures. Also includes circular queue and task scheduling simulations.

Remove K Digits uses a monotonic stack greedily. Largest Rectangle uses stack + area calculation. Some problems combine stack-maintained state with a DP recurrence. These are the hardest stack problems — if stuck, ask: what invariant does my stack maintain?

At each element, choose to include or exclude. Generates 2ⁿ subsets. Template: for loop starting at `start`, add element, recurse with start+1, remove element. Subsets II adds deduplication by skipping duplicates after sorting.

Unlike subsets, order matters and all elements must be used. Use a visited array or swap-in-place. Permutations II deduplicates by sorting + skipping used duplicates. Time complexity is O(n × n!) — state this upfront.

DFS on a 2D grid with visited marking + undo. Word Search is the canonical example. Mark cell as visited before recursing, unmark after returning. Crucial: the undo step is what makes it backtracking, not just DFS.

Place elements one by one with hard constraints. Prune aggressively — check constraint validity before recursing, not after. N-Queens uses row/column/diagonal sets for O(1) validity checks. Sudoku Solver uses the same principle per box/row/col.

Generate all valid strings or partition a string satisfying some rule. Generate Parentheses tracks open/close counts. Palindrome Partitioning checks each prefix before recursing. Letter Combinations maps digits to characters.

Three recursive orderings and their iterative equivalents with an explicit stack. Inorder of BST gives sorted sequence. Preorder is natural for tree serialization. Postorder is natural for bottom-up aggregation. Know all three iteratively — interviewers ask for it.

Queue-based level-by-level traversal. Use queue size at the start of each iteration to process exactly one level. Right side view, level averages, and zigzag are all level-order BFS with a small twist.

BST property: left subtree < root < right subtree. Inorder gives sorted order. Validate BST by passing min/max bounds down — not just checking immediate children. Delete is the trickiest: handle 0/1/2 children cases.

For BST: navigate left/right based on values. For general binary tree: if both targets are in different subtrees, current node is LCA. Post-order DFS — return non-null from left or right, or current node if both found.

dp defined on subtrees, computed post-order. Each node returns information about its subtree to its parent. House Robber III is the entry point — each node returns (rob_this, skip_this). Diameter and max path sum require returning the best single path upward while tracking a global max.

Encode a tree to a string and reconstruct it. Preorder with null markers is the cleanest approach. Construction from two traversals (pre+in, post+in) uses the root-finding property of each traversal order.

Convert sorted array to balanced BST (mid as root, recurse). AVL/Red-Black internals rarely asked but concepts are fair game. Segment trees for range queries are increasingly asked at Microsoft — build, query, update.

Maintain a min-heap of size K. For each new element, if it's larger than the heap's min, replace it. Result: heap contains the K largest elements. O(n log K) — better than sorting O(n log n) when K << n. Works for frequencies, distances, sums.

Min-heap seeded with the first element from each of K sorted lists. Always extract minimum, push the next element from the same list. O(N log K) total. Covered in merge sort but revisit here with the heap lens — it's a fundamental pattern.

Maintain a max-heap for the lower half and a min-heap for the upper half, kept balanced in size. Median is always the top of one or both heaps. Rebalance after each insert. This pattern is the canonical "hard heap" interview problem.

Use a heap to always process the highest-priority task. IPO: unlock projects greedily by capital, use max-heap for profit. CPU scheduling: use min-heap for deadlines. These combine greedy logic with heap-maintained ordering.

Three pointers: prev, curr, next. Reverse by redirecting curr.next to prev. Iterative is preferred in interviews. Reverse K Group and Reverse Between are extensions — handle the sublist boundaries carefully with dummy nodes.

Cycle detection, midpoint finding, kth from end. Floyd's cycle: if fast meets slow, cycle exists; reset one pointer to head, move both one step at a time to find cycle entry. Removing Nth from end: advance fast by N, then move both until fast reaches end.

Merge two sorted lists iteratively with a dummy head. Compare heads, attach smaller, advance. Merge K lists escalates to a heap or divide-and-conquer approach.

Intersection: two pointers switch lists at the end — they meet at the intersection node after traversing the same total length. Palindrome: find middle, reverse second half, compare. Restore the list after if asked.

LRU: doubly linked list + hashmap. O(1) get and put. The list maintains access order; the map provides O(1) node lookup. LFU adds a frequency layer — map of frequency to doubly linked lists. Classic Microsoft/Google design question.

Each node has children[26] and an isEnd flag. Insert walks characters creating nodes as needed. Search walks and checks isEnd at the last character. StartsWith checks if the path exists regardless of isEnd. Build this from scratch until it's automatic — it's the base for every other trie problem.

Combine trie traversal with DFS on a grid. Word Search II inserts all words into a trie, then DFS on the grid — prune branches when no trie prefix matches. This drops the complexity from O(words × 4^L) to O(4^L) with shared prefix pruning.

Store integers bit by bit from MSB to LSB. To maximize XOR with a query number, greedily take the opposite bit at each level. Maximum XOR of Two Numbers is the canonical problem. Extends to range XOR queries and prefix XOR problems.

a XOR a = 0, a XOR 0 = a. XOR of all elements cancels duplicates — whatever remains is the element that appeared an odd number of times. Single Number and its variants are the canonical problems. Two numbers that differ: n XOR m gives 1-bits where they differ; use lowest set bit to partition into two groups.

n & (n-1) clears the lowest set bit — count set bits by repeatedly applying this until n=0. Counting Bits for all numbers 0..n uses DP: dp[i] = dp[i >> 1] + (i & 1). Know Brian Kernighan's algorithm cold.

Enumerate all 2ⁿ subsets with a bitmask from 0 to (1<<n)-1. Check if bit i is set with (mask >> i) & 1. Enumerate all submasks of a mask with: for(sub=mask; sub>0; sub=(sub-1)&mask). Used in bitmask DP (Day 6 of graphs) and combination problems where n ≤ 20.

Add without +: XOR gives sum bits, AND shifted left gives carry; repeat until no carry. Multiply using shift-and-add. These are more about understanding binary arithmetic than production coding — still asked at Microsoft and Google.