Pattern Recognition Cheat Sheet
Map 15 common problem signals (sorted array, need all combos, maximise value with constraint, etc.) to the algorithm patterns that solve them fastest.
Pattern Recognition Cheat Sheet is a free DSA Interview Prep lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
The 60-Second Pattern Recognition Game
In a real interview, you have roughly 60 seconds after reading a problem to identify which algorithmic pattern applies before the interviewer expects you to start coding. This is the most important skill to develop — not memorising implementations, but recognising which tool to reach for.
Pattern recognition comes from mapping problem signals (words and constraints in the problem statement) to known algorithm families. Once you identify the pattern, the implementation becomes a template-filling exercise. This lesson is a systematic cheat sheet of the 15 most common problem signals and their corresponding patterns.
# The recognition process
recognition_steps = [
'1. Read the problem once fully (do not start coding)',
'2. Identify the data structure: array, string, tree, graph, matrix?',
'3. Identify the ask: find min/max, count ways, enumerate, detect cycle...?',
'4. Note the constraint: n<=20 (bitmask), sorted (binary search), DAG (topo sort)?',
'5. Map signal -> pattern',
'6. State the pattern and complexity to the interviewer before coding',
'7. Handle edge cases mentally before writing',
]
for step in recognition_steps:
print(step)Signal 1-3: Array and String Patterns
The most frequent problem signals for arrays and strings:
- Sorted array + find target → Binary search O(log n)
- Find pair/triplet summing to target → Two pointers O(n) if sorted, hash map O(n) if unsorted
- Longest/shortest subarray/substring satisfying condition → Sliding window O(n)
- Contiguous subarray max/min sum → Kadane's algorithm O(n)
- Duplicate detection → Hash set O(n) or sort O(n log n)
If the array is sorted, always consider binary search first. Unsorted + target sum + O(n) = almost always a hash map for the complement lookup.
# Quick recognition: array/string signals
signals = [
('Sorted array, find element', 'Binary search O(log n)'),
('Find two elements summing to K', 'Sort+two-ptr O(n log n) or hash O(n)'),
('Longest subarray with property P', 'Sliding window (variable size) O(n)'),
('Max sum contiguous subarray', 'Kadane algorithm O(n)'),
('Anagram/permutation check', 'Frequency map (Counter) O(n)'),
('Contains duplicate', 'Hash set O(n)'),
('Merge two sorted arrays/lists', 'Two pointers O(n+m)'),
('Rotate / shift array', 'Reverse trick O(n) in-place'),
('Next permutation', 'Find rightmost ascent + swap + reverse'),
('Maximum product subarray', 'Track max and min (handles negatives)'),
]
for signal, pattern in signals:
print(f'{signal:45s} => {pattern}')Signal 4-6: Tree and Graph Patterns
Tree and graph problem signals and their patterns:
- Level-by-level traversal / shortest path in unweighted graph → BFS with deque O(V+E)
- Explore all paths / cycle detection / DFS order → DFS recursive or iterative O(V+E)
- BST + in-order properties (kth element, sorted order) → In-order DFS O(n)
- Lowest common ancestor → Recursive descent with path tracking O(n)
- Connected components / union two groups → DSU O(n × alpha(n))
# Tree/graph signal recognition
tree_graph_signals = [
('Level-order / minimum depth / word ladder', 'BFS with deque'),
('All paths / path sum / all permutations tree', 'DFS recursive'),
('Cycle detection (undirected)', 'DFS with parent / DSU'),
('Cycle detection (directed) / course schedule', 'DFS three-color / Kahn topo sort'),
('Shortest path weighted graph', 'Dijkstra (non-neg) / Bellman-Ford (neg)'),
('All-pairs shortest path', 'Floyd-Warshall O(V^3)'),
('Topological order', 'Kahn BFS topo sort'),
('Min spanning tree', 'Kruskal (DSU) / Prim (heap)'),
('Dynamic connectivity / union-find', 'DSU path compression + union by rank'),
('Autocomplete / prefix search', 'Trie'),
('BST kth smallest / range sum', 'In-order DFS'),
]
for signal, pattern in tree_graph_signals:
print(f'{signal:50s} => {pattern}')Signal 7-9: Dynamic Programming Signals
DP signals are the hardest to recognise. Look for these keywords:
- 'Number of ways to...' → Counting DP (add sub-problem counts)
- 'Minimum/maximum cost to achieve...' → Optimisation DP (take min/max of sub-problems)
- 'Can we achieve...' (feasibility) → Boolean DP (OR of sub-problems)
- Sub-problem defined by two string indices → 2D DP (LCS, edit distance)
- Take or skip items under capacity constraint → Knapsack DP
- Optimal sub-structure + overlapping sub-problems → Check recursion tree for repeated calls → DP
# DP signal recognition
dp_signals = [
('Number of ways to climb stairs / decode string', '1D DP (Fibonacci-like)'),
('Minimum cost to reach end / coin change', '1D DP (greedy fails)'),
('Longest increasing subsequence', '1D DP O(n^2) or patience sort O(n log n)'),
('Longest common subsequence of two strings', '2D DP O(mn)'),
('Edit distance between two strings', '2D DP O(mn) (LCS variant)'),
('Partition array into two equal subsets', '0/1 knapsack boolean DP'),
('Fill knapsack with max value under weight limit', '0/1 knapsack optimisation DP'),
('Burst balloons / matrix chain multiplication', 'Interval DP'),
('Palindrome partitioning minimum cuts', 'Interval DP + prefix palindrome'),
('Rob houses in circle', '1D DP × 2 (linear sub-problems)'),
]
for signal, pattern in dp_signals:
print(f'{signal:55s} => {pattern}')Signal 10-12: Heap, Stack, and Greedy Signals
Signals for heap, monotonic stack, and greedy problems:
- Top-K elements / k-th largest or smallest → Heap (min-heap for top-K largest, max-heap for kth smallest) O(n log k)
- Streaming median → Two heaps (max-heap of small half + min-heap of large half)
- Next greater/smaller element → Monotonic stack O(n)
- Largest area rectangle / trapping water → Monotonic stack O(n)
- Interval scheduling / maximize non-overlapping intervals → Greedy (sort by end time)
# Heap / stack / greedy signals
heap_stack_greedy = [
('Top-K frequent elements', 'Min-heap size K: O(n log k)'),
('Kth largest in array', 'Max-heap pop K times: O(n + k log n)'),
('Streaming median', 'Two heaps (max + min): O(log n) per insert'),
('Merge K sorted lists', 'Min-heap of (val, list_idx): O(n log k)'),
('Next greater element', 'Monotonic decreasing stack: O(n)'),
('Largest rectangle in histogram', 'Monotonic increasing stack: O(n)'),
('Sliding window maximum', 'Monotonic decreasing deque: O(n)'),
('Trapping rain water', 'Two pointers OR monotonic stack: O(n)'),
('Jump game reachability / minimum jumps', 'Greedy range expansion: O(n)'),
('Merge overlapping intervals', 'Sort by start, linear scan: O(n log n)'),
('Gas station circular', 'Greedy: start from reset point: O(n)'),
('Task scheduler with cooldown', 'Greedy: sort by frequency: O(n log n)'),
]
for signal, pattern in heap_stack_greedy:
print(f'{signal:45s} => {pattern}')Signal 13-15: Backtracking and Bit Manipulation
Signals for backtracking and bit manipulation:
- Generate all subsets / permutations / combinations → Backtracking O(2^n or n!)
- Constraint satisfaction (N-queens, Sudoku) → Backtracking with pruning
- Find one missing / unique element → XOR O(n) O(1) space
- Enumerate all subsets of small set (n ≤ 20) → Bitmask 2^n enumeration
- Counting set bits / power of two check → Bit tricks (n & (n-1))
- State compression DP with small set → Bitmask DP O(2^n × n)
# Backtracking and bit signals
bt_bit_signals = [
('Generate all subsets of array', 'Backtracking O(n * 2^n) / bitmask'),
('Generate all permutations', 'Backtracking O(n * n!)'),
('Combination sum with target', 'Backtracking with pruning'),
('Word search in grid', 'Backtracking DFS on grid O(m*n*4^L)'),
('N-queens placement', 'Backtracking with column/diag sets'),
('Find single unique element (all others x2)', 'XOR all: O(n) O(1)'),
('Missing number in 0..n', 'XOR or sum formula: O(n) O(1)'),
('Count set bits in n', 'n &= n-1 loop or DP O(n)'),
('Check power of two', 'n > 0 and n & (n-1) == 0'),
('Travelling salesman (n<=20)', 'Bitmask DP O(2^n * n^2)'),
('Number with max XOR in array', 'Trie on binary representation'),
]
for signal, pattern in bt_bit_signals:
print(f'{signal:50s} => {pattern}')Constraint Analysis: What N Tells You
The input size constraint n directly tells you the acceptable time complexity — and therefore the algorithm family:
- n ≤ 20: O(2^n) or O(n!) acceptable — bitmask DP, backtracking
- n ≤ 500: O(n³) acceptable — Floyd-Warshall, brute-force DP
- n ≤ 5000: O(n²) acceptable — naive DP, quadratic sort
- n ≤ 10^6: O(n log n) needed — merge sort, heap, binary search
- n ≤ 10^8: O(n) needed — two pointers, sliding window, linear DP
This constraint analysis should be your first step after reading the problem — before deciding on any algorithm.
# Constraint -> acceptable complexity -> algorithm family
complexity_map = [
('n <= 20', 'O(2^n) or O(n!)', 'Bitmask DP, backtracking/permutations'),
('n <= 500', 'O(n^3)', 'Floyd-Warshall, cubic DP, brute force'),
('n <= 5000', 'O(n^2)', 'Quadratic DP, bubble/insertion sort'),
('n <= 100000', 'O(n log n)', 'Merge sort, heap, binary search, topo sort'),
('n <= 1000000', 'O(n)', 'Linear DP, two pointers, sliding window, hash'),
('n <= 10^8', 'O(n) tight', 'Only simplest O(n) — no large constants'),
('n <= 10^18', 'O(log n) or O(1)', 'Math / number theory, binary search on answer'),
]
print(f'{'Constraint':15s} {'Complexity':15s} {'Algorithm Family'}')
print('-'*70)
for constraint, complexity, algorithms in complexity_map:
print(f'{constraint:15s} {complexity:15s} {algorithms}')Problem → Pattern: Quick-Fire Practice
Practice this mapping until it is automatic. Read each problem description and identify the pattern before looking at the solution. Speed matters — in an interview you should identify the pattern in under 60 seconds:
- 'Given a sorted array, find if any two elements sum to K'
- 'Given a tree, find the diameter (longest path between any two nodes)'
- 'Given n tasks with cooldown k, find minimum CPU intervals'
- 'Given a string, find the longest palindromic substring'
- 'Given 1..n with one missing, find the missing number'
# Quick-fire pattern recognition answers
problems = [
('Sorted array: two elements sum to K',
'Two pointers (left from start, right from end): O(n)'),
('Tree diameter (longest path)',
'DFS returning (height, max_diameter) pair: O(n)'),
('Task scheduler with cooldown k',
'Greedy: (max_freq - 1)*(k+1) + count_of_max_freq: O(n log n)'),
('Longest palindromic substring',
'Expand around centre OR Manacher: O(n^2) or O(n)'),
('Missing number in 1..n',
'XOR all indices and values: O(n) O(1)'),
('Number of islands in binary grid',
'BFS/DFS flood fill counting connected components: O(m*n)'),
('Decode string like 3[a2[bc]] -> aaabcbcaabcbc',
'Stack to handle nested brackets: O(n)'),
('Valid parentheses [(){[]}]',
'Stack push open, pop+match on close: O(n)'),
]
for problem, solution in problems:
print(f'Q: {problem}\nA: {solution}\n')Red Flags: When Your Pattern Fails
Even experienced engineers choose the wrong pattern initially. Recognise these signals that your current approach is wrong and pivot:
- Your O(n²) passes small tests but TLEs on large inputs → need a hash map, binary search, or monotonic structure
- Your greedy fails a counter-example → try DP
- Your DP state space is too large → look for a greedy proof or a smarter state definition
- Your BFS gives wrong answer → check if you need Dijkstra (weighted) instead of BFS (unweighted)
- You are passing null pointer exceptions → add base cases and edge-case guards before implementing
# Red flags and recovery strategies
red_flags = [
('TLE on large n', 'Check complexity; switch from O(n^2) to O(n log n) or O(n)'),
('WA with greedy', 'Find a counter-example; switch to DP or prove exchange arg'),
('DP table huge', 'State compression (bitmask/rolling array) or different state'),
('BFS gives wrong shortest path', 'Check if edges have weights; use Dijkstra instead'),
('Stack overflow in recursion', 'Add memoisation or convert to iterative with explicit stack'),
('Off-by-one in binary search', 'Use half-open intervals [lo, hi); verify with 2-element test'),
('DSU wrong answer', 'Check 0-indexed vs 1-indexed; check union direction'),
('Backtracking TLE', 'Add pruning conditions; ensure undo step is correct'),
]
print('Pattern | Recovery')
print('-'*70)
for flag, recovery in red_flags:
print(f'{flag:40s} => {recovery}')Communicating Pattern Recognition in Interviews
In interviews, verbalising your pattern recognition demonstrates expertise and gives the interviewer a chance to guide you if you are on the wrong track. Use this script structure:
- 'I notice the array is sorted, so I'm thinking binary search...'
- 'The problem asks for the maximum subarray, which is a classic Kadane's algorithm problem...'
- 'We need all possible subsets, which suggests backtracking with a recursion tree...'
- 'The constraint n ≤ 20 tells me 2^n = 1M is acceptable, so bitmask DP could work...'
After stating the pattern, mention the time and space complexity before writing a single line of code. This shows you are thinking about efficiency before implementation.
# Interview communication template
def communicate_approach(problem, pattern, time_complexity, space_complexity, edge_cases):
print(f'Problem: {problem}')
print(f'Pattern: {pattern}')
print(f'Time: {time_complexity}, Space: {space_complexity}')
print(f'Edge cases to handle: {", ".join(edge_cases)}')
print()
# Example communications
communicate_approach(
problem='Find longest substring without repeating characters',
pattern='Sliding window with a set tracking current window characters',
time_complexity='O(n)',
space_complexity='O(min(n, alphabet_size))',
edge_cases=['empty string', 'all same characters', 'all unique characters']
)
communicate_approach(
problem='Given sorted matrix, find if target exists',
pattern='Binary search or staircase search (top-right corner): eliminate row or column each step',
time_complexity='O(m + n)',
space_complexity='O(1)',
edge_cases=['empty matrix', 'single element', 'target at corners']
)Building Your Pattern Recognition Vocabulary
The fastest way to build pattern recognition is to solve problems in themed batches — not randomly. Spend one week on sliding window problems only. Then two-pointer problems. Then DP problems. Doing 20 problems of the same type rapidly builds the intuition to recognise that pattern at a glance.
After each problem, write a one-line 'pattern note': the problem signal and the pattern it triggered. Build your own cheat sheet. After 200 problems solved in themed batches, you will recognise ~90% of interview problems in under 30 seconds — the remaining 10% require careful analysis even for experienced engineers.
# Personal pattern note template
pattern_notes = [
{'signal': 'sorted array + two sum', 'pattern': 'two pointers', 'example': 'LC 167 Two Sum II'},
{'signal': 'longest X without repeating', 'pattern': 'sliding window + set', 'example': 'LC 3 Longest Substring'},
{'signal': 'max sum subarray', 'pattern': 'Kadane', 'example': 'LC 53 Max Subarray'},
{'signal': 'permutations/subsets', 'pattern': 'backtracking', 'example': 'LC 46 Permutations'},
{'signal': 'tree path sum', 'pattern': 'DFS with accumulator', 'example': 'LC 112 Path Sum'},
{'signal': 'course schedule', 'pattern': 'Kahn topo sort', 'example': 'LC 207 Course Schedule'},
{'signal': 'top-K elements', 'pattern': 'min-heap size K', 'example': 'LC 215 Kth Largest'},
]
print(f'{'Signal':40s} {'Pattern':30s} {'Example'}')
print('-'*90)
for note in pattern_notes:
print(f'{note["signal"]:40s} {note["pattern"]:30s} {note["example"]}')Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: pattern recognition maps problem signals to algorithm families — sorted array implies binary search, 'all subsets' implies backtracking, 'minimum cost' implies DP, the constraint n tells you the acceptable complexity: n ≤ 20 allows O(2^n), n ≤ 10^6 requires O(n log n) or better, and verbalising the pattern and complexity before coding demonstrates expertise and enables interviewer feedback. Next up we put pattern recognition into practice with timed mock interview problems at easy and medium difficulty.
Frequently asked questions
Is the “Pattern Recognition Cheat Sheet” lesson free?
Yes — the full text of “Pattern Recognition Cheat Sheet” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Pattern Recognition Cheat Sheet”?
Map 15 common problem signals (sorted array, need all combos, maximise value with constraint, etc.) to the algorithm patterns that solve them fastest. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Pattern Recognition Cheat Sheet” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.