LeetCode Pattern Guide
Section priorityPriority 5 of 5 — Must know — expect it in almost every loopMust knowPriority 4 of 5 — High value — a gap here costs you roundsHigh valuePriority 3 of 5 — Worth knowing — usually a variant of a must-know patternWorth knowingPriority 2 of 5 — Niche — read once, revisit only if a company is known to askNicheMarked on the sections that carry it — unmarked sections are background/reference.
Scope — The front door: from a problem statement to the card that solves it — the signal in the wording, the constraint cue, the pattern, a link to its card, and the look-alike that is not it. A router only: every template lives in the card a row links to. See also: complexity_cheatsheet.md § 6 — the constraint ruler the “constraint cue” column reads from; lc_category.md — the wisdompeak taxonomy, and which sheet covers each of its categories.
How to use this page
- Read
nfirst. The constraints usually name the complexity before the statement names the pattern:n ≤ 20invites O(2ⁿ),n ≤ 10⁵invites O(n log n) or O(n), and a value range of 10⁹ invites a binary search on the answer. The full ruler is complexity_cheatsheet.md § 6. - Find the row whose signal matches the wording, in the family table below. The signal is the phrase in the statement, not the topic name.
- Open the card, then read the last column before you code. “Looks like it, but is not” is the mistake the row exists to stop: the problem that matches the signal and still wants a different card.
Recognition — signal → pattern → card Priority 5 of 5 — Must know — expect it in almost every loop
One row per pattern. The Card column links to the template that solves the anchor problem; the problems themselves live in that sheet’s examples.
Arrays & strings
| Signal in the statement | Constraint cue | Pattern | Card | Looks like it, but is not |
|---|---|---|---|---|
| “longest / shortest contiguous subarray or substring”, “at most k distinct” | n ≤ 10⁵ | variable sliding window | sliding_window § Template 3 (longest), Template 4 (shortest) | an exact sum, sum == k, where values can be negative → prefix sum + hash map (LC 560) |
| “smallest substring containing all of t”, anagram / permutation of t in s | n ≤ 10⁵, alphabet 26–128 | char-count window | sliding_window § Template 5 | a subsequence, not a substring → two pointers (LC 392) |
| “number of subarrays with exactly k …” | n ≤ 10⁵ | exactly k = at most k − at most (k−1) | sliding_window § Template 6 | the “exactly k” is a sum (sum == k) and values can be negative → prefix sum + hash map; an exact count of distinct values stays here, since signs do not matter to a counter |
| “count subarrays whose sum is k / divisible by k” | n ≤ 10⁵, negatives allowed | prefix sum + count map | prefix_sum § Template 2 (sum), Template 3 (divisible: count equal remainders) | all values positive and you want the longest / shortest → sliding window |
| “many range-sum queries” | q ≤ 10⁵ | prefix sum array | prefix_sum § Template 1 | the array changes between queries → Fenwick / segment tree (LC 307) |
| “add v to every element in [l, r]”, many times | n, updates ≤ 10⁵ | difference array | difference_array § Template 1 | you must read a max after each update → segment tree with lazy propagation |
| “pair / triplet with sum target” on a sorted array, “container”, “palindrome check” | n ≤ 10⁵ | converging two pointers | 2_pointers § Template 2 | unsorted and you need indices → hash map (LC 1) |
| “remove / deduplicate in place”, “move zeros” | O(1) extra space | read/write two pointers | 2_pointers § Template 1 | order does not matter → swap with the last element |
| “sort 0s, 1s and 2s in one pass” | O(1) space | three-way partition | 2_pointers § Template 6 | more than three keys → counting sort |
| “longest palindromic substring”, “count palindromic substrings” | n ≤ 1,000 | expand from centre | 2_pointers § Template 3 | palindromic subsequence → interval DP (LC 516) |
| “two sum” on an unsorted array, “seen before?” | n ≤ 10⁵ | complement lookup | hash_map § Template 1 | sorted input and O(1) space wanted → two pointers (LC 167) |
| “group anagrams”, “count frequencies”, “first unique” | n ≤ 10⁴ | grouping / counting by a computed key | hash_map § Template 3, Template 2 | top-k by frequency → heap or bucket sort (LC 347) |
| “maximum subarray sum / product” | n ≤ 10⁵ | Kadane: best run ending here | kadane_algorithm § 0-2 (sum), § 1-3 (product: keep the min as well as the max) | a subarray of length ≥ k, or a sum = k → prefix sums |
| “merge / insert intervals”, “minimum rooms”, “remove fewest to stop overlap” | n ≤ 10⁴ | sort by start (merge) or by end (schedule) | intervals § Pattern 1, Pattern 2 | many overlapping events at a time → sweep line (LC 253, scanning_line) |
| “kth largest / smallest”, “k closest” | n ≤ 10⁵, one shot | quickselect | quickselect § Template 1 | a stream, or you need all k in order → size-k heap |
Binary search
| Signal in the statement | Constraint cue | Pattern | Card | Looks like it, but is not |
|---|---|---|---|---|
| “sorted array”, “find target / first position / insert position” | n ≤ 10⁵, O(log n) asked | classic binary search (exact match), lower / upper bound (first position, insert position) | binary_search § Template 1 (exact), § Template 2 (bounds) | unsorted but you need a count → sort first, or a hash map |
| “minimum capacity / speed / largest-sum so that it fits in k”, “maximize the minimum distance” | values up to 10⁹ | binary search on the answer | binary_search_on_answer § Template 1 | feasibility flips more than once as the answer grows (not a single true → false or false → true switch) → DP or greedy |
| “rotated sorted array” | n ≤ 5,000, O(log n) asked | binary search, one half is always sorted | binary_search | duplicates allowed → worst case O(n) (LC 81) |
Linked list
| Signal in the statement | Constraint cue | Pattern | Card | Looks like it, but is not |
|---|---|---|---|---|
| “reverse the list / a sublist / k-group”, “reorder” | O(1) space | pointer reversal, dummy head | linked_list § Template 1 | you may use O(n) space → push to a list, rebuild |
| “cycle”, “start of the cycle”, “middle node”, “kth from the end” | O(1) space | fast / slow pointers | 2_pointers § Template 7 | duplicates in an array of 1…n → the same trick on indices (LC 287) |
| “merge k sorted lists” | k ≤ 10⁴ | k-way merge with a heap | heap § Template 3 | only two lists → a plain merge with a dummy head (LC 21) |
Trees
| Signal in the statement | Constraint cue | Pattern | Card | Looks like it, but is not |
|---|---|---|---|---|
| “level by level”, “right side view”, “zigzag”, “minimum depth” | nodes ≤ 10⁴ | BFS with a level loop | bfs § Template 1 | a value aggregated up from the leaves → post-order DFS |
| “diameter”, “balanced?”, “max path sum”, anything a node computes from its children | recursion depth = height | post-order DFS returning a value | dfs § Template 6 | the answer depends on the path from the root → pass it down as an argument (LC 112) |
| “root-to-leaf path with sum”, “all paths” | nodes ≤ 5,000 | pre-order DFS carrying the path | tree_lca_distance § 4 | any downward path, not only from the root → prefix sum on the path (LC 437) |
| “lowest common ancestor” | nodes ≤ 10⁵ | LCA by returned presence | tree_lca_distance § 1 | it is a BST → walk down by value, O(h) (LC 235) |
| “valid BST”, “kth smallest in a BST”, “BST iterator” | nodes ≤ 10⁴ | in-order is sorted | bst § Template 4, Template 5 | a plain binary tree → no ordering to lean on |
| “build the tree from preorder and inorder” | nodes ≤ 3,000 | divide and conquer with an index map | binary_tree § Template 3 | serialize / deserialize → pre-order with null markers (tree_codec) |
“prefix search”, “word dictionary with .”, “many words in a grid” |
words ≤ 3·10⁴ | trie | trie | one word at a time against a set → a hash set is enough |
Graphs
| Signal in the statement | Constraint cue | Pattern | Card | Looks like it, but is not |
|---|---|---|---|---|
| “number of islands”, “connected regions”, “flood fill” | grid ≤ 300 × 300 | grid DFS / BFS, mark visited | dfs § Template 2 | edges arrive one at a time and you query connectivity → union-find |
| “shortest path / minimum steps”, every move costs 1 | V + E ≤ 10⁵ | BFS (mark when enqueued) | bfs § Template 2 | moves have different costs → Dijkstra; costs are 0 or 1 → 0-1 BFS |
| “rotting oranges”, “distance to the nearest 0 / gate” | grid ≤ 10⁵ cells | multi-source BFS | bfs § Template 4 | the distance from one source only → plain BFS |
| “weighted shortest path”, “network delay”, “minimum effort path” | E ≤ 10⁵, weights ≥ 0 | Dijkstra | Dijkstra § Template 1 (additive cost), § LC 1631 (effort: the max edge on the path, not the sum) | negative weights or “at most k stops” → Bellman-Ford (LC 787); all pairs with n ≤ 400 → Floyd-Warshall |
| “course schedule”, “order of tasks with prerequisites”, “alien dictionary” | V + E ≤ 10⁵ | topological sort (Kahn’s BFS) | topology_sorting § Template 1 | an undirected graph → there is no order; check for a cycle with union-find |
| “redundant connection”, “number of provinces”, “accounts merge” | n ≤ 10⁵ | union-find | union_find § 0-3 | you also need path lengths → BFS / DFS |
| “can it be split into two groups”, “is it bipartite” | n ≤ 100 | BFS 2-colouring | graph § Template 6 | three or more groups → backtracking colouring |
| “evaluate division”, ratio queries | V ≤ 100 | DFS over weighted edges, multiplying along the path | dfs § Template 10 | many queries on a fixed graph → union-find with weights |
Dynamic programming
| Signal in the statement | Constraint cue | Pattern | Card | Looks like it, but is not |
|---|---|---|---|---|
| “how many ways to climb / decode”, “rob houses that are not adjacent” | n ≤ 10⁵ | 1-D DP, rolling variables | dp § Template 6 | choices form a tree with no overlap → plain recursion or backtracking |
| “can the string be segmented into words” | n ≤ 300 | prefix partition DP | dp § Template 1b | you must list every segmentation → backtracking with memo (LC 140) |
| “unique paths”, “minimum path sum” in a grid | m, n ≤ 200 | 2-D grid DP | dp § Template 2 | the path can go in any direction → shortest path (Dijkstra / BFS) |
| “subset with sum target”, “partition into equal sums”, “target sum” | n ≤ 200, sum ≤ 10⁴ | 0/1 knapsack | dp § Template 4 | items can be reused (coin change, LC 322 / 518) → unbounded knapsack, loop order flips (dp_loop_order) |
| “longest increasing subsequence”, “Russian dolls” | n ≤ 10⁵ | LIS: O(n²) DP, or O(n log n) with tails (the one n ≤ 10⁵ needs) | dp § Template 7 (O(n²)), patience_sorting § 1-1 (O(n log n)) | contiguous → sliding window or Kadane |
| “longest common subsequence”, “edit distance”, “interleaving” | m, n ≤ 1,000 | 2-D string DP over prefixes | dp_string § LCS deep dive | a common substring → reset to 0 on a mismatch |
| “buy and sell stock with cooldown / fee / k transactions” | n ≤ 10⁵ | state machine DP | dp § Template 5 | one transaction → track the running minimum (LC 121) |
| “burst balloons”, “minimum cost to merge stones” | n ≤ 300 | interval DP | dp § Template 3 | the order of operations does not matter → greedy |
| “assign n ≤ 16 items to k groups”, “visit all nodes” | n ≤ 16–20 | bitmask DP over the used set; with a current node, BFS over (node, mask) | bit_manipulation § 2-3 (assign), shortest_path_comparison § LC 847 (visit all) | n in the thousands → it is not bitmask; look for a greedy or a DP on values |
Backtracking
| Signal in the statement | Constraint cue | Pattern | Card | Looks like it, but is not |
|---|---|---|---|---|
| “all subsets”, “all combinations of k” | n ≤ 10–20 | backtracking with start_idx |
backtrack § Template 3, Template 6 | only the count is asked → DP |
| “all permutations” | n ≤ 8 | backtracking with used[] |
backtrack § Template 5 | the next permutation only → a two-pass scan (LC 31) |
| “combinations summing to target”, reuse allowed or not | candidates ≤ 30 | pass i or i + 1 |
backtrack § Template 7 | order matters and you only count → DP (LC 377) |
| “word search in a grid”, “N-Queens”, “sudoku” | board ≤ 9 × 9 or m·n ≤ 36 | backtracking on a board | backtrack § Template 9, Template 10 | many words in one grid → trie + backtracking (LC 212) |
| “partition the string into palindromes” | n ≤ 16 | backtracking over cut points | backtrack § Template 8 | the minimum number of cuts → DP (LC 132) |
Heaps and greedy
| Signal in the statement | Constraint cue | Pattern | Card | Looks like it, but is not |
|---|---|---|---|---|
| “top k frequent”, “k closest”, “kth largest in a stream” | n ≤ 10⁵ | size-k heap | heap § Template 1 | one shot over a fixed array → quickselect, O(n) average |
| “median of a data stream” | 5 · 10⁴ calls | two heaps | heap § Template 4 | a sliding window median → also delete from the window (monotonic_queue § Template 4) |
| “task scheduler with cooldown”, “reorganize the string so no two are adjacent” | n ≤ 10⁴, 26 kinds | greedy on the most frequent | greedy § Template 2, Template 5 | the order of the input must be kept → a queue simulation |
| “can you reach the end”, “minimum jumps” | n ≤ 10⁴ | greedy farthest reach | greedy § Template 4 | each jump has a cost → DP or Dijkstra |
Stacks and design
| Signal in the statement | Constraint cue | Pattern | Card | Looks like it, but is not |
|---|---|---|---|---|
| “valid parentheses”, “decode string”, “simplify path” | n ≤ 10⁴ | stack of open items | stack § Template 2 (brackets), stack_expression_parsing § 3 (decode string), stack § Template 6 (simplify path) | only one bracket type → a counter is enough |
| “next greater / warmer day”, “stock span” | n ≤ 10⁵ | monotonic stack | stack § Template 3 | max of every window of size k → monotonic deque (LC 239) |
| “largest rectangle in histogram”, “maximal rectangle” | n ≤ 10⁵ | monotonic stack, left and right bounds | monotonic_stack § Template 3 | trapped water → two pointers is simpler (LC 42) |
| “max / min of every window of size k” | n ≤ 10⁵ | monotonic deque | monotonic_queue § Template 1 | a sum, not a max → a plain sliding window |
| “min stack”, “LRU cache”, “O(1) get and put” | O(1) per op | one structure per query, kept in step | stack § Template 4, design § 0-2 | eviction by frequency, not recency → LFU, two maps (LC 460) |
| “range sum with point updates” | n, q ≤ 3 · 10⁴ | Fenwick tree / segment tree | segment_tree § Template 1 | no updates → a prefix sum array |
| “single number”, “count bits”, “subsets as masks” | values fit in 32 bits | bit tricks | bit_manipulation § 1-2 | values unbounded → a hash map |
Before you pick a pattern — the six-step loop
Picking the right pattern is step 3 of six. The five around it are what an interviewer is actually grading, and they are the same for every question on this page. Read this once before your first mock, not during revision.
- Understand the question: requirement, input and output, the accepted form of the answer.
- Ask about scope and limits: the scale of the data and the range of the numbers (this is the constraint cue above), the boundaries, the expected time and space.
- Come up with approaches: say a brute force out loud, then a better one with its algorithm and data structure. Write pseudocode, name the edge cases, and agree on it before coding.
- Write the code: clean, with names that say what they hold, and with test cases written down.
- Run it: walk the tests, fix bugs, state the time and space complexity and the line that sets each.
- Follow-ups: a better bound; input that scales, arrives as a stream, or does not fit in memory.
Drill Path
One anchor problem per family, so a first pass touches every family above. ⭐ marks the L3 core set. Each list runs easy → hard.
- Core ⭐: LC 1 ok Two Sum · LC 20 ok Valid Parentheses · LC 206 again Reverse Linked List · LC 121 ok Best Time to Buy and Sell Stock · LC 3 no verdict Longest Substring Without Repeating Characters · LC 102 ok Level Order Traversal · LC 200 ok Number of Islands · LC 322 again Coin Change · LC 207 ok Course Schedule · LC 78 no verdict Subsets · LC 347 again Top K Frequent Elements · LC 739 ok Daily Temperatures · LC 875 ok Koko Eating Bananas · LC 76 ok Minimum Window Substring
- Practice: LC 167 ok Two Sum II · LC 560 again Subarray Sum Equals K · LC 236 ok Lowest Common Ancestor · LC 994 ok Rotting Oranges · LC 743 again Network Delay Time · LC 416 again Partition Equal Subset Sum · LC 1143 ok Longest Common Subsequence · LC 295 ok Find Median from Data Stream
- Stretch: LC 787 again Cheapest Flights Within K Stops · LC 239 again Sliding Window Maximum · LC 84 again Largest Rectangle in Histogram · LC 212 again Word Search II · LC 312 again Burst Balloons