LeetCode Patterns — Master Reference

A consolidated catalog of the recurring patterns behind LeetCode problems, with recognition signals, key operations, and representative problems. Use the Master Taxonomy as the index, then jump into the deep-dive section for the family you're studying.

Master Taxonomy

#	Family	Patterns
1	Arrays & Strings	Two Pointers, Sliding Window, Prefix Sum / Difference Array, Kadane's, Hashing / Frequency Map, Sorting-based, Cyclic Sort, Intervals, Monotonic Stack, Monotonic Deque, String matching (KMP / Rabin-Karp / Z)
2	Linked Lists	Fast & Slow Pointers, In-place Reversal, Merge / Two-list, Dummy Node
3	Trees & BSTs	DFS Traversal, BFS / Level-order, Tree DP, BST properties, LCA, Trie, Segment Tree / Fenwick (BIT), Serialize / Deserialize
4	Graphs	BFS / DFS, Topological Sort, Union-Find (DSU), Dijkstra, Bellman-Ford / Floyd-Warshall, A*, MST (Kruskal / Prim), Bipartite / Coloring, Bridges & Articulation (Tarjan), Eulerian Path
5	Dynamic Programming	1-D Decision DP, Knapsack, Coin Change, LIS, LCS / Edit Distance, Grid DP, Interval DP, Bitmask DP, Tree DP, Digit DP, State-machine DP, Catalan / Counting DP
6	Searching & Selection	Binary Search, Binary Search on Answer, Quickselect, Search in Rotated / 2-D matrix
7	Heap / Priority Queue	Top-K, Merge K Sorted, Two Heaps (median), Scheduling with heap
8	Backtracking	Subsets / Combinations / Permutations, Constraint satisfaction, Grid enumeration, Partitioning
9	Greedy	Interval scheduling, Jump Game, Task scheduling, Huffman-style
10	Math & Number Theory	GCD/LCM, Primes / Sieve, Modular exponentiation, Bit Manipulation, Combinatorics, Geometry, Probability / Randomization, Digit / Base
11	Design & Data Structures	LRU / LFU Cache, O(1) Insert/Delete/GetRandom, Iterator design, Rate limiter / Hit counter, Min / Max Stack
12	Specialized / Advanced	Line Sweep, Meet in the Middle, Rolling Hash, Reservoir Sampling, Matrix Exponentiation, Mo's Algorithm, Suffix Array / Automaton

Priority tiers (what to study first)

Tier	Patterns
Must-know	Two Pointers, Sliding Window, Hashing, Binary Search, BFS/DFS, DP (1-D + grid), Backtracking, Heap / Top-K, Intervals, Prefix Sum
High-value	Monotonic Stack, Union-Find, Topological Sort, Trie, Binary Search on Answer, Fast/Slow Pointers, Greedy, Bit Manipulation
Advanced / rarer	Segment Tree / BIT, Dijkstra, Bitmask DP, Digit DP, Line Sweep, Meet in the Middle

Interval Patterns

#	Pattern	Signal	Key Operation	Problems
1	Merge Overlapping	"merge", "combine overlapping"	Sort by start; if `curr.start <= prev.end`, `prev.end = max(prev.end, curr.end)`	Merge Intervals (56), Employee Free Time (759)
2	Insert Interval	"add interval to sorted list"	Three phases: before, merge overlap, after	Insert Interval (57)
3	Interval Intersection	"overlap of two sorted lists"	overlap = `[max(starts), min(ends)]`; advance smaller end	Interval List Intersections (986)
4	Non-Overlapping (Greedy)	"max non-overlapping", "min removals"	Sort by end, greedily pick earliest finish	Non-overlapping Intervals (435), Min Arrows (452), Max Length Pair Chain (646)
5	Meeting Rooms / Max Concurrent	"min rooms", "max concurrent"	Min-heap of end times, or +1/−1 sweep	Meeting Rooms I/II (252/253), Car Pooling (1094), My Calendar (729/731/732)
6	Sweep Line / Event Counting	"skyline", "painting", "running count"	start(+1)/end(−1) events, sort, sweep	Skyline (218), Describe the Painting (1943), Points That Intersect (2848)
7	Interval Covering / Jump	"cover the range", "fewest intervals"	Greedy furthest-reach	Video Stitching (1024), Min Taps to Water Garden (1326), Teemo (495)
8	Interval + Heap	"min groups/machines", "attend events"	Sort by start, heap tracks availability	Max Events Attended (1353), Divide Intervals Into Min Groups (2406)

