Coding Interview Patterns: Complete Revision Guide

Here is the review of all 32 patterns covered in Grokking the Coding Interview. Use this as your night-before-the-interview revision document. Each pattern follows the same structure so you can scan quickly and find the cue you need.

How to read each pattern card.

• Core idea. What the pattern is in one or two sentences.
• Recognize it when. The trigger words or problem shapes that signal this pattern.
• How it works. The mechanism in plain English.
• Typical complexity. Time and space cost when applied correctly.
• Variations. Common flavors of the same pattern.
• Example problems. Representative problems to anchor the pattern.
• Watch out for. The most common mistakes.

1. Pattern: Two Pointers

Core idea. Use two indices that walk through the same array or string, either toward each other from the ends or together in the same direction. They replace a nested loop with a single pass, dropping the cost from O(n²) to O(n).

Recognize it when. The input is sorted (or can be sorted), and you are looking for a pair, triplet, or subarray that satisfies a condition like a target sum, a comparison, or a duplicate-removal rule. The brute force would be two nested loops.

How it works. Place one pointer at the start and one at the end. Compare the values they point to. If the result is too small, move the left pointer right to increase it. If too large, move the right pointer left to decrease it. Stop when the pointers cross. The sortedness of the array is what makes this directional reasoning correct.

Typical complexity. Time: O(n). Space: O(1).

Variations. Opposite-end pointers for pair-sum problems. Same-direction pointers for remove-duplicates and partition problems. Three pointers for 3Sum where one index is fixed and the other two converge.

Example problems. Pair with Target Sum, Remove Duplicates, Squaring a Sorted Array, 3Sum, Container With Most Water, Trapping Rain Water.

Watch out for. The array must be sorted for opposite-end Two Pointers to work. For unsorted inputs you usually need a hash map instead. In 3Sum, remember to skip over duplicate values explicitly to avoid duplicate triplets in the answer.

2. Pattern: Island (Matrix Traversal)

Core idea. Treat a 2D grid like a graph and use BFS or DFS to find connected groups of cells. Each connected group is an "island."

Recognize it when. The input is a 2D matrix of land and water, 0s and 1s, or any cell type that can be connected to its neighbors. You need to count groups, find the largest group, paint a region, or check if cells are reachable from each other.

How it works. Walk through every cell. When you find an unvisited target cell, launch a DFS or BFS from it that explores all its connected neighbors (usually four directions, sometimes eight). Mark each visited cell so you do not revisit it. When the search finishes, you have processed one full island. Continue scanning for the next unvisited target cell.

Typical complexity. Time: O(rows × cols), since each cell is visited once. Space: O(rows × cols) for the visited set or recursion stack in the worst case.

Variations. Counting islands. Measuring island area. Flood fill (recoloring). Multi-source BFS for problems where multiple starting points spread simultaneously, like rotting oranges.

Example problems. Number of Islands, Max Area of Island, Flood Fill, Surrounded Regions, Rotting Oranges.

Watch out for. Forgetting to mark cells as visited, which causes infinite loops. Mixing up row and column indices. Missing the diagonal neighbors when the problem actually requires eight-directional connectivity.

3. Pattern: Fast and Slow Pointers

Core idea. Two pointers walk the same data structure at different speeds. The faster one outpaces the slower one, and the relationship between their positions reveals structural facts like cycles or midpoints.

Recognize it when. The problem involves a linked list and asks about cycles, the middle node, the kth node from the end, or palindromes. It can also apply to sequences where you need to detect repetition without using extra memory.

How it works. The slow pointer moves one step at a time. The fast pointer moves two steps. If there is no cycle, fast reaches the end first. If there is a cycle, fast eventually laps slow inside the cycle and they meet. To find the cycle's start, reset one pointer to the head and move both at the same speed; they meet at the cycle entry. To find the middle, stop when fast reaches the end and slow is automatically at the middle.

Typical complexity. Time: O(n). Space: O(1).

