Chapter Goal: This meta-chapter ties the entire guide together. Pattern recognition is the single most important interview skill — the ability to read a problem statement and immediately know which algorithm, data structure, and technique to apply. This chapter gives you a complete recognition framework: signal words, input type mappings, constraint-based complexity bounds, and a master decision tree. Internalize this and you walk into every interview with a systematic lens, not a blank mind.
When you see a new problem, work through these steps in order before writing any code:
STEP 1 — UNDERSTAND THE OUTPUT TYPE
• Single number (min, max, count, length, boolean) → optimization or counting
• A specific sequence or arrangement → reconstruction
• All valid solutions → backtracking/enumeration
• Yes/No → feasibility check
STEP 2 — UNDERSTAND THE INPUT TYPE
• Array/string (sorted?) → two pointers, binary search, sliding window
• Linked list → fast/slow pointers, reversal
• Tree → BFS (levels) or DFS (paths)
• Graph → BFS/DFS/Dijkstra/Toposort
• Numbers in range [1..n] → cyclic sort, bit tricks
STEP 3 — READ THE CONSTRAINTS
• n ≤ 20 → bitmask DP or backtracking
• n ≤ 300 → O(n³) DP (interval DP)
• n ≤ 10^4 → O(n²) two nested loops
• n ≤ 10^5 → O(n log n) sorting/binary search/heaps
• n ≤ 10^6 → O(n) linear, hashing, two pointers
• n ≤ 10^9 → O(log n) or O(1) math/binary search
STEP 4 — IDENTIFY SIGNAL WORDS
(See pattern sections below for complete signal-word lists)
STEP 5 — PICK 1-2 CANDIDATE PATTERNS
• Sketch the approach in 30 seconds (pseudocode in your head)
• Check: does it handle edge cases? Does complexity match constraints?
STEP 6 — CODE THE CLEANEST APPROACH
Before coding, state your approach in one sentence. If you can't, your understanding is incomplete.
❌ "I'll use dynamic programming somehow..."
✅ "I'll use 0/1 knapsack DP where dp[i][w] is the max value
using first i items with capacity w."
❌ "I'll iterate through the array..."
✅ "I'll use a sliding window expanding when the sum < target
and shrinking when sum ≥ target, tracking the minimum window."
The problem constraints tell you almost exactly which time complexity is expected. Use this table to immediately narrow down your options.
n ≤ 10: O(n!) or O(2^n × n) → full backtracking, TSP brute force
n ≤ 15: O(2^n) → bitmask DP, subset enumeration
n ≤ 20: O(2^n × n) → meet in the middle, bitmask DP
n ≤ 100: O(n³) → Floyd-Warshall, interval DP, 3D DP
n ≤ 500: O(n²) to O(n³) → edit distance, LCS, matrix DP
n ≤ 1000: O(n²) → two nested loops, O(n²) DP, naive LIS
n ≤ 5000: O(n²) → quadratic DP, n² backtracking
n ≤ 10^5: O(n log n) → sort, binary search, segment tree, heaps
n ≤ 10^6: O(n) or O(n log n) → linear scan, sieve, hashing, two pointers
n ≤ 10^7: O(n) → O(n) only (avoid log factors)
n ≤ 10^9: O(log n) or O(√n) → binary search, math, fast power
n = 10^18: O(log n) → binary exponentiation, digit DP
| Complexity | Algorithms |
|---|---|
| O(1) | Math formula, bit trick, hash lookup |
| O(log n) | Binary search, fast power, GCD |
| O(√n) | Trial division, sqrt decomposition |
| O(n) | Linear scan, hashing, two pointers, BFS/DFS |
| O(n log n) | Sorting, merge sort, heap, segment tree |
| O(n log² n) | Divide & conquer with log factor |
| O(n²) | Two nested loops, quadratic DP, naive LIS |
| O(n² log n) | Sorting within O(n²) DP |
| O(n³) | Floyd-Warshall, interval DP, matrix chain |
| O(n × W) | Knapsack DP (W = weight limit) |
| O(2^n × n) | Bitmask DP, TSP |
| O(n!) | Brute-force permutations |
SORTED ARRAY
→ Two pointers (pair/triplet sum)
→ Binary search (find position, range, rotated)
→ Sliding window (if subarray constraint)
UNSORTED ARRAY
→ Sort first, then two pointers / greedy
→ Hash map (frequency, complement lookup)
→ DP (optimal subarray, counting paths)
→ Monotonic stack (next greater element)
ARRAY WITH VALUES IN [1..n]
→ Cyclic sort (find missing/duplicate)
→ Bit manipulation (XOR trick)
LINKED LIST
→ Fast & slow pointers (cycle, middle, nth from end)
→ In-place reversal (reverse, rotate, k-groups)
→ Dummy head trick (simplify edge cases)
BINARY TREE
→ BFS (level order, min depth, zigzag)
→ DFS (path sum, all paths, diameter, LCA)
→ Post-order (bottom-up DP on tree)
GRAPH (general)
→ BFS (shortest unweighted path, bipartite)
→ DFS (cycle detection, connectivity, SCC)
→ Topological sort (DAG, dependencies)
→ Dijkstra (shortest weighted path, non-negative)
→ Bellman-Ford (negative weights)
→ DSU (dynamic connectivity, MST via Kruskal)
STRING
→ Two pointers / sliding window (substring problems)
→ Hashing (anagram, palindrome, substring match)
→ Trie (prefix, autocomplete, XOR)
→ DP (LCS, edit distance, palindrome partition)
INTERVAL/RANGE DATA
→ Sort by start time + greedy merge
→ Sort by end time + greedy selection
→ Min-heap of end times (meeting rooms)
→ Sweep line (count overlaps, events)
STREAM / ONLINE DATA
→ Min/max heap (running median, top-K)
→ Reservoir sampling (random sample)
→ Sliding window (recent K elements)
✅ USE TWO POINTERS WHEN:
• Input is SORTED (or can be sorted) — "sorted array", "sorted list"
• Looking for a PAIR or TRIPLET satisfying a condition
• "In-place" modification of sorted array
• Need to check both ends simultaneously
• Palindrome check on array/string
• Remove duplicates from sorted array
TRIGGER WORDS:
"sorted array", "two sum", "three sum", "pair with target",
"palindrome", "remove duplicates", "container with most water",
"in-place", "no extra space"
❌ NOT two pointers when:
• Unsorted and can't sort
• Need all pairs (use hash map instead)
• Looking for non-contiguous elements
// Variant 1: OPPOSITE DIRECTION (sorted array, pair/triplet)
int l = 0, r = arr.size()-1;
while (l < r) {
if (condition_met(arr[l], arr[r])) { /* found! */ l++; r--; }
else if (need_larger(arr[l], arr[r])) l++;
else r--;
}
// Variant 2: SAME DIRECTION — Read/Write (in-place filter)
int write = 0;
for (int read = 0; read < arr.size(); read++) {
if (keep(arr[read])) arr[write++] = arr[read];
}
// write = new length
// Variant 3: FAST/SLOW (cycle detection, nth from end)
int slow = 0, fast = 0;
while (fast < n && fast+1 < n) {
slow++;
fast += 2;
}| Problem | Variant | Key Logic |
|---|---|---|
| Two Sum (sorted) | Opposite | if sum==target: found; if sum<target: l++; else r-- |
| 3Sum | Opposite (inner) | Fix one, two-pointer on rest |
| Remove Duplicates | Read/Write | Write only when arr[read] != arr[write-1] |
| Palindrome Check | Opposite | Compare arr[l] and arr[r], move inward |
| Container With Most Water | Opposite | Move the shorter side inward |
✅ USE SLIDING WINDOW WHEN:
• Looking for optimal (max/min length) CONTIGUOUS subarray or substring
• "Subarray with sum ≥ k" or "at most k distinct chars"
• Window with a constraint that relaxes/tightens as window grows/shrinks
TRIGGER WORDS:
"subarray", "substring", "contiguous", "window of size k",
"maximum sum", "minimum length", "longest", "shortest",
"at most k distinct", "all characters appear"
❌ NOT sliding window when:
• Non-contiguous elements (use DP or hash map)
• Need to check all pairs (O(n²))
• Order doesn't matter
// Template A: FIXED SIZE window of exactly k
int windowSum = 0;
for (int i = 0; i < k; i++) windowSum += arr[i];
int maxSum = windowSum;
for (int i = k; i < arr.size(); i++) {
windowSum += arr[i] - arr[i-k]; // Slide: add new, remove old
maxSum = max(maxSum, windowSum);
}
// Template B: VARIABLE SIZE — maximize window (Pattern Max)
int l = 0, result = 0;
// state = some accumulator (sum, freq map, count)
for (int r = 0; r < arr.size(); r++) {
add(arr[r], state); // Expand right
while (invalid(state)) { // Shrink left until valid
remove(arr[l], state); l++;
}
result = max(result, r - l + 1); // Record best valid window
}
// Template C: VARIABLE SIZE — minimize window (Pattern Min)
int l = 0, result = INT_MAX;
for (int r = 0; r < arr.size(); r++) {
add(arr[r], state);
while (valid(state)) { // Shrink while still valid
result = min(result, r - l + 1);
remove(arr[l], state); l++;
}
}| Problem | Template | State | Result |
|---|---|---|---|
| Max sum subarray of size k | Fixed | running sum | max sum |
| Longest substring without repeat | Max | freq map | max window size |
| Minimum window substring | Min | char coverage count | min window size |
| Longest substring with ≤ k distinct chars | Max | distinct count | max window size |
| Permutation in string | Fixed | sorted/freq counts | boolean |
✅ USE FAST/SLOW POINTERS WHEN:
• Cycle detection in linked list or array (Floyd's algorithm)
• Finding the MIDDLE of a linked list
• Finding the n-th node from the END
• Detecting if a number is "happy" (cycle in number sequence)
• Palindrome check on a linked list (split + reverse half)
TRIGGER WORDS:
"cycle in linked list", "loop", "circular", "happy number",
"middle of list", "nth from end", "palindrome linked list"
❌ NOT fast/slow when:
• No cyclic structure to detect
• Random access array (just use indices)
// Floyd's Cycle Detection — Phase 1: Detect cycle
ListNode* slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) break; // Cycle detected
}
// Phase 2: Find cycle entry (if cycle exists)
slow = head;
while (slow != fast) { slow = slow->next; fast = fast->next; }
// slow == fast == cycle entry
// Finding middle:
slow = head; fast = head;
while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
// slow = middle (second middle for even-length)✅ USE MERGE INTERVALS WHEN:
• Input is a list of intervals/ranges
• Need to find overlap, merge, or schedule
• "Meetings that can't overlap", "available times", "events"
TRIGGER WORDS:
"intervals", "meetings", "overlapping", "ranges", "schedule",
"insert interval", "merge", "coverage", "meeting rooms"
SORT CRITERION:
• Merge overlapping → sort by START time
• Maximum non-overlapping (greedy) → sort by END time
• Meeting rooms (min rooms) → sort by START, heap of end times
"Merge all overlapping intervals" → sort by start, extend end greedily
"Remove minimum to make non-overlapping" → sort by end, count overlapping removed
"Minimum meeting rooms needed" → sort by start, min-heap of end times
"Insert new interval into sorted list" → binary search + merge neighbors
"Find all overlapping pairs" → sweep line with events
✅ USE CYCLIC SORT WHEN:
• Array contains numbers in range [1..n] or [0..n]
• Need to find MISSING numbers or DUPLICATES
• "In-place" with O(1) extra space
• n+1 numbers in [1..n] (duplicate guaranteed)
TRIGGER WORDS:
"missing number", "find all missing", "find duplicate", "numbers 1 to n",
"array contains n elements in range [1..n]", "find all duplicates"
Template:
While i < n: if nums[i] is in correct position (nums[i]-1 == i): i++
else if nums[nums[i]-1] == nums[i]: duplicate found, i++
else: swap(nums[i], nums[nums[i]-1])
Then scan: nums[i] != i+1 → i+1 is missing
✅ USE TREE BFS WHEN:
• Level-by-level processing required
• MINIMUM depth or shortest path from root
• "Zigzag level order", "right side view", "average per level"
• "Closest to root" conditions
TRIGGER WORDS:
"level order", "level by level", "minimum depth", "right/left side view",
"average of levels", "zigzag", "cousins", "closest ancestor"
✅ USE TREE DFS WHEN:
• Processing PATH from root to leaf
• ALL paths with a condition (path sum, path max)
• Height, diameter, balance check
• LCA (Lowest Common Ancestor)
• Serialize/deserialize
• ANY post-order bottom-up computation
TRIGGER WORDS:
"path sum", "all paths", "root to leaf", "any path", "diameter",
"height", "balanced", "LCA", "serialize", "validate BST",
"ancestor", "maximum path"
DFS VARIANT CHOICE:
Pre-order → build/serialize, copy tree
In-order → BST operations (sorted order)
Post-order → height, diameter, delete, bottom-up DP
// When DFS needs to both ANSWER A QUERY and PROPAGATE UPWARD:
// Return two values (pair/struct)
pair<int,int> dfs(TreeNode* node) {
if (!node) return {baseCase1, baseCase2};
auto [l1, l2] = dfs(node->left);
auto [r1, r2] = dfs(node->right);
int answerHere = /* use l1, l2, r1, r2, node->val */;
updateGlobal(answerHere);
int propagateUp = /* what parent needs */;
return {propagateUp, /* second value */};
}
// Used in: diameter, max path sum, LCA, House Robber III✅ USE TWO HEAPS WHEN:
• Need the MEDIAN of a stream (or sliding window)
• Partition elements into two halves dynamically
• "Smallest from the larger half" or "largest from the smaller half"
• Scheduling where you need both min and max simultaneously
TRIGGER WORDS:
"median", "stream of numbers", "running median", "sliding window median",
"find median from data stream"
STRUCTURE:
maxHeap → smaller half (top = largest of small half)
minHeap → larger half (top = smallest of large half)
Invariant: maxHeap.size() == minHeap.size() ± 1
Median: maxHeap.top() if sizes differ, avg(tops) if equal
✅ USE BACKTRACKING WHEN:
• Need to enumerate ALL valid solutions (not just count)
• "Generate all...", "find all combinations/permutations/subsets"
• Constraint satisfaction with choices at each step
• n is small (n ≤ 20 for 2^n, n ≤ 8 for n!)
TRIGGER WORDS:
"all combinations", "all permutations", "all subsets", "power set",
"generate all", "find all paths", "N-Queens", "Sudoku",
"phone letter combinations"
CHOOSE BACKTRACKING VARIANT:
Subsets: start index advances, include at every level
Permutations: used[] array, start from 0 each level
Combinations: start index advances, only when curr.size()==k
With dupes: sort first + skip same value at same recursion level
NOT backtracking → count only (use DP instead)
✅ USE BINARY SEARCH WHEN:
• Sorted array or monotone condition
• "Find position", "search for target"
• "Minimum X such that condition holds"
• "Maximum X such that condition holds"
• Rotated sorted array
TRIGGER WORDS:
"sorted", "find position", "search", "minimum capacity",
"minimum speed", "split into k groups minimize maximum",
"find peak", "rotated sorted array"
VARIANT SELECTION:
Exact value search → Template A (while lo<=hi, hi=mid-1 or lo=mid+1)
First/last position → Template B (while lo<hi, hi=mid or lo=mid+1)
Minimize answer → Template M1 (if feasible: hi=mid; else: lo=mid+1)
Maximize answer → Template M2 (round up mid; if feasible: lo=mid; else: hi=mid-1)
2D matrix → flatten: matrix[mid/cols][mid%cols]
Non-sorted (peak) → local monotone: if arr[mid]<arr[mid+1], peak is right
✅ USE TOP-K (HEAP) WHEN:
• Find K LARGEST or K SMALLEST elements
• K most/least frequent elements
• K closest points
• Online stream where you can't store all elements
WHICH HEAP TO USE:
K largest → MIN-heap of size k (pop smallest when overflow → top = k-th largest)
K smallest → MAX-heap of size k (pop largest when overflow → top = k-th smallest)
K-th element alone → quickselect O(n) average, or nth_element STL
COMPLEXITY: O(n log k) — better than O(n log n) when k << n
✅ USE K-WAY MERGE WHEN:
• Given K sorted arrays/lists, need to merge or find elements in order
• "Smallest range covering K lists"
• "K-th smallest in K sorted arrays"
STRUCTURE:
Min-heap of size K: each entry = {value, list_index, element_index}
Extract min, push next element from same list
Time: O(n log k) where n = total elements
SHORTEST PATH:
Unweighted graph → BFS (O(V+E))
Non-negative weights → Dijkstra (O((V+E) log V))
Negative weights → Bellman-Ford (O(VE))
All pairs + small V → Floyd-Warshall (O(V³))
Binary weights (0/1) → 0-1 BFS with deque (O(V+E))
CONNECTIVITY:
Static connectivity → DFS/BFS component labeling
Dynamic (add edges) → DSU with path compression
Directed strong components → Kosaraju's 2-pass DFS
CYCLE DETECTION:
Undirected → DFS with parent tracking
Directed → 3-color DFS (white/gray/black)
ORDERING:
DAG ordering → Topological sort (Kahn's BFS or DFS post-order)
"Prerequisites" or "dependencies" → ALWAYS topological sort
MINIMUM SPANNING TREE:
Sparse graph → Kruskal's (O(E log E))
Dense graph → Prim's (O(E log V) or O(V²))
TRIGGER WORDS FOR GRAPH DETECTION:
"network", "connections", "paths between nodes",
"dependencies", "prerequisites", "courses", "schedule",
"islands", "components", "provinces", "friends", "accounts"
RECOGNIZE DP WHEN:
• "Minimum/maximum" + optimal substructure
• "Count number of ways" + overlapping subproblems
• "Is it possible" + yes/no with subproblem breakdown
• The answer to the problem depends on answers to smaller versions
CHOOSE THE DP PATTERN:
1D DP (State = position):
dp[i] = answer for first i elements
→ Fibonacci, Climbing Stairs, House Robber, Decode Ways
→ "Can we reach...", "Count ways to reach..."
2D DP (Two sequences or grid):
dp[i][j] = answer for s[0..i-1] and t[0..j-1], or grid cell (i,j)
→ LCS, Edit Distance, Unique Paths, Min Path Sum
0/1 Knapsack (Select subset):
dp[i][w] = answer using first i items with capacity w
→ REVERSE inner loop, each item used at most once
→ "Partition equal subset", "Target sum", "Can we select..."
Unbounded Knapsack (Reuse items):
→ FORWARD inner loop, each item can be reused
→ Coin Change, Coin Change II, Combination Sum
String DP (Two strings):
dp[i][j] with s[i-1]==t[j-1] or not matching
→ LCS, Edit Distance, Wildcard Matching, Regex
Interval DP (Range subproblem):
dp[l][r] = answer for range [l,r]
Fill by INCREASING LENGTH
→ Burst Balloons, Matrix Chain, Palindrome Partitioning
Tree DP (Bottom-up on tree):
DFS returns pair {include_root, exclude_root}
→ House Robber III, Max Path Sum, Diameter
Bitmask DP (Subset state):
dp[mask][last] = answer for subset mask ending at last
→ TSP, Assignment, Shortest Superstring
State Machine DP (Discrete states):
States = hold/free/cooldown/etc.
→ All stock buy/sell variants
LIS-type (Sequence building):
dp[i] = length of best sequence ending at i
→ LIS, Russian Doll Envelopes, Box Stacking
WHEN TO AVOID DP:
→ All solutions needed (use backtracking)
→ Greedy provably correct (exchange argument holds)
→ No overlapping subproblems (use D&C)
SORT + TWO POINTERS
"3Sum", "4Sum", "Closest 3Sum"
Sort array, fix outer elements, inner two-pointer
SORT + GREEDY
"Non-overlapping intervals", "Meeting rooms", "Minimum arrows"
Sort by end time, greedily pick
BINARY SEARCH ON ANSWER + GREEDY FEASIBILITY CHECK
"Koko eating bananas", "Ship packages in D days", "Split array"
Binary search on answer space, check with O(n) greedy scan
PREFIX SUM + HASH MAP
"Subarray sum equals k", "Continuous subarray sum"
Build prefix sums, store in map, check complement
TRIE + DFS/BACKTRACKING
"Word Search II", "Concatenated Words"
Build trie, DFS grid using trie for pruning
HEAP + SLIDING WINDOW
"Sliding window maximum" (use deque/monotonic)
"Sliding window median" (two heaps)
GRAPH + DP (DP on DAG)
"Longest path in DAG", "Number of ways in grid with obstacles"
Topological order, then DP in that order
BIT MANIPULATION + DP
"Bitmask DP" (TSP, covering all items)
State = bitmask of items processed
MONOTONIC STACK + ARRAY
"Largest rectangle in histogram", "Next greater element"
Maintain stack of increasing or decreasing elements
BINARY SEARCH + SEGMENT TREE
"Count of range sum", "Find k-th smallest in BST"
Coordinate compress, then binary search on segment tree
START: Read the problem
│
├─ OUTPUT TYPE
│ ├─ Single value (min/max/count/bool)?
│ │ └─ Proceed to step 2
│ ├─ A specific arrangement/sequence?
│ │ └─ Greedy / Reconstruction
│ └─ ALL valid solutions?
│ └─ BACKTRACKING
│
├─ INPUT TYPE
│ ├─ ARRAY (sorted)?
│ │ ├─ Find pair/triplet → TWO POINTERS
│ │ ├─ Find subarray → SLIDING WINDOW or PREFIX SUM
│ │ ├─ Find position → BINARY SEARCH
│ │ └─ Find k-th element → QUICKSELECT or HEAP
│ │
│ ├─ ARRAY (unsorted)?
│ │ ├─ Values in [1..n] → CYCLIC SORT or BIT TRICK (XOR)
│ │ ├─ Max/min subarray → KADANE'S (DP) or SLIDING WINDOW
│ │ ├─ Count subarrays with property → PREFIX SUM + HASH MAP
│ │ ├─ Optimal selection → DP (knapsack family)
│ │ └─ Sort first? → See sorted array
│ │
│ ├─ LINKED LIST?
│ │ ├─ Cycle? Middle? → FAST/SLOW POINTERS
│ │ └─ Reverse? Rotate? → IN-PLACE REVERSAL
│ │
│ ├─ TREE?
│ │ ├─ Level-by-level / min depth → BFS
│ │ ├─ Path / all paths / diameter → DFS
│ │ └─ BST operations → INORDER (= sorted)
│ │
│ ├─ GRAPH?
│ │ ├─ Shortest path, unweighted → BFS
│ │ ├─ Shortest path, weighted (non-neg) → DIJKSTRA
│ │ ├─ Shortest path, negative weights → BELLMAN-FORD
│ │ ├─ All pairs shortest path → FLOYD-WARSHALL
│ │ ├─ Ordering / dependencies → TOPOLOGICAL SORT
│ │ ├─ Connectivity (dynamic) → DSU
│ │ └─ Minimum spanning tree → KRUSKAL / PRIM
│ │
│ ├─ INTERVALS?
│ │ ├─ Merge overlapping → SORT by start + GREEDY
│ │ ├─ Max non-overlapping → SORT by end + GREEDY
│ │ └─ Min meeting rooms → SORT + MIN-HEAP
│ │
│ └─ STRING?
│ ├─ Substring / subarray → SLIDING WINDOW
│ ├─ Anagram / frequency → HASH MAP
│ ├─ Prefix match → TRIE
│ └─ Two strings (LCS, edit) → 2D DP
│
└─ CONSTRAINT CHECK (confirm complexity)
n≤20 → bitmask / backtracking
n≤1000 → O(n²) DP
n≤10^5 → O(n log n)
n≤10^6 → O(n) linear
n≤10^9 → O(log n) math
| Signal Words | Pattern |
|---|---|
| "sorted array", "pair/triplet with sum", "palindrome" | Two Pointers |
| "subarray/substring", "contiguous", "window of k", "longest/shortest" | Sliding Window |
| "cycle", "loop", "middle of list", "nth from end" | Fast & Slow |
| "intervals", "meetings", "overlap", "schedule" | Merge Intervals |
| "missing number", "numbers in [1..n]", "find duplicate" | Cyclic Sort |
| "level order", "minimum depth", "zigzag" | Tree BFS |
| "path sum", "all paths", "diameter", "LCA", "validate BST" | Tree DFS |
| "median of stream", "running median" | Two Heaps |
| "all combinations", "all permutations", "generate all" | Backtracking |
| "sorted + find position", "minimum X satisfying condition" | Binary Search |
| "K largest/smallest", "K most frequent" | Top-K (Heap) |
| "K sorted arrays/lists", "k-way merge" | K-way Merge |
| "dependencies", "prerequisites", "build order", "course schedule" | Topological Sort |
| "minimum/maximum ways", "count paths", "is it possible" | Dynamic Programming |
| "next greater element", "largest rectangle", "stock prices" | Monotonic Stack |
| "XOR", "single number", "missing in [1..n]", "flip bits" | Bit Manipulation |
| "nCr", "permutations count", "Catalan", "modular" | Math / Combinatorics |
The following problems are curated to test your pattern recognition across all categories. For each, identify the pattern BEFORE looking at the solution.
| # | Problem | Difficulty | Pattern to Identify | Link |
|---|---|---|---|---|
| 1 | Trapping Rain Water | Hard | Two pointers / Monotonic stack | LC 42 |
| 2 | Minimum Window Substring | Hard | Sliding window (Pattern Min) | LC 76 |
| 3 | Serialize and Deserialize Binary Tree | Hard | Tree BFS or DFS | LC 297 |
| 4 | Largest Rectangle in Histogram | Hard | Monotonic stack | LC 84 |
| 5 | Median of Two Sorted Arrays | Hard | Binary search on partition | LC 4 |
| 6 | Word Ladder | Hard | BFS on implicit graph | LC 127 |
| 7 | Course Schedule II | Medium | Topological sort (Kahn's) | LC 210 |
| 8 | Alien Dictionary | Hard | Build graph + topological sort | LC 269 |
The real practice: For each problem above, spend 3-5 minutes reading only the problem statement (no solution), then write down: (1) the pattern you believe applies, (2) your one-sentence approach, (3) the expected time complexity. Then verify by reading the solution. Track your pattern recognition accuracy — aim for ≥ 80% correct identification within 5 minutes of reading.