Decisions

Decision	Rule of thumb
Sort by start vs. end	Merge/insert → start. Greedy scheduling / max count → end.
Overlap test	`a.start <= b.end && b.start <= a.end`
Heap vs. sweep line	Heap when tracking "which resource frees first"; sweep when you only need a count.

Heap / Priority Queue Patterns

#	Pattern	Signal	Key Operation	Problems
1	Top-K Elements	"kth largest", "top k frequent"	K largest → min-heap size K; K smallest → max-heap size K	Kth Largest (215), Top K Frequent (347/692), K Closest Points (973)
2	Merge K Sorted	"merge k sorted", "smallest range"	Push heads to min-heap, pop & push successor	Merge k Lists (23), Kth Smallest in Matrix (378), Smallest Range (632), K Pairs Smallest Sums (373)
3	Two Heaps (Median)	"median from stream", "balance halves"	Max-heap (low half) + min-heap (high half), balanced	Median from Data Stream (295), Sliding Window Median (480), IPO (502)
4	Scheduling / Greedy w/ Heap	"priorities", "cpu", "cooldown"	Heap picks next-best available choice	Task Scheduler (621), Reorganize String (767), Single-Threaded CPU (1834)
5	Kth in Ordered Space	"kth smallest sum/product/pair"	Lazily explore implicit sorted space	Kth Smallest Matrix (378), K Pairs (373), Ugly Number II (264)
6	Running Max/Min (Lazy Delete)	"max in window", "constrained subseq"	Skip stale heap tops; pair with indices	Constrained Subsequence Sum (1425), Jump Game VI (1696)
7	Interval / Resource w/ Heap	"min rooms/groups"	Sort by start, heap of end times	Meeting Rooms II (253), Divide Intervals (2406), Car Pooling (1094)
8	Greedy Repeated Extremes	"last stone", "connect sticks"	Extract & reinsert extreme while simulating	Last Stone Weight (1046), Connect Sticks (1167), Furthest Building (1642)
9	Dijkstra (Heap-based BFS)	"cheapest/shortest weighted path"	Min-heap pops closest unvisited node	Network Delay (743), Min Effort Path (1631), Cheapest Flights (787), Swim in Water (778)

Decisions

Decision	Rule of thumb
Min vs. max heap for Top-K	K largest → min-heap size K. K smallest → max-heap size K. (Counterintuitive.)
Heap vs. sort	Heap wins when K ≪ n, or data streams. Sort wins if you need everything ordered.
Heap vs. quickselect	Quickselect: O(n) avg for a single Kth. Heap: O(n log k), handles streams & ties.
Lazy deletion	Push replacements; discard stale tops when popped.

Two / Three / N Pointer Patterns

