Pattern 18 · Meta
Pattern Recognition
The hard part of an interview is not implementing the solution — it's knowing which pattern the problem is asking for. This is the routing table: a systematic decision framework of signals, constraints, and traps so you never freeze at the whiteboard.
patterns 18 mappedsignal rows 20flowcharts 4drill 20 problems
01 core concept
Recognition is the real skill
You can drill seventeen implementations to muscle memory and still lose the interview in the first five minutes — by picking the wrong one. Recognition is a separate skill, and it can be practiced separately: read problems and name the pattern without coding.
The question this page answers
“I know how to code a sliding window… but how do I know
this problem needs a sliding window?”
The master decision tree
Start from the primary data structure and walk down. Each branch is one question.
START: Read the problem. What is the PRIMARY data structure?
|
+---> ARRAY / STRING
| |
| +-- Is it sorted (or can we sort)?
| | YES --> Two Pointers or Binary Search
| |
| +-- Contiguous subarray/substring?
| | YES --> Sliding Window or Prefix Sum
| |
| +-- Intervals (start, end)?
| | YES --> Sort + Merge Intervals
| |
| +-- Top K / Kth largest?
| | YES --> Heap (or Quickselect)
| |
| +-- Next greater / smaller element?
| | YES --> Monotonic Stack
| |
| +-- All subsets / permutations / combinations?
| | YES --> Backtracking
| |
| +-- Optimization + overlapping subproblems?
| | YES --> Dynamic Programming
| |
| +-- Missing/duplicate number in range [1,n]?
| | YES --> Cyclic Sort or Math
| |
| +-- Counting / grouping / frequency?
| YES --> Hash Map
|
+---> LINKED LIST
| |
| +-- Cycle? Middle? Nth from end?
| | YES --> Fast & Slow Pointers
| |
| +-- Reverse / reorder / merge two?
| | YES --> In-place Linked List manipulation
| |
| +-- Merge K sorted lists?
| YES --> Heap (min-heap of list heads)
|
+---> TREE
| |
| +-- Level-by-level processing?
| | YES --> BFS (level-order traversal)
| |
| +-- Path / validate BST / LCA?
| | YES --> DFS (recursion)
| |
| +-- BST search / insert / delete?
| YES --> Binary Search logic on tree
|
+---> GRAPH
| |
| +-- Shortest path (unweighted)?
| | YES --> BFS
| |
| +-- Shortest path (weighted)?
| | YES --> Dijkstra's
| |
| +-- Connectivity / components?
| | YES --> Union-Find or DFS
| |
| +-- Dependencies / ordering?
| | YES --> Topological Sort (Kahn's BFS or DFS)
| |
| +-- All paths / cycle detection?
| YES --> DFS with backtracking
|
+---> STRING (special cases)
|
+-- Prefix matching / autocomplete?
| YES --> Trie
|
+-- Brackets / nesting / matching?
| YES --> Stack
|
+-- Pattern with choices / regex-like?
YES --> Backtracking or DP
02 signal table
Keyword → pattern
Problems telegraph their pattern through specific words. This table maps the signals you'll actually read to the pattern you should reach for — the last column links to the guide that covers it.
| Signal / keyword | Pattern | Time | Guide |
|---|---|---|---|
| “sorted array”, “find target” | Binary Search | O(log n) | 06 |
| “two numbers that sum to” | Two Pointers / Map | O(n) | 01, 02 |
| “longest/shortest substring with…” | Sliding Window | O(n) | 05 |
| “subarray sum equals k” | Prefix Sum + Map | O(n) | 09 |
| “merge overlapping intervals” | Sort + Sweep | O(n log n) | 13 |
| “top k”, “kth largest/smallest” | Heap | O(n log k) | 12 |
| “next greater element” | Monotonic Stack | O(n) | 14 |
| “all combinations/subsets/permutations” | Backtracking | O(2ⁿ) or O(n!) | 11 |
| “minimum cost”, “maximum profit”, “ways” | Dynamic Programming | varies | 07 |
| “connected components”, “union” | Union-Find | O(n · α(n)) | 17 |
| “course schedule”, “build order” | Topological Sort | O(V + E) | 03 |
| “shortest path”, “minimum steps” | BFS | O(V + E) | 04 |
| “word search”, “prefix”, “autocomplete” | Trie | O(m) | 16 |
| “valid parentheses”, “calculator” | Stack | O(n) | 01 |
| “linked list cycle”, “middle node” | Fast & Slow Pointers | O(n) | 15 |
| “matrix”, “grid”, “island” | BFS/DFS on grid | O(R · C) | 03, 04 |
| “meeting rooms”, “min platforms” | Sort + Heap/Sweep | O(n log n) | 12, 13 |
| “palindrome” | Two Pointers or DP | O(n) or O(n²) | 02, 07 |
| “LRU Cache” | HashMap + DLL | O(1) | special |
| “design”, “implement” | Multiple DS combined | varies | varies |
When NOT to trust the first signal
Signals can bait you. “Contiguous + sum” says sliding window — but negative numbers
silently break it. “Shortest path” says BFS — but weighted edges demand Dijkstra's.
Always cross-check the signal against the data's properties before committing;
section 05 lists the classic bait-and-switches.
03 constraints
The constraints tell you the algorithm
The second signal is numeric. The size of n tells you what complexity the
problem-setter expects — which shortlists the patterns that can deliver it.
| Constraint | Expected complexity |
|---|---|
| n ≤ 10 | O(n!) — brute force / backtracking |
| n ≤ 20 | O(2ⁿ) — bitmask / backtracking |
| n ≤ 100 | O(n³) — triple loop / DP |
| n ≤ 1,000 | O(n²) — DP / nested loop |
| n ≤ 10,000 | O(n · √n) |
| n ≤ 100,000 | O(n log n) — sort / heap |
| n ≤ 1,000,000 | O(n) — linear scan |
| n ≤ 10⁹ | O(log n) — binary search |
Use it both ways
Stuck with no idea? The constraint narrows the field (n ≤ 20 practically shouts
backtracking or bitmask). Have a candidate solution? The constraint sanity-checks it
before you invest ten minutes coding an O(n²) answer that can't pass.
04 worked example
Classifying a problem, live
Here's the framework applied to a real statement — the single most-missed classification in the trap table. Read the signals, put the candidates on the board, and eliminate until one survives.
step 1 / 8walkthrough — which pattern is “subarray sum equals k”?
goal count
n ≤ 2·10⁴
The problem (LC 560): “Given an integer array nums — which may contain negative numbers — and an integer k, count the contiguous subarrays whose sum equals exactly k.” Six candidate patterns on the board. Start eliminating.
05 common traps
“Obvious but wrong” pattern choices
These are the problems where the loudest signal points at the wrong pattern. Learn the table, then the four biggest offenders in detail.
| Problem description | Tempting | Correct | Why |
|---|---|---|---|
| “Find if path exists” in weighted graph | BFS | Dijkstra's | BFS doesn't handle weights |
| “Longest substring without repeating” | Two pointers | Sliding Window | Need to shrink window dynamically |
| “Subarray sum = k” (with negatives) | Sliding Window | Prefix Sum + HashMap | Window can't shrink with negatives |
| “Number of islands” (follow-up: dynamic) | DFS | Union-Find | Dynamic additions need incremental updates |
| “Word break” (can string be segmented?) | Greedy / Trie only | DP | Greedy fails: “catsanddog” |
| “Jump Game II” (minimum jumps) | DFS / Backtracking | Greedy / BFS | BFS by levels gives min jumps |
| “Valid parentheses” with multiple types | Counter | Stack | Counter can't track ordering |
| “Merge k sorted lists” | Merge one by one | Min Heap | One-by-one is O(nk), heap O(n log k) |
| “Course schedule” (can finish all?) | BFS on adj list | Topological Sort | Need to detect cycles in DAG |
Mistake 1 — sliding window on negative numbers
Window-shrinking logic assumes adding an element makes the sum bigger. Negatives break
that monotonicity, so the window can't decide when to shrink. Sum-equals-k with negatives is
Prefix Sum + HashMap; maximum subarray sum is Kadane's (DP).
Mistake 2 — BFS on a weighted graph
BFS finds the path with the fewest edges, not the lowest total weight.
The moment edges carry weights, shortest path means Dijkstra's
(or Bellman-Ford if weights can be negative).
Mistake 3 — greedy segmentation for Word Break
Greedily matching the longest (or first) dictionary word fails on inputs like
"catsanddog" — committing to "cats" vs "cat" changes what's
reachable later. Overlapping subproblems + a yes/no over prefixes = DP.
Mistake 4 — counting brackets instead of stacking them
A counter proves the totals balance, not the order: "([)]" has matched
counts but invalid nesting. Multiple bracket types need a stack.
06 flowcharts
Decision flowcharts for the crowded cases
Three problem families where several patterns plausibly apply. Walk the chart instead of guessing.
F1Subarray problems
SUBARRAY PROBLEM?
|
+-- Does the array have NEGATIVE numbers?
| |
| YES --> Can NOT use sliding window for sum problems
| | |
| | +-- "Sum equals k" --> Prefix Sum + HashMap
| | +-- "Maximum subarray sum" --> Kadane's (DP)
| |
| NO (all positive)
| |
| +-- "Sum equals k" or "sum >= k" --> Sliding Window
| +-- "Longest with at most k distinct" --> Sliding Window
|
+-- Is it about PRODUCT, not sum?
| YES --> Track prefix products, handle zeros separately
|
+-- Fixed-size window?
YES --> Basic Sliding Window (no shrinking needed)
F2Graph problems
GRAPH PROBLEM?
|
+-- Is it a TREE (n nodes, n-1 edges, connected)?
| YES --> DFS/BFS (no cycle handling needed)
|
+-- Do edges have WEIGHTS?
| |
| YES --> Shortest path? --> Dijkstra's (no negative weights)
| | --> Bellman-Ford (negative weights OK)
| NO
| |
| +-- "Shortest path" / "Minimum steps" --> BFS
| +-- "All paths" / "Does path exist" --> DFS
| +-- "Connected components" --> Union-Find or DFS
| +-- "Order of tasks" --> Topological Sort
| +-- "Bipartite check" --> BFS/DFS with coloring
|
+-- Is the graph DIRECTED?
|
YES --> Cycle detection: DFS with 3-color (white/gray/black)
NO --> Cycle detection: Union-Find
F3DP problems
IS THIS A DP PROBLEM?
|
Ask: "Can I break this into overlapping subproblems?"
Ask: "Does optimal solution contain optimal sub-solutions?"
|
YES to both --> DP
|
WHAT TYPE?
|
+-- Single sequence (array/string)?
| dp[i] = answer considering first i elements
| Examples: Climbing Stairs, House Robber, LIS
|
+-- Two sequences?
| dp[i][j] = answer for first i of seq1, first j of seq2
| Examples: LCS, Edit Distance, Interleaving String
|
+-- Grid?
| dp[r][c] = answer to reach cell (r,c)
| Examples: Unique Paths, Min Path Sum
|
+-- Knapsack variant?
| dp[i][w] = best using first i items with capacity w
| Examples: 0/1 Knapsack, Coin Change, Partition Equal Subset
|
+-- Interval?
dp[i][j] = answer for subarray/substring from i to j
Examples: Burst Balloons, Palindrome Partitioning
07 quick reference
The one-glance card
Every pattern, its key signal, and its cost. This is the table to be able to reproduce from memory.
| Pattern | Key signal | Time | Space |
|---|---|---|---|
| Hash Map | Count / lookup / group | O(n) | O(n) |
| Two Pointers | Sorted + pair/triplet | O(n) | O(1) |
| Sliding Window | Contiguous + constraint | O(n) | O(k) |
| Prefix Sum | Range sum / subarray sum | O(n) | O(n) |
| Binary Search | Sorted + find target | O(log n) | O(1) |
| Merge Intervals | Overlapping intervals | O(n log n) | O(n) |
| DFS/BFS (graph/tree) | Traversal / shortest | O(V+E) | O(V) |
| Topological Sort | Dependencies / ordering | O(V+E) | O(V+E) |
| Heap | Top K / merge K sorted | O(n log k) | O(k) |
| Monotonic Stack | Next greater/smaller | O(n) | O(n) |
| Backtracking | All combos / subsets | O(2ⁿ) | O(n) |
| DP | Optimize + subproblems | varies | varies |
| Trie | Prefix search / words | O(m) | O(n·m) |
| Union-Find | Connectivity / groups | O(α(n)) | O(n) |
| Fast & Slow Pointers | Cycle / middle / nth | O(n) | O(1) |
Multi-pattern problems
Some problems admit several valid approaches — knowing the alternatives lets you pick the one you code fastest, and gives you a follow-up answer when the interviewer asks “any other way?”
| Problem | Valid approaches |
|---|---|
| Number of Islands | DFS, BFS, Union-Find |
| Longest Consecutive Sequence | Hash Set, Union-Find |
| Course Schedule | BFS (Kahn's), DFS |
| Word Break | DP, BFS, Trie + DP |
| Kth Largest Element | Heap, Quickselect |
| Palindrome Partitioning | Backtracking, DP |
| House Robber | DP array, DP variables |
08 interview strategy
The 35-minute game plan
Recognition happens in the first ten minutes — protect that time. Do not start coding early, and do not go silent.
0 min 5 min 10 min 30 min 35 min
| | | | |
| UNDERSTAND & PATTERN | DISCUSS | IMPLEMENT | TEST |
| - Read carefully | - State | - Write clean code | - Walk |
| - Ask clarifications | pattern | - Handle edge cases | thru |
| - Identify pattern | - Get OK | - Talk while coding | ex |
| - Think of edge cases | - Pseudo | - Don't optimize early | - Edge |
|________________________|____________|_________________________|__________|
KEY RULES:
* Do NOT start coding before minute 10
* Do NOT stay silent for more than 30 seconds
* If stuck at minute 15, say: "I'm considering X and Y approaches..."
* At minute 25, if not done: simplify, get brute force working first
If you're stuck
- Talk through examples out loud.
- Think about brute force first — what would O(n²) look like?
- Ask: “What data structure gives me the lookup I need?”
- Ask: “Have I seen a similar problem?” — map it to a known pattern.
- Look at the constraints for the complexity hint (section 03).
- Ask the interviewer: “Would it help if I sorted the input first?”
Final advice
Practice recognition separately from coding — read problems and just name the pattern.
Build muscle memory so implementation is automatic once the pattern is named.
When in doubt, start with brute force and optimize away the redundant work.
Communicate constantly — the thought process matters more than perfect code.
And always check the edge cases: empty input, single element, all same elements,
already sorted, duplicates.
10 practice
Practice ladder
In this order — easiest first. Tick each one as you solve it, and re-solve anything that took more than 25 minutes two days later.
20 problems