Problem-Solving Patterns cheat sheet

  • Hash Maps & Sets: Trade memory for time: "have I seen this?", counting, and grouping in O(1).
  • Two Pointers: Two indexes moving toward each other or in the same direction to avoid nested loops.
  • Sliding Window: Grow the window, shrink when it breaks the rule — for subarrays and substrings.
  • Prefix Sums & Difference Arrays: Answer range-sum questions in O(1) and count subarrays with a hash map.
  • Intervals: Sort by start, then merge, insert or sweep — meeting rooms and overlaps.
  • Binary Search: One bug-free template: find the first position where a condition becomes true.
  • Binary Search on the Answer: When the answer is a number and "can I do it with X?" is monotonic.
  • Sorting as a Tool: Custom comparators, counting sort and quickselect for the k-th element.
  • Cyclic Sort: Values 1 to n each have a home index: find missing and duplicate numbers in O(n) time and O(1) space, and count minimum swaps.
  • Fast & Slow Pointers: Cycles, middles and the k-th from the end with two runners at different speeds.
  • In-Place Reversal & Dummy Nodes: Reverse, merge and reorder lists without losing a pointer.
  • Stack Patterns: Matching brackets, evaluating expressions and simulating undo.
  • Monotonic Stack & Queue: Next greater element, histograms and sliding-window maximum in O(n).
  • Heaps: Top-K, K-Way Merge, Two Heaps: Keep only k items, merge sorted streams, and track a running median.
  • Tree DFS: Think in Subtrees: Return values up, pass constraints down — depth, paths, diameter and LCA.
  • Tree BFS: Level by Level: Level-order traversal and every "per level" question.
  • Binary Search Trees: In-order is sorted: validation, k-th smallest and searching with bounds.
  • Graphs & Grids: BFS and DFS: Islands, flood fill, shortest steps in a grid and multi-source BFS.
  • Topological Sort: Order tasks with dependencies and detect cycles (Kahn's algorithm).
  • Union-Find: Group things that are connected, fast — with path compression.
  • Shortest Paths: BFS for unweighted, Dijkstra for weighted, 0-1 BFS for in between.
  • Backtracking: Subsets, combinations, permutations and constraint puzzles with one template.
  • DP Without Fear: From brute-force recursion to memoisation to a table, in four mechanical steps.
  • 1D DP: Climbing stairs, house robber, maximum subarray and longest increasing subsequence.
  • Knapsack Family: Take it or leave it: subset sum, coin change and their variants.
  • Grid DP: Paths and costs on a grid, and how to save memory with one row.
  • String DP: Two strings, two indexes: LCS, edit distance and palindromes.
  • Tree & Interval DP: DP on subtrees (house robber III, cameras) and on ranges (burst balloons, cutting sticks).
  • State-Machine & Bitmask DP: Stock problems as a few states per day, and subsets of a small set as the state.
  • Greedy: Make the best local choice — and how to convince yourself it is safe.
  • Tries: Prefix trees for autocomplete, word search and prefix counting.
  • Bit Manipulation: XOR tricks, masks and counting bits — the handful that interviews use.
  • Designing Data Structures: LRU and LFU caches, O(1) random sets, time-based maps and iterators — combine two structures.
  • Matrix & Simulation: Spiral order, rotation, in-place markers and the Game of Life — index bookkeeping without bugs.
  • Math for Interviews: GCD, primes and the sieve, fast power, modular arithmetic, overflow, and random sampling.
  • String Matching: KMP & Rolling Hash: Find a pattern in O(n + m) with the failure table, and compare substrings in O(1) with hashing.
  • Range Queries: Fenwick & Segment Trees: Prefix sums that survive updates: O(log n) update and query, and counting inversions.