#	Pattern	Signal	Key Operation	Problems
1	Opposite Ends (Converging)	"sorted", "pair sums to", "container"	`sum<target → left++`; `sum>target → right--`	Two Sum II (167), Container With Most Water (11), Trapping Rain Water (42), Valid Palindrome (125)
2	Fast & Slow	"cycle", "middle", "nth from end"	`slow=slow.next; fast=fast.next.next`	Linked List Cycle (141/142), Middle (876), Remove Nth From End (19), Happy Number (202), Find Duplicate (287)
3	Read/Write In-Place	"remove in place", "move zeroes"	Write advances only when element kept	Remove Duplicates (26/80), Move Zeroes (283), Remove Element (27)
4	Sliding Window (same dir)	"longest/shortest subarray", "at most K"	Expand right; shrink left while invalid	Longest Substring No Repeat (3), Min Window Substring (76), Longest Repeating Char Replace (424)
5	Two Sequences (Merge/Compare)	"merge sorted", "is subsequence"	Advance whichever pointer lags	Merge Sorted Array (88), Intersection (350), Is Subsequence (392), Backspace Compare (844)
6	Three Pointers (3Sum family)	"triplets", "sum closest"	Fix `i`, converging two-pointer on rest; skip dups	3Sum (15), 3Sum Closest (16), 4Sum (18), Valid Triangle (611)
7	Partition (Dutch Flag)	"sort 0/1/2", "partition around pivot"	low / mid / high regions in one pass	Sort Colors (75), Wiggle Sort II (324)
8	Expand from Center	"palindromic substring"	Grow outward from center(s)	Longest Palindromic Substring (5), Palindromic Substrings (647)
9	N Pointers / K-way	"k sorted lists"	One pointer per list, advance the min	Merge k Lists (23), Smallest Range (632), Median of Two Sorted Arrays (4)

Decisions

Decision	Rule of thumb
Opposite-ends vs. sliding window	Opposite ends → sorted, answer is pair/area. Window → contiguous subarray with a constraint.
Sort first?	2Sum sorted → no. 3Sum/4Sum → yes. Fast/slow cycle → no.
Dedup in kSum	After a valid tuple, skip equal neighbors on both pointers.
Cycle start	Reset one pointer to head after meeting, advance both by 1.
Which pointer moves?	Merge/compare → advance the one at the smaller value.

Sliding Window Patterns

#	Pattern	Signal	Key Operation	Problems
1	Fixed-Size Window	"subarray of size K"	Add `arr[right]`; when `right>=K` remove `arr[right-K]`	Max Average Subarray (643), Sliding Window Max (239), Find All Anagrams (438), Permutation in String (567)
2	Variable — Longest	"longest with...", "at most K distinct"	Expand right; shrink left while invalid; record max after valid	Longest Substring No Repeat (3), Longest Repeating Char Replace (424), Max Consecutive Ones III (1004), Fruit Into Baskets (904)
3	Variable — Shortest	"min/shortest that...", "smallest window containing"	Expand right; while valid record min then shrink left	Min Window Substring (76), Min Size Subarray Sum (209), Replace Substring Balanced (1234)
4	At Most K → Exactly K	"exactly K distinct/odds"	`exactly(K) = atMost(K) − atMost(K−1)`; `count += right-left+1`	Subarrays w/ K Distinct (992), Nice Subarrays (1248), Binary Subarrays With Sum (930)
5	Window + Monotonic Deque	"max/min in window", "max−min ≤ limit"	Pop back while violating monotonicity; pop front when out of window	Sliding Window Max (239), Abs Diff ≤ Limit (1438), Shortest Subarray Sum ≥ K (862)
6	Window + Freq/Hash Map	"anagram", "permutation", "K distinct"	`need`/`have` counters or `matched` count	Min Window Substring (76), Find All Anagrams (438), At Most K Distinct (340), Concatenation of All Words (30)
7	Prefix-Sum + Window	"negatives", "sum ≥ K", "circular"	Prefix sums + deque/hashmap (pure window fails)	Shortest Subarray Sum ≥ K (862), Subarray Sum = K (560), Max Size Subarray Sum = K (325)

Decisions

Decision	Rule of thumb
Longest vs. shortest	Longest → shrink only when invalid, record after. Shortest → shrink while valid, record during.
Can I use a window at all?	Needs monotonic movement toward/away from validity. Negatives break it → prefix-sum + deque/hashmap.
"Exactly K"	Rewrite as `atMost(K) − atMost(K−1)`.
Counting subarrays	Each valid right adds `right − left + 1`.
Fixed vs. variable	Size given → fixed. Size is the answer → variable.
Need window max/min	Use a monotonic deque, not a heap (O(1) removal of exiting element).