Variations. Cycle detection (Floyd's algorithm). Finding the cycle start. Finding the middle node. Detecting palindromes by reversing the second half in place.

Example problems. Linked List Cycle, Linked List Cycle II, Middle of the Linked List, Palindrome Linked List, Happy Number.

Watch out for. Off-by-one errors when the list has even length and you need the "first middle" versus the "second middle." Always check whether fast and fast.next are non-null before moving fast two steps to avoid null-pointer errors.

4. Pattern: Sliding Window

Core idea. Maintain a contiguous subarray or substring (the "window") and slide it across the input. As you extend the right edge and shrink the left edge, you keep an aggregate (sum, count, frequency map) updated in O(1) per step.

Recognize it when. The problem asks for a contiguous subarray or substring that meets a condition: maximum sum of size K, longest substring without repeats, smallest window containing all characters of a target, and so on. The brute force is recomputing over every subarray.

How it works. Two indices, left and right, both start at 0. Move right forward to expand the window, updating the running aggregate as each new element enters. When the window violates the condition or reaches a size limit, advance left to shrink it, updating the aggregate as each element leaves. Track the best window seen so far.

Typical complexity. Time: O(n). Space: O(1) or O(k) where k is the size of the character set or distinct values in the window.

Variations. Fixed-size window (size K is given). Dynamic window (size grows and shrinks based on a condition). Window with frequency map for character or element counts. Multi-pointer windows for problems with two coupled conditions.

Example problems. Maximum Sum Subarray of Size K, Smallest Subarray with a Given Sum, Longest Substring with K Distinct Characters, Longest Substring Without Repeating Characters, Permutation in String, Minimum Window Substring.

Watch out for. Forgetting to remove the leaving element from your aggregate when shrinking. Confusing "at most K distinct" with "exactly K distinct" (the second usually equals "at most K" minus "at most K minus 1"). Off-by-one errors in window length.

5. Pattern: Merge Intervals

Core idea. When intervals overlap, you can combine them. Sorting by start time first turns a complicated geometric problem into a simple linear sweep.

Recognize it when. The input is a list of intervals or ranges, and you need to merge overlapping ones, find intersections, insert a new interval, or count conflicts. Calendars, meeting rooms, and time-range problems are all signals.

How it works. Sort intervals by start time. Walk through them in order, maintaining the current merged interval. For each new interval, check whether its start is less than or equal to the current end. If so, extend the current interval's end to the maximum of the two ends. If not, the new interval is disjoint, so push the current one to the result and start a new current interval.

Typical complexity. Time: O(n log n) due to sorting. Space: O(n) for the output, or O(1) if merging in place.

Variations. Merging overlapping intervals. Inserting one new interval into a sorted list. Finding intersections between two interval lists. Counting minimum meeting rooms (often solved with a min-heap of end times).

Example problems. Merge Intervals, Insert Interval, Intervals Intersection, Meeting Rooms II, Employee Free Time, Non-overlapping Intervals.

Watch out for. Edge-touching intervals like [1,3] and [3,5]: decide upfront whether they count as overlapping or disjoint, since the problem statement determines it. Sort by start time, not end time, unless the problem explicitly needs end-time order (like the activity selection greedy).

6. Pattern: Cyclic Sort

Core idea. When an array contains numbers in a known range from 1 to n (or 0 to n minus 1), each number has a "correct" index. Place every number at its correct index in a single pass, and the array sorts itself in O(n).

Recognize it when. The array contains integers in a contiguous range like 1 to n, and the problem asks for a missing number, duplicate number, smallest positive missing, or to sort in O(n) without comparisons.

How it works. Walk through the array. For each index, check whether the value at that index belongs there (value equals index plus 1, in the standard 1-to-n case). If not, swap the value into its correct position. Repeat at the same index until the value is correct or out of range, then move on. After one pass, every misplaced number reveals a missing or duplicate slot.

Typical complexity. Time: O(n) amortized, since each swap places at least one number permanently. Space: O(1).

Variations. Find missing number. Find all missing numbers. Find duplicates. Find smallest missing positive integer. First k missing positives.

Example problems. Cyclic Sort, Find the Missing Number, Find All Duplicates, Find the Corrupt Pair, Find the Smallest Missing Positive Number.

Watch out for. This pattern only works when values are in a known small range. If you have arbitrary integers, use a hash set instead. Also, when swapping, do not advance the index until the current slot is correct, or you will leave misplaced values behind.

7. Pattern: In-place Reversal of a Linked List

Core idea. Reverse a linked list (or a portion of one) by rewiring next-pointers as you walk through it, using only O(1) extra memory.

Recognize it when. The problem mentions reversing a linked list, reversing a sublist between positions, or reversing groups of K nodes. Any time the constraint says "do it in place" or "without extra memory," reversal in place is the move.

How it works. Maintain three pointers: previous, current, and next. At each step, save current.next into next, point current.next to previous, advance previous to current, and advance current to next. When current becomes null, previous is the new head. For sublist reversal, do the same thing between the two boundary nodes, then stitch the reversed portion back into the surrounding list.

Typical complexity. Time: O(n). Space: O(1).

Variations. Full reversal. Reverse a sub-list between two positions. Reverse every K-element sub-list. Reverse alternating K-element sub-lists. Rotate the list by K places.

Example problems. Reverse a Linked List, Reverse a Sub-list, Reverse Every K-element Sub-list, Reverse Alternating K-element Sub-list, Rotate a Linked List.

Watch out for. Losing the next pointer before saving it. Forgetting to set the original head's next to null after reversing (otherwise you create a cycle). For sublist reversals, drawing the diagram with dummy node first will save you many bugs.

8. Pattern: Tree Breadth First Search

Core idea. Visit a tree level by level using a queue. Each iteration of the outer loop processes exactly one level, which makes level-based questions trivial.

Recognize it when. The problem asks for level order, level averages, right-side view, zigzag traversal, minimum depth, or the largest value in each level. Anything where the answer is structured "per level" is a BFS problem.

How it works. Push the root into a queue. While the queue is not empty, record its current size (this is the number of nodes at the current level), then loop that many times, popping each node, processing it, and pushing its children. Repeat until the queue empties. The "current level size" trick is the key to keeping levels separated.

Typical complexity. Time: O(n) where n is the number of nodes. Space: O(w) where w is the maximum width of the tree (worst case n/2 for a balanced tree).

Variations. Standard level order. Reverse level order (push results to the front, or use a deque). Zigzag (alternate direction per level). Connect level order siblings (populating next pointers).

Example problems. Level Order Traversal, Reverse Level Order Traversal, Zigzag Traversal, Level Averages in a Binary Tree, Minimum Depth of a Binary Tree, Right View of a Binary Tree, Connect Level Order Siblings.

Watch out for. Forgetting to capture the level size before the inner loop, which mixes nodes from different levels. Not handling null roots up front (return empty result immediately).

9. Pattern: Tree Depth First Search

Core idea. Walk a tree by going as deep as possible down one branch before backtracking and exploring the next. Naturally implemented with recursion (or an explicit stack).

Recognize it when. The problem asks for path-related quantities: root-to-leaf paths, path sums, longest path, diameter, lowest common ancestor, or any answer that depends on the relationship between an ancestor and its descendants.

How it works. Recurse on the left subtree, recurse on the right subtree, and combine their results at the current node. Pre-order, in-order, and post-order traversals differ only in when you process the current node relative to its children. For path-tracking problems, pass the current path as a parameter and either undo your changes when returning (true backtracking) or pass an immutable copy.

Typical complexity. Time: O(n). Space: O(h) where h is the height of the tree, due to the recursion stack. O(log n) for balanced trees, O(n) for skewed trees.

Variations. Pre-order, in-order, post-order. Path-sum problems. All-paths enumeration. Tree diameter (longest path between any two nodes). Lowest Common Ancestor. Serialize and deserialize.

Example problems. Binary Tree Path Sum, All Paths for a Sum, Count Paths for a Sum, Sum of Path Numbers, Tree Diameter, Path with Maximum Sum, Lowest Common Ancestor of a Binary Tree.

Watch out for. Forgetting the base case when the node is null. In path-tracking problems, not popping the last node from the path when returning (causes the path list to leak across branches). Confusing global state with returned values.

10. Pattern: Two Heaps

Core idea. Split a stream of numbers into a smaller half and a larger half, kept in a max-heap and a min-heap respectively. The tops of the two heaps give you instant access to the median or other order-statistic queries.

Recognize it when. You see a data stream of numbers and need the running median, or you need fast access to the largest of the small half and the smallest of the large half. Any "find the middle as numbers arrive" problem fits.

How it works. Maintain a max-heap for the smaller half and a min-heap for the larger half. When a new number arrives, push it onto one heap based on a comparison with the max-heap's top, then rebalance so the heap sizes differ by at most one. The median is either the top of the larger heap or the average of both tops.

Typical complexity. Insertion: O(log n). Median query: O(1). Total space: O(n).

Variations. Find the median from a number stream. Sliding window median (requires lazy deletion or an ordered multiset). Maximize capital with two heaps. IPO problem.

Example problems. Find the Median of a Number Stream, Sliding Window Median, Maximize Capital, IPO, Next Interval.

Watch out for. Forgetting to rebalance after each insertion, which lets one heap grow unbounded. In sliding window median, plain heaps cannot remove arbitrary elements efficiently, so use lazy deletion (mark elements as removed and lazily clean the top) or a balanced tree.

11. Pattern: Subsets

Core idea. Enumerate all subsets, permutations, or combinations of an input by building them up incrementally. Each existing partial result spawns new partial results when the next element is considered.

Recognize it when. The problem asks you to generate all subsets, all permutations, all combinations, or to enumerate the power set. Any "find all possible X" question over a small input is a subset-pattern problem.

How it works. The classic iterative approach: start with a list containing the empty subset. For each input element, copy every existing subset and append the new element to the copies, then add the copies to the list. After processing all elements, the list contains all 2^n subsets. The recursive (backtracking) version makes a yes-or-no choice for each element.

Typical complexity. Time: O(n × 2^n) for subsets, O(n × n!) for permutations. Space: same as time, since you are storing the output.

Variations. Subsets without duplicates. Subsets with duplicates (sort first and skip equal siblings). Permutations. Permutations with duplicates. K-combinations. String permutations by changing case.

Example problems. Subsets, Subsets With Duplicates, Permutations, Letter Case Permutation, Balanced Parentheses, Unique Generalized Abbreviations.

Watch out for. Duplicate handling. When the input has duplicates, sort it first and skip elements equal to the previous one at the same recursion depth, otherwise you produce duplicate subsets. Also, distinguish between subsets (order does not matter) and permutations (order matters).

12. Pattern: Modified Binary Search

Core idea. Binary search is not just for finding a value in a sorted array. The same halving logic applies whenever you can answer the question "is the answer to my left or my right" in O(1) at the midpoint.

Recognize it when. The input is sorted, partially sorted (rotated), or has a monotonic property. You need to find a target, a boundary, a peak, or the smallest value satisfying some condition. The constraint hints at log n or the input is huge.

How it works. Maintain low and high boundaries. At each step, compute mid, evaluate a condition, and decide whether to move low to mid plus 1 or high to mid minus 1. The trick in "modified" variants is the condition itself: it might compare neighbors, check rotation, or test a candidate answer in answer-space search.

Typical complexity. Time: O(log n). Space: O(1).

Variations. Order-agnostic binary search (you do not know if the array is ascending or descending). Search in a rotated sorted array. Find peak element. Find first or last position. Search in an infinite sorted array. Binary search on the answer (search the answer space, not the input).

Example problems. Order-agnostic Binary Search, Ceiling of a Number, Next Letter, Number Range, Search in a Sorted Infinite Array, Minimum in Rotated Sorted Array, Koko Eating Bananas, Capacity to Ship Packages.

Watch out for. The classic infinite loop: make sure low and high actually move on every iteration. Off-by-one errors in the boundary updates. For "binary search on the answer," correctly identifying the search space and the monotonic predicate is the whole problem.

13. Pattern: Top K Elements

Core idea. When you need the top K largest, smallest, or most frequent elements out of n total, use a heap of size K rather than sorting all n elements. You trade O(n log n) for O(n log k).

Recognize it when. The problem asks for the K largest, K smallest, K most frequent, or Kth largest in a stream. Any "top K" or "Kth" phrasing is the strongest possible signal.

How it works. For the K largest, build a min-heap and push each element. If the heap grows beyond size K, pop the smallest. After processing every element, the heap contains the K largest. The current min on the heap is the Kth largest. For K smallest, mirror the logic with a max-heap.

Typical complexity. Time: O(n log k). Space: O(k).

Variations. Top K largest or smallest from an array. Top K frequent elements (use a frequency map plus heap). Kth largest in a stream. K closest points to origin. Reorganize string. Frequency sort.

Example problems. Top K Frequent Numbers, Kth Largest Number in a Stream, Top K Frequent Elements, K Closest Points to Origin, Connect Ropes with Minimum Cost, Reorganize String.

Watch out for. Choosing the wrong heap direction. For K largest, you need a min-heap of size K (counterintuitive at first). Forgetting to maintain the size bound, which collapses the optimization back to a full sort.

14. Pattern: Bitwise XOR

Core idea. XOR has two magical properties: a XOR a equals 0, and a XOR 0 equals a. Combined, these let you find unique elements among pairs or solve bit-manipulation problems with O(1) space.

Recognize it when. The problem involves finding a single number among pairs, finding two unique numbers, computing a complement, flipping bits, or using bit-level tricks. The input is integers and the constraints suggest constant-space.

How it works. XOR all the numbers together. Pairs cancel out, and the unique number remains. For "two unique numbers," XOR everything to get their XOR sum, then use any set bit in the result to partition the array into two groups, each containing one unique number, and XOR each group.

Typical complexity. Time: O(n). Space: O(1).

Variations. Single number among duplicates. Two single numbers among duplicates. Complement of a base-10 number. Flip and invert image. Missing number using XOR (XOR all values 0 to n with all array values).

Example problems. Single Number, Single Number II, Two Single Numbers, Complement of Base 10 Number, Flip an Image, Missing Number.

Watch out for. Bit-by-bit thinking is required: trace through small examples on paper before coding. Negative numbers and language-specific integer widths can bite you in problems like "complement of a base-10 number," where you only flip the bits used in the number's binary representation, not all 32.

15. Pattern: Backtracking

Core idea. Explore a tree of decisions by making a choice, recursing, and undoing the choice if it fails. Pruning bad branches early is what makes backtracking faster than pure brute force.

Recognize it when. The problem asks for all valid configurations, all paths, all placements, or for any one configuration meeting strict constraints. Combinatorial puzzles, board placements, and constraint satisfaction problems are textbook backtracking.

How it works. At each decision point, iterate over the available choices. For each choice, apply it, recurse to the next decision, and then undo it (the "backtrack" step) before trying the next choice. Cut off branches early when partial state already violates a constraint. The decision tree has depth equal to the number of decisions and branching factor equal to the choices per decision.

Typical complexity. Highly variable. The worst case is exponential, often O(b^d) for branching factor b and depth d. Good pruning can dramatically reduce real-world runtime.

Variations. Generate all valid combinations. Constraint satisfaction (N-Queens, Sudoku). Path finding with constraints. Word search on a grid. Graph coloring. Generating parentheses.

Example problems. Sudoku Solver, N-Queens, Generate Parentheses, Word Search, Letter Combinations of a Phone Number, Combination Sum, Palindrome Partitioning.

Watch out for. Forgetting the undo step, which corrupts state across branches. Insufficient pruning, which makes the solution time out. Mutating shared state without undoing it on return.

16. Pattern: 0/1 Knapsack (Dynamic Programming)

Core idea. For each item, you make one yes-or-no decision: take it or skip it. The optimal answer is built up from optimal answers to smaller subproblems, indexed by the items considered so far and the remaining capacity.

Recognize it when. You have a set of items with weights or costs and values, and a capacity or budget. You need to maximize or minimize an aggregate. Or the problem can be reframed as "pick a subset that sums to X."

How it works. Define dp[i][c] as the best value achievable using the first i items with capacity c. The transition is a maximum over two cases: skip item i (dp[i minus 1][c]), or take item i if it fits (dp[i minus 1][c minus w_i] plus v_i). The answer is dp[n][C]. Space can usually be compressed from 2D to 1D by iterating capacity in reverse.

Typical complexity. Time: O(n × C). Space: O(n × C) for the 2D table, O(C) for the space-optimized 1D version.

Variations. Standard 0/1 Knapsack (maximize value). Equal Subset Sum Partition. Subset Sum (decision version). Minimum Subset Sum Difference. Count of Subsets with Given Sum. Target Sum (assign signs).

Example problems. 0/1 Knapsack, Equal Subset Sum Partition, Subset Sum, Minimum Subset Sum Difference, Count of Subsets with Given Sum, Target Sum.

Watch out for. Distinguishing 0/1 (each item used at most once) from Unbounded Knapsack (items can be reused). When space-optimizing to 1D, iterate capacity in reverse for 0/1 to avoid reusing the current item, and forward for Unbounded.

17. Pattern: Topological Sort (Graph)

Core idea. Order the vertices of a directed acyclic graph so every edge points from earlier to later in the order. If the graph has a cycle, no valid order exists.

Recognize it when. The problem describes prerequisites, dependencies, build order, course scheduling, or "do these things in some valid order." The data is a directed graph, and you need either a valid order or a count of valid orders, or to detect a cycle.

How it works. Kahn's algorithm: build an in-degree count for every vertex. Start a queue with all vertices of in-degree 0. Repeatedly pop a vertex, append it to the result, and decrement the in-degrees of its neighbors. When a neighbor reaches in-degree 0, push it. If the result contains all vertices, it is a valid topological order. If not, the graph has a cycle. The DFS-based variant pushes vertices onto a stack in post-order.

Typical complexity. Time: O(V plus E). Space: O(V plus E) for the graph and queue.

Variations. Single valid order (Kahn's BFS). All valid orders (backtracking over choices when multiple vertices have in-degree 0). Cycle detection. Lexicographically smallest order (use a min-heap instead of a queue). Alien dictionary (build the graph from string comparisons first).

Example problems. Task Scheduling Order, All Tasks Scheduling Orders, Alien Dictionary, Course Schedule, Course Schedule II, Reconstructing a Sequence.

Watch out for. Mistakenly running topological sort on an undirected graph: it does not apply. Forgetting that disconnected components still need to all show up in the result. When all-orders is required, the search space can blow up exponentially.

18. Pattern: K-way Merge

Core idea. When you need to merge K sorted lists into one sorted output, a min-heap of "current head pointers" gives you the next smallest element in O(log K) per pop.

Recognize it when. The input is multiple sorted lists, sorted arrays, or sorted streams, and you need a single merged output, the Kth element across all of them, or a smallest range covering at least one element from each.

How it works. Push the first element of each list (along with its list identifier and index) onto a min-heap. Pop the smallest, append it to the output, and push the next element from that list onto the heap. Repeat until the heap is empty. The heap always contains exactly one candidate per list, so the next smallest is always at the top.

Typical complexity. Time: O(N log K) where N is the total number of elements across all lists. Space: O(K).

Variations. Merge K sorted linked lists. Merge K sorted arrays. Kth smallest in a sorted matrix. Smallest number range covering elements from K lists. Find K pairs with smallest sums.

Example problems. Merge K Sorted Lists, Kth Smallest Number in M Sorted Lists, Smallest Number Range, Find K Pairs with Smallest Sums, Kth Smallest Element in a Sorted Matrix.

Watch out for. Not handling empty input lists when building the initial heap (skip them). Forgetting to track which list each heap element came from, so you cannot push its successor. For "smallest range" problems, also track the current maximum across the heap.

19. Pattern: Monotonic Stack

Core idea. A stack where elements are kept in either non-increasing or non-decreasing order. When pushing a new element would violate the order, pop the offenders. Each pop usually reveals a "next greater" or "next smaller" relationship.

Recognize it when. The problem asks for the next greater element, next smaller element, previous greater, previous smaller, span of stock prices, largest rectangle in a histogram, or "for each element, find the closest X to the right." Anything with a "next/previous greater/smaller" theme fits.

How it works. Walk the array left to right. Maintain a stack of indices whose values are in monotonic order. Before pushing the current index, pop every element whose value violates the order (for example, every smaller value if the stack is non-increasing). Each popped element has just been "answered" by the current element, which is its next greater. Push the current index.

Typical complexity. Time: O(n). Space: O(n).

Variations. Next greater element. Next smaller element. Previous greater or smaller. Largest rectangle in histogram. Daily temperatures. Trapping rain water (alternative O(n) approach).

Example problems. Next Greater Element, Next Smaller Element, Largest Rectangle in Histogram, Daily Temperatures, Stock Span, Sum of Subarray Minimums.

Watch out for. Choosing the wrong monotonic direction (increasing vs decreasing) for the question being asked. Off-by-one in index versus value tracking. Forgetting to pop remaining elements at the end (some problems need a sentinel value at the end of the array to flush the stack).

20. Pattern: Multi-threaded

Core idea. Use multiple threads with synchronization primitives (locks, semaphores, condition variables) to solve a problem where the order of execution matters or where work can be split safely.

Recognize it when. The problem statement explicitly mentions threads, concurrent execution, ordering across threads, or producer-consumer style scenarios. Common at companies that emphasize concurrency, especially for backend or systems roles.

How it works. Identify the synchronization need: ordering, mutual exclusion, or signaling. Use a counting semaphore to control how many threads can proceed past a point. Use a mutex for mutual exclusion. Use a condition variable (or wait-notify in Java) for "wait until X becomes true." Carefully design which thread releases the resource the next thread is waiting for, so no thread starves.

Typical complexity. Asymptotic complexity is usually the same as the single-threaded version; the goal is correctness under concurrent execution, not asymptotic speedup.

Variations. Strict ordering of prints across threads. Producer-consumer with bounded buffers. Reader-writer locks. Building a structure with multiple worker threads (web crawler). Dining philosophers (classic deadlock-avoidance).

Example problems. Print in Order, Print FooBar Alternately, Print Zero Even Odd, Building H2O, Fizz Buzz Multithreaded, Web Crawler Multithreaded, Dining Philosophers.

Watch out for. Deadlocks (always acquire locks in the same order). Race conditions (test shared state always inside a critical section). Spurious wake-ups in condition variables (always re-check the predicate inside a while loop, not an if).

21. Pattern: Union Find

Core idea. A data structure that tracks a partition of elements into disjoint sets and supports two operations efficiently: find (which set does this element belong to) and union (merge two sets). With path compression and union by rank, both are nearly O(1) on average.

Recognize it when. The problem involves connectivity in a graph, dynamic equivalence relations, or "are these two things in the same group?" Cycle detection in undirected graphs, connected components, Kruskal's MST algorithm, and the percolation problem all use Union Find.

How it works. Each element points to a parent, and the root of each tree represents the set. Find walks up the parent pointers until it reaches a root, optionally compressing the path by repointing every node on the way directly to the root. Union finds the roots of two elements and links one root to the other, optionally using rank or size to keep trees shallow.

Typical complexity. Time per operation: amortized O(α(n)), the inverse Ackermann function, which is effectively constant. Space: O(n).

Variations. Connectivity queries. Cycle detection in undirected graphs. Kruskal's minimum spanning tree. Number of connected components. Dynamic connectivity. Weighted Union Find for storing relationships beyond equivalence.

Example problems. Graph Redundant Connection, Number of Provinces, Is Graph Bipartite (alternative approach), Number of Islands II, Accounts Merge, Most Stones Removed with Same Row or Column.

Watch out for. Forgetting to apply path compression and union by rank, which degrades performance to O(n) per operation. Mutating the parent array while iterating, which is fine but easy to confuse with copying. For weighted Union Find, the relationship update during find requires care.

22. Pattern: Counting

Core idea. Many problems collapse to "count how many times each value appears" plus some downstream logic on those counts. Hash maps and frequency arrays are the workhorse data structures.

Recognize it when. The problem mentions frequency, occurrences, anagrams, majority element, finding duplicates, or "how many distinct/equal/different X are there." Inputs with bounded value ranges often use a fixed-size array instead of a hash map.

How it works. Walk the input once and increment a counter for each element. Then walk the counts and answer the actual question (find the max, find the threshold, find duplicates). For sliding-window variants, increment as elements enter and decrement as they leave.

Typical complexity. Time: O(n) for counting, plus whatever the downstream logic needs. Space: O(k) where k is the number of distinct values.

Variations. Frequency map for counting. Boyer-Moore majority vote (O(1) space for majority element). Counting sort as a stepping stone. Anagram detection by counting letters. Sliding window with frequency map (combine with Pattern 4).

Example problems. Count Elements With Maximum Frequency, Maximum Population Year, Least Number of Unique Integers after K Removals, Majority Element, Group Anagrams, Top K Frequent Elements.

Watch out for. Choosing a hash map when a fixed-size array would be faster (lowercase letters are 26 slots, ASCII is 128, etc.). Forgetting to handle case sensitivity or whitespace in string-counting problems.

23. Pattern: Monotonic Queue

Core idea. A double-ended queue where elements are kept in monotonic order. Unlike a monotonic stack, you can pop from both ends, which makes it ideal for sliding window maximum or minimum queries.

Recognize it when. The problem combines a sliding window with a max or min query at each step, or asks for "the max in every window of size K." The brute force is O(n × k); the monotonic deque brings it to O(n).

How it works. Maintain a deque of indices. Before pushing the current index, pop from the back any index whose value violates monotonicity. Before reading the answer for the current window, pop from the front any index that has fallen outside the window. The front of the deque is always the index of the max (for a non-increasing deque) or min in the current window.

Typical complexity. Time: O(n), since each index is pushed and popped at most once. Space: O(k).

Variations. Sliding window maximum or minimum. Shortest subarray with sum at least K. Constrained subsequence sum. Jump game with deque optimization.

Example problems. Sliding Window Maximum, Shortest Subarray with Sum at Least K, Constrained Subsequence Sum, Jump Game VI, Sum of Subarray Minimums (combined with monotonic stack).

Watch out for. Storing values directly when you actually need indices (you usually need indices to detect when an entry has slid out of the window). Mixing up the front and back operations when implementing in your language of choice.

24. Pattern: Simulation

Core idea. Some problems do not have a clever shortcut. The fastest path is to model the system step by step and execute the rules as written.

Recognize it when. The problem describes a process: a robot moving on a grid, water filling a container, a game playing out, a queue processing requests. The constraints are usually small enough that a direct simulation fits within the time limit.

How it works. Translate the rules of the system into code as faithfully as possible. Maintain the state (position, time, inventory, configuration) and update it according to the rules until a stopping condition is reached. For grid simulations, use direction arrays to handle movement compactly. For time-based simulations, often a priority queue keyed by event time is the right structure.

Typical complexity. Varies. Often O(steps × work-per-step). The constraints will hint at how large the simulation can be.

Variations. Robot or pointer moving on a grid. Queue or stream processing. Game state evolution. Spiral matrix traversal. Iterating until a fixed point or stable state.

Example problems. Array Transformation, Water Bottles, Spiral Matrix III, Robot Bounded in Circle, Game of Life, Pour Water.

Watch out for. Reaching for cleverness when simulation is the intended solution and would have been simpler. Underestimating the state size: if the state space repeats, you may need cycle detection. Off-by-one errors in movement and bounds checks.

25. Pattern: Linear Sorting Algorithms

Core idea. Comparison-based sorting has a lower bound of O(n log n), but if the data is constrained (small range, fixed alphabet, distributable buckets), you can sort in O(n) using counting, radix, or bucket sort.

Recognize it when. The values are integers in a small known range, or strings of bounded length, or you have to sort by a key with a small distribution. Constraints like "0 to 1000" or "lowercase English letters" are strong signals.

How it works. Counting sort: count the frequency of each value, then write values back in order based on cumulative counts. Radix sort: counting-sort by each digit (or character) from least to most significant. Bucket sort: partition values into buckets by range, sort each bucket (often with insertion sort), and concatenate.

Typical complexity. Counting sort: O(n plus k) where k is the value range. Radix sort: O(d × (n plus k)) where d is the number of digits. Bucket sort: O(n) average, O(n²) worst case.

Variations. Counting sort. Radix sort (LSD or MSD). Bucket sort. Pigeonhole sort. Used as a subroutine for problems with extra constraints, like "sort by frequency."

Example problems. Relative Sort Array, Height Checker, Array Partition, Maximum Gap, Sort Colors (Dutch National Flag).

Watch out for. Memory usage: counting sort with a huge value range is wasteful and can blow up memory. Stability matters for radix sort: the inner counting sort must be stable. For bucket sort, choose bucket size carefully or you collapse to a single bucket.

26. Pattern: Meet in the Middle

Core idea. When a brute-force search over n items is 2^n and too slow, split the input into two halves of size n/2, enumerate each half independently (2^(n/2) each), and combine the two halves smartly. The total cost drops from 2^n to roughly 2^(n/2) which can be the difference between feasible and impossible.

Recognize it when. The problem looks like a subset-sum or combination search, n is too large for full brute force (n around 30 to 40) but small enough that 2^(n/2) is fine. The brute force is exponential in n.

How it works. Split the input into halves A and B. Enumerate all subset sums (or whatever the partial state is) of A, and store them in a sorted list or hash map. Then enumerate all subsets of B; for each, compute what it needs from A and look it up. The lookup is O(log) or O(1), and the total cost is dominated by the two halves.

Typical complexity. Time: O(2^(n/2)) typically with a log factor for sorting or binary search. Space: O(2^(n/2)).

Variations. Subset sum equal to a target. Closest subset sum to target. Splitting into pairs of disjoint subsets. K-shortest path variants.

Example problems. Subset Sum Equal to Target, Subsets having Sum between A and B, Closest Subsequence Sum, Partition to K Equal Sum Subsets (with optimizations).

Watch out for. This pattern is only worth using when the input size makes it necessary. Below n equals 20 or so, plain DP or backtracking with pruning is usually simpler and just as fast. The combine step is the trickiest part to get right.

27. Pattern: Mo's Algorithm

Core idea. When you have many range queries on a static array, group the queries cleverly so that successive queries share most of their range. Move the window's two boundaries incrementally between queries and answer each in nearly constant amortized time per element move.

Recognize it when. The problem gives you an array and Q offline queries of the form "answer something about the range [L, R]." Q and N are both up to around 10^5 to 10^6, and a naive per-query loop times out. The queries are static and can be reordered.

How it works. Divide the array into blocks of size roughly √n. Sort the queries by (L's block, then by R), with R sorted in alternating directions per block. Maintain a current window [curL, curR] and an aggregate (count, frequency map). For each sorted query, slide curL and curR to match the query's L and R, updating the aggregate as elements enter and leave. Record the answer.

Typical complexity. Time: O((n plus q) × √n). Space: O(n) for the aggregate state.

Variations. Mo's algorithm on subarrays. Mo's on trees (with Euler tour). Mo's with updates (3D version, more complex).

Example problems. XOR Queries of a Subarray, Distinct Elements in a Subarray, Minimum Absolute Difference Queries, Powerful Array.

Watch out for. This pattern is rare in coding interviews and shows up mostly in competitive programming. Implementing the bucket sort and the alternating R-sort correctly is fiddly, so practice the template before relying on it. Online queries (where you must answer as they arrive) cannot use Mo's.

28. Pattern: Serialize and Deserialize

Core idea. Convert a complex data structure (tree, graph) into a string or array (serialization), and reverse the process to reconstruct the original from that string (deserialization). The serialization format must capture enough structure for unambiguous reconstruction.

Recognize it when. The problem asks you to encode a tree or graph as a string, send it over a wire, persist it, or reconstruct it from a saved form. Codec design and BST-from-traversal problems are also serialization in disguise.

How it works. For trees, a common approach is pre-order traversal with explicit nulls (so you can rebuild the structure), or level-order with markers. For graphs, encode each node with a unique ID and serialize the adjacency list, then deserialize by first creating all nodes and then linking them. The format choice (delimiters, markers for null) determines how parsing works.

Typical complexity. Time: O(n) for both directions. Space: O(n) for the string and any reconstruction state.

Variations. Serialize and deserialize binary tree. Serialize and deserialize N-ary tree. Serialize and deserialize BST (can skip null markers since traversal order determines structure). Encode and decode strings.

Example problems. Serialize and Deserialize Binary Tree, Serialize and Deserialize N-ary Tree, Serialize and Deserialize BST, Encode and Decode Strings, Verify Preorder Serialization of a Binary Tree.

Watch out for. Forgetting to include null markers, which makes the structure ambiguous. Off-by-one errors when consuming the input string in deserialization. For graphs with cycles, using a visited map keyed by ID is critical to avoid infinite loops.

29. Pattern: Clone

Core idea. Make a deep copy of a complex data structure (a graph or a linked list with extra pointers) such that no node in the copy shares memory with the original.

Recognize it when. The problem asks for a deep copy of a graph, a linked list with random pointers, or a tree with arbitrary cross-links. Anything saying "create an independent clone" or "modifications to the copy must not affect the original" is this pattern.

How it works. Walk the original structure with DFS or BFS. Maintain a hash map from each original node to its newly-cloned counterpart. When you encounter a node, create its clone if not already in the map, then recurse on its neighbors (or follow random pointers, child pointers, etc.) and link the clones together using the map. The map prevents infinite loops in cyclic structures and guarantees one clone per original.

Typical complexity. Time: O(n plus e) where n is nodes and e is edges or extra pointers. Space: O(n) for the map.

Variations. Clone a graph. Clone a linked list with random pointers (alternative O(1) space approach interleaves clones with originals). Clone an N-ary tree. Clone a binary tree with parent pointers.

Example problems. Clone Graph, Copy List with Random Pointer, Clone N-ary Tree, Clone Binary Tree with Random Pointer.

Watch out for. Forgetting to clone all neighbor links, which leaves the clone leaking back into the original. Not handling self-loops (a node whose neighbor includes itself). Missing the visited check, which causes infinite recursion in cyclic graphs.

30. Pattern: Articulation Point and Bridge

Core idea. In an undirected graph, an articulation point is a vertex whose removal disconnects the graph; a bridge is an edge whose removal disconnects it. Both are found in linear time using DFS with discovery times and low-link values (Tarjan's algorithm).

Recognize it when. The problem is about graph connectivity under removal: critical routers in a network, single points of failure, edges whose loss splits the graph, or "what is the minimum to disconnect this." Network reliability and bridge-edge problems are the giveaway.

How it works. Run DFS, recording each node's discovery time and a "low" value defined as the minimum discovery time reachable from its subtree (including via at most one back-edge). A non-root node u is an articulation point if it has a child v with low[v] greater than or equal to disc[u]. The edge (u, v) is a bridge if low[v] is strictly greater than disc[u]. The root is an articulation point if it has more than one DFS child.

Typical complexity. Time: O(V plus E). Space: O(V) for the DFS state.

Variations. Find all articulation points. Find all bridges. Biconnected components. Two-edge-connected components. 2-vertex-connectivity.

Example problems. Critical Connections in a Network, Minimum Number of Days to Disconnect Island, Minimize Malware Spread, Minimize Malware Spread II.

Watch out for. The asymmetric condition for the root (uses child count, not low values). Confusing the strict greater-than for bridges with the greater-than-or-equal for articulation points. Make sure your graph is undirected; this technique does not apply to directed graphs as-is.

31. Pattern: Segment Tree

Core idea. A balanced binary tree built over an array, where each internal node stores an aggregate (sum, min, max) of a range of the array. Point updates and range queries each cost O(log n).

Recognize it when. The problem mixes range queries (sum, min, max over [L, R]) with updates to individual elements or ranges. The number of queries plus updates is large enough that a per-query O(n) walk times out.

How it works. Build the tree bottom-up: leaves correspond to array elements, and each internal node stores the aggregate of its children. To query a range, recurse into nodes whose range overlaps with the query, combining their aggregates. To update, walk from the leaf up, recomputing aggregates along the path. Lazy propagation extends this to range updates by deferring changes to descendants until they are needed.

Typical complexity. Build: O(n). Query: O(log n). Update: O(log n). Space: O(4n) for safety in array-backed implementations.

Variations. Range sum or range min or range max with point updates. Range updates with lazy propagation. 2D segment trees. Persistent segment trees. Merge sort tree (segment tree where each node holds a sorted array).

Example problems. Range Sum Query - Mutable, Range Minimum Query, Queue Reconstruction by Height, Count of Smaller Numbers After Self, Falling Squares.

Watch out for. Off-by-one errors in node-to-range mapping. For lazy propagation, always push the lazy value down to children before doing further work. Use a 1-indexed array of size 4n to avoid out-of-bounds in some implementations.

32. Pattern: Binary Indexed Tree (Fenwick Tree)

Core idea. A compact data structure for prefix sums (or other reversible aggregates) with O(log n) updates and prefix queries. Simpler to implement than a segment tree when you only need prefix-style queries.

Recognize it when. The problem asks for prefix sums with point updates, count-of-smaller-elements (with coordinate compression), or any cumulative-frequency query. Range sum query plus update is the canonical use.

How it works. Use a 1-indexed array. Each index i stores the sum of a specific range determined by the lowest set bit of i. To update index i, walk upward by i plus (i AND minus i) until past n, adding the delta. To query prefix sum up to i, walk downward by i minus (i AND minus i) until 0, accumulating the sum. Range sums [L, R] are computed as prefix(R) minus prefix(L minus 1).

Typical complexity. Update: O(log n). Prefix query: O(log n). Space: O(n).

Variations. Prefix sum with point updates. Range update with point query (using a difference BIT). 2D BIT for matrix prefix sums. Order-statistics tree using a BIT over compressed coordinates.

Example problems. Number of Longest Increasing Subsequence, Maximum Profitable Triplets With Increasing Prices, Count of Range Sum, Reverse Pairs, Count of Smaller Numbers After Self.

Watch out for. Off-by-one indexing: BITs are usually 1-indexed, and forgetting this is the most common bug. The aggregate must be invertible (sum, XOR) for prefix subtraction to work; for max or min, you need a segment tree instead. Coordinate compression is often required when values are large but sparse.

Quick reference: pattern selection cheat sheet

When you see a problem, ask in this order:

1. Is the input sorted? Two Pointers, Modified Binary Search, or Merge Intervals are likely.
2. Is it a contiguous subarray or substring problem? Sliding Window or Monotonic Queue.
3. Is it a linked list with cycle, middle, or in-place reversal? Fast and Slow Pointers, or In-place Linked List Reversal.
4. Is it a tree? BFS for level-order, DFS for path-based.
5. Is it a 2D grid with connected cells? Island (Matrix Traversal).
6. Top K, Kth, or median? Top K Elements or Two Heaps.
7. All combinations or permutations? Subsets or Backtracking.
8. Optimization with capacity or budget? 0/1 Knapsack or related DP.
9. Dependencies or ordering? Topological Sort.
10. Connectivity or grouping? Union Find.
11. Multiple sorted streams? K-way Merge.
12. Next greater or smaller? Monotonic Stack.
13. Many range queries? Segment Tree, Binary Indexed Tree, or Mo's Algorithm.
14. Frequency or counting? Counting pattern.
15. None of the above and the input is small? Backtracking, Simulation, or Meet in the Middle.

If a problem still does not match, revisit the constraints. Constraints are the strongest hint about which pattern fits.

How to use this document the night before an interview

Pick the patterns most relevant to the company you are interviewing at and read those cards. For FAANG-style coding interviews, focus on Two Pointers, Sliding Window, Tree BFS, Tree DFS, Modified Binary Search, Top K Elements, Subsets, Backtracking, 0/1 Knapsack, and Monotonic Stack. Those ten patterns alone cover most questions you will see.

Read each card the way you would read a recipe before cooking: look at the ingredients (recognition cues), skim the steps (how it works), and remember the pitfalls. You do not need to memorize the example problem names. You need to be able to read a new problem and instantly say "this looks like a sliding window with a frequency map."

That is what pattern-based preparation gives you. Practice the recognition. The rest is filling in details.