Probability & Randomization Patterns

#	Pattern	Signal	Key Operation	Problems
1	Reservoir Sampling	"random node from stream", "unknown length", "O(1) space"	Keep element `i` with prob `1/i` (k=1)	Linked List Random Node (382), Random Pick Index (398)
2	Weighted Random	"prob proportional to weight"	Prefix sums + `bisect_right(prefix, rand(0,total))`	Random Pick with Weight (528), Random Point in Rectangles (497)
3	Rejection Sampling	"randN from randM", "point in circle", "avoid blacklist"	Sample bounding region; resample while invalid	Rand10 from Rand7 (470), Random Point in Circle (478), Random Pick w/ Blacklist (710)
4	Fisher–Yates Shuffle	"shuffle", "each permutation equally likely"	`for i: swap(i, rand(i, n-1))`	Shuffle an Array (384), Random Flip Matrix (519)
5	Expected Value / Prob DP	"probability that...", "expected number", "after N moves"	`P[state] = Σ P[prev] × transition_prob`	Knight Probability (688), New 21 Game (837), Soup Servings (808), Airplane Seat (1227)
6	Randomized Selection	"kth largest", "expected O(n)"	Random pivot → partition → recurse one side	Kth Largest (215), Sort an Array (912)
7	Randomized Data Structure	"insert/delete/getRandom O(1)"	Hashmap(value→index) + array; delete via swap-with-last	Insert Delete GetRandom O(1) (380/381)
8	Monte Carlo / Simulation	"estimate", "simulate"	`successes / trials` over N runs	π-estimation / estimation-style

Decisions

Decision	Rule of thumb
Uniform over stream, unknown length	Reservoir sampling (`k/i`).
Uniform over known weights	Prefix sum + binary search.
Have rand(M), need rand(N)	Rejection sampling.
Uniform permutation	Fisher–Yates, swap into `[i, n)` (into `[0,n)` is biased).
"Prob/expected after k steps"	DP over states, transitions weighted by prob.
Proving uniformity	Every outcome must have prob exactly `1/total`; classic bug is off-by-one in the random range.

Combinatorics Patterns

#	Pattern	Signal	Key Operation	Problems
1	Backtracking Enumeration	"generate all", "return all possible"	`choose → recurse → un-choose`; `start` index blocks reuse	Subsets (78), Permutations (46), Combinations (77), Combination Sum (39/40), Generate Parentheses (22)
2	Counting (Closed-Form nCr)	"how many ways", "count", large N	`C(n,k)=n!/(k!(n-k)!)`; grid paths = `C(m+n-2, m-1)`	Unique Paths (62), Pascal's Triangle (118/119)
3	Permutation Rank/Unrank	"kth permutation", "rank of permutation"	block = `(n-1)!`; digit = `k/(n-1)!`, `k %= (n-1)!`	Permutation Sequence (60), Next Permutation (31)
4	Duplicates (Sort + Skip)	"contains duplicates", "unique combinations"	`if i>start and a[i]==a[i-1]: continue`	Subsets II (90), Permutations II (47), Combination Sum II (40)
5	Catalan Structures	"valid parens count", "unique BSTs", "triangulate"	`C_n = Σ C_i·C_(n-1-i)`	Unique BSTs (96), Generate Parentheses (22), Diff Ways to Add Parens (241)
6	Inclusion–Exclusion	"count that are NOT", "at least one"	`	A∪B	=	A	+	B	−	A∩B	`; total − invalid	Count Numbers w/ Unique Digits (357), Nth Magical Number (878)
7	Stars and Bars	"distribute identical items"	non-neg solutions to `Σx=n` → `C(n+k-1, k-1)`	Integer break / composition counts
8	Combinatorial DP	"number of ways to decode/climb/tile"	`ways[i] = Σ ways[reachable prev]`	Climbing Stairs (70), Decode Ways (91), Coin Change II (518), Combination Sum IV (377)

Decisions

Decision	Rule of thumb
Order matters?	Yes → permutation. No → combination/subset.
Enumerate vs. count	Return all → backtracking. How many → formula/DP.
Reuse elements?	No reuse → pass `i+1`. With reuse → pass `i`.
Duplicates in input	Sort, skip same-value siblings at the same level.
Balanced / nested	Think Catalan.
Distribute identical items	Stars and bars: `C(n+k-1, k-1)`.
Big answers	Return mod 1e9+7; precompute factorials + modular inverses.
Order in counting DP	Ordered (Comb Sum IV) → target outer, coins inner. Unordered (Coin Change II) → coins outer, target inner.

Math & Number Theory Patterns

#	Pattern	Signal	Key Operation	Problems
1	GCD / LCM (Euclidean)	"gcd", "simplify ratio", "water jug"	`gcd(a,b)=gcd(b,a%b)`; `lcm=a/gcd*b`	Water and Jug (365), Fraction Addition (592), GCD of Strings (1071)
2	Primes / Sieve	"count primes", "prime factorization"	Sieve O(n log log n); trial division to `√n`	Count Primes (204), Closest Primes (2523), Prime Arrangements (1175)
3	Modular Arith / Fast Exp	"mod 1e9+7", "pow(x,n)", "x^n mod m"	Binary exponentiation O(log n); Fermat inverse	Pow(x,n) (50), Super Pow (372), Count Good Numbers (1922)
4	Digit Manipulation	"reverse integer", "sum of digits", "palindrome number"	`digit=n%10; n//=10`; watch overflow	Reverse Integer (7), Palindrome Number (9), Add Digits (258), Plus One (66)
5	Base Conversion	"convert to base K", "excel column"	`%base` for digits; `*base+digit` to rebuild	Excel Column (168/171), Convert to Base 7 (504), Add Binary (67)
6	Bit Manipulation	"single number", "count set bits", "power of two"	`n&(n-1)` drops lowest set bit; `x^x=0`; `1<<k`	Single Number (136/137/260), Number of 1 Bits (191), Counting Bits (338), Missing Number (268)
7	Combinatorics Formulas	"how many ways", "unique paths"	nCr, Pascal, Catalan	Unique Paths (62), Pascal's Triangle (118)
8	Geometry / Coordinate	"collinear", "rectangle overlap", "convex hull"	Cross product for orientation; shoelace for area	Max Points on a Line (149), Rectangle Area (223), Valid Square (593), Erect the Fence (587)
9	Number Theory Properties	"bulb switcher", "perfect square", "count divisors"	Odd divisor count ⇔ perfect square; factors to `√n`	Bulb Switcher (319), Perfect Squares (279), Ugly Number (263/264)
10	Sequences & Series	"nth term", "sum of series", "Fibonacci"	Arithmetic sum `n(a1+an)/2`; matrix expo for recurrence	Fibonacci (509), Tribonacci (1137), Missing Number `n(n+1)/2` (268)
11	Overflow-Safe Arithmetic	"without overflow", "divide without /", "multiply strings"	Compare vs. `INT_MAX/10` before multiply; bit-shift division	Divide Two Integers (29), Multiply Strings (43), atoi (8)
12	Math Simulation / Pattern	"after N operations", "look-and-say", "nth digit"	Detect period → `n % period`; or derive formula	Count and Say (38), Nth Digit (400), Elimination Game (390), Nim Game (292)

Decisions

Decision	Rule of thumb
Prime test: one vs. many	Single → trial division to `√n`. Range → Sieve.
Big powers / counts	Binary exponentiation + mod every multiply.
Avoid floating point	Compare slopes/areas as integer cross products / ratios, never `==` on floats.
Overflow guard	Check `result > INT_MAX/10` before `result*10 + d`.
Perfect square shortcut	Odd number of divisors ⇔ perfect square.
`n & (n-1)`	Clears lowest set bit — powers of two, bit counts, subsets.
Divisor loop bound	Iterate `i` to `√n`, pair `i` with `n/i`.
Skip ahead via cycle	Simulate until a state repeats, then `n % period`.

Dynamic Programming — Deep Dive

1-D Decision DP (the "House Robber" family)

The pattern: maximize/minimize over a sequence where choosing element i forbids choosing its neighbor. A binary take/skip choice constrained by the previous decision. Not greedy — parity-based "rob every other house" fails on inputs like [2,1,1,2].

rob[i] = max(rob[i-1],            # skip house i
             rob[i-2] + nums[i])  # rob house i

Only looks back two steps → collapse to two variables:

def rob(nums):
    prev2, prev1 = 0, 0
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

Problem	Twist	What changes
House Robber (198)	line of houses	base recurrence
House Robber II (213)	circle (first & last adjacent)	run twice: `max(rob(nums[1:]), rob(nums[:-1]))`
House Robber III (337)	binary tree	tree DP; node returns `(rob_this, skip_this)`
Delete and Earn (740)	pick `x` deletes `x±1`	bucket counts by value → House Robber on value axis
Climbing Stairs (70)	count ways up	`ways[i] = ways[i-1] + ways[i-2]`
Min Cost Climbing Stairs (746)	min cost	`dp[i] = cost[i] + min(dp[i-1], dp[i-2])`
Paint House (256)	3 colors, no adjacent same	`dp[i][c] = cost + min(dp[i-1][other colors])`

Recognition: a choice that disqualifies an adjacent choice → take/skip DP.

DP sub-patterns overview

Sub-pattern	Signal	Representative
1-D Decision	"adjacent forbidden", "climb"	House Robber (198), Climbing Stairs (70)
Knapsack (0/1)	"subset with total", "can partition"	Partition Equal Subset Sum (416), Target Sum (494)
Unbounded Knapsack	"unlimited reuse"	Coin Change (322), Coin Change II (518)
LIS	"longest increasing subsequence"	LIS (300), Russian Doll Envelopes (354)
2-Sequence (LCS/Edit)	"two strings", "common", "edit"	LCS (1143), Edit Distance (72), Distinct Subsequences (115)
Grid DP	"paths in grid", "min path sum"	Unique Paths (62), Min Path Sum (64), Maximal Square (221)
Interval DP	"merge intervals optimally", "burst"	Burst Balloons (312), Matrix Chain, Palindrome Partition II (132)
Bitmask DP	"n ≤ 20", "visit all", "assignment"	TSP, Partition to K Equal Subsets (698), Shortest Path Visiting All Nodes (847)
State-machine DP	"stock", "cooldown", "at most K transactions"	Best Time to Buy/Sell Stock II–IV (122/123/188), w/ Cooldown (309)
Digit DP	"count numbers ≤ N with property"	Numbers with Repeated Digits (1012), Count Special Integers (2376)

▤Quick Recognition Cheat Sheet

If the problem says…	Reach for…
"sorted array" + "pair/target"	Two Pointers (opposite ends)
"contiguous subarray/substring" + constraint	Sliding Window
"subarray sum equals K" (with negatives)	Prefix Sum + Hashmap
"kth largest / top k"	Heap or Quickselect
"next greater/smaller element"	Monotonic Stack
"max/min in every window"	Monotonic Deque
"merge / overlapping ranges"	Intervals
"shortest path, unweighted"	BFS
"shortest path, weighted"	Dijkstra
"ordering with dependencies"	Topological Sort
"connected / groups / union"	Union-Find
"generate all / list every"	Backtracking
"min/max feasible value"	Binary Search on Answer
"adjacent choice forbidden"	1-D Decision DP (House Robber)
"how many ways"	Counting DP or nCr
"cycle in list / find duplicate"	Fast & Slow Pointers
"prefix / autocomplete / word set"	Trie
"random pick / shuffle / sample"	Randomization (reservoir / weighted / Fisher–Yates)