Loading learning content...
Here's a secret that transforms how you approach algorithmic problems: almost every problem you'll encounter is a variation of a known problem. The novel problems are rare exceptions, appearing primarily in advanced competitive programming or research contexts. For interviews, practical software engineering, and the vast majority of algorithmic challenges, the problem in front of you is almost certainly a disguised version of a classic.
Once you realize this, the goal shifts from "inventing" solutions to recognizing which known problem archetype applies. This recognition skill—mapping an unfamiliar problem to a familiar template—is the highest-leverage skill in algorithmic problem-solving. It transforms creativity requirements into pattern-matching exercises.
By the end of this page, you will possess a mental library of problem archetypes and the techniques for recognizing when new problems are variations of known ones. You'll learn how to strip away problem disguises, identify the core computational structure, and apply battle-tested solutions with confidence.
Why are most problems variations of known archetypes? Because computational problems have fundamental structures. These structures emerge from the nature of computation itself:
These aren't arbitrary categories; they represent the fundamental ways computers can attack problems. Every new problem ultimately reduces to one or a combination of these fundamental operations.
When facing any new problem, your first instinct should be: "What known problem can I REDUCE this to?" Not "How do I solve this from scratch?" but "What is this a disguised version of?" This mindset shift is the hallmark of experienced problem-solvers.
Problem setters disguise classic problems through:
Your job is to strip away these disguises and recognize the underlying archetype.
The following archetypes represent the fundamental problem families. Memorize these; they're the foundation of pattern recognition.
| Problem Template | When It Applies | Core Solution |
|---|---|---|
| Two Sum | Find pair with property in array | Hash map for O(1) complement lookup |
| Binary Search on Sorted Array | Find element or insertion point | Halve search space each iteration |
| Binary Search on Answer | Find minimum/maximum that satisfies condition | Binary search on value space, test condition |
| K-th Element | Find k-th largest/smallest | Quickselect O(n), or heap O(n log k) |
| Find Peak/Valley | Local min/max in array | Binary search with comparison to neighbors |
| Problem Template | When It Applies | Core Solution |
|---|---|---|
| Maximum Subarray (Kadane) | Find contiguous subarray with max sum | Track running sum, reset when negative |
| Longest Increasing Subsequence | Find longest sequence maintaining order | DP O(n²) or patience sort O(n log n) |
| Sliding Window | Find subarray of fixed/variable size with property | Expand/contract window, track state |
| Prefix Sum / Difference Array | Range queries on static array | Precompute cumulative sums |
| Stock Buy/Sell | Optimize timing of transactions | DP or track global min-so-far |
| Problem Template | When It Applies | Core Solution |
|---|---|---|
| Pattern Match | Find occurrences of pattern in text | KMP, Rabin-Karp, Z-algorithm |
| Edit Distance | Minimum operations to transform A to B | 2D DP: insert, delete, replace |
| Longest Common Subsequence | Longest subsequence in both strings | 2D DP: match or skip character |
| Longest Palindrome | Find longest palindromic substring/subsequence | Expand from center, DP, Manacher |
| Anagram / Permutation | Check or find character rearrangements | Frequency arrays, sliding window |
| Problem Template | When It Applies | Core Solution |
|---|---|---|
| Shortest Path (Unweighted) | Minimum edges from source to destination | BFS, parent tracking for path |
| Shortest Path (Weighted) | Minimum cost path | Dijkstra (non-negative), Bellman-Ford (negative) |
| Cycle Detection | Find if cycle exists | DFS with colors, or Union-Find |
| Connected Components | Count/identify separate groups | DFS/BFS traversal, or Union-Find |
| Topological Sort | Order with dependencies | Kahn's BFS or DFS post-order |
| Bipartite Check | Can graph be 2-colored? | BFS/DFS with alternating colors |
| Minimum Spanning Tree | Connect all with minimum total weight | Prim's or Kruskal's with Union-Find |
DP problems deserve special attention because they're so common and their archetypes are so recognizable once you know them.
Recognize DP problem types by asking these diagnostic questions:
| Question | If Yes | DP Type |
|---|---|---|
| Am I processing one sequence element by element? | State: index in sequence | Linear DP |
| Am I comparing/combining two sequences? | State: indices in both sequences | 2D Sequence DP |
| Am I selecting items with a capacity constraint? | State: items considered + capacity used | Knapsack |
| Am I finding optimal way to split/merge a range? | State: interval endpoints | Interval DP |
| Am I finding paths through a grid? | State: (row, col) position | Grid DP |
| Am I making decisions at tree nodes? | State: current node, possibly include/exclude | Tree DP |
| Am I selecting a subset of n ≤ 20 items? | State: bitmask of selected items | Bitmask DP |
Many problems reduce to knapsack variants: Subset Sum, Partition Equal Subset, Target Sum, Coin Change (both count & min coins), Rod Cutting. Learn to recognize the structure: "Given items with sizes/values, optimize subject to a capacity constraint."
Let's see how to strip away disguises and recognize the core problem:
Given beginWord, endWord, and a dictionary, find the shortest transformation sequence from beginWord to endWord, changing one letter at a time, where each intermediate word must be in the dictionary.
The Disguise: Word transformations, dictionary, strings.
Strip the Disguise:
The Core Problem: Shortest path in an unweighted graph → BFS.
Given an array of meeting time intervals, find the minimum number of conference rooms required.
The Disguise: Meeting scheduling, conference rooms.
Strip the Disguise:
The Core Problem: Maximum number of overlapping intervals → Sweep line algorithm. Sort by start time, use min-heap to track end times of ongoing meetings, or simply count events.
Given coins of different denominations and a total amount, find the minimum number of coins needed to make up that amount.
The Disguise: Coins, money.
Strip the Disguise:
The Core Problem: Unbounded Knapsack (minimization variant) → DP with dp[amount] = min coins to make that amount.
Given a reference of a node in a connected undirected graph, return a deep copy of the graph.
The Disguise: Cloning, deep copy.
Strip the Disguise:
The Core Problem: Graph traversal (BFS/DFS) with mapping → Use hash map to track old-to-new node mapping, traverse graph, create copy of each node and its edges.
Formal problem reduction is a technique from theoretical computer science that's immensely practical. The idea: show that Problem A can be transformed into Problem B, solve B with a known algorithm, then transform the solution back.
Problem: Given strings s and t, check if s is a subsequence of t.
Reduction Process:
Core question: Can we find characters of s (in order) in t?
Abstract: Check if ordered elements from set A appear in sequence B.
Match: This is a two-pointer problem. Or: it's a special case of LCS where we check if LCS length equals |s|.
Solution via two pointers:
The reduction to LCS would work but be overkill (O(n×m)). The two-pointer approach is the more direct archetype match.
Often, a problem can be reduced to multiple known problems. Choose the reduction that leads to the best complexity. Is Subsequence → LCS works but O(n×m). Is Subsequence → Two Pointers works with O(n+m). Same problem, different reductions, different efficiencies.
Pattern recognition requires a library of patterns. Here's how to build and maintain yours:
Master these 30+ canonical problems—they're the templates for hundreds of variations:
After solving each problem, record:
This log becomes your personal pattern library. Review it periodically. Over time, you'll see the same archetypes appearing again and again, confirming the pattern-based nature of algorithmic problems.
Solving 50 problems deeply, understanding their archetypes and connections, beats rushing through 200 problems without reflection. It's not about problem count—it's about pattern recognition depth. Each problem should expand or reinforce your archetype library.
Many advanced problems combine multiple archetypes. Recognizing these combinations is a higher-order skill.
| Combination | Example Problem | Approach |
|---|---|---|
| Binary Search + Greedy | Split Array Largest Sum | Binary search on answer, greedy check feasibility |
| Graph + DP | Longest Path in DAG | Topological sort, then DP on sorted order |
| Graph + Binary Search | Swim in Rising Water | Binary search on time, BFS to check connectivity |
| Trie + Backtracking | Word Search II | Build trie from words, DFS grid with trie validation |
| Union-Find + Sort | Kruskal's MST | Sort edges, union if components different |
| DP + Binary Search | LIS in O(n log n) | DP with binary search on subsequence array |
| Sliding Window + Hash | Longest Substring K Distinct | Window with hash map tracking character counts |
When a problem doesn't match a single archetype:
Example: Cheapest Flights Within K Stops
Sub-tasks:
Composition: Modified Bellman-Ford with K iterations, or Dijkstra with state = (node, stops remaining).
If multiple archetypes seem applicable, think about which one captures the "hard part" of the problem. The other archetypes may just be preprocessing or postprocessing around the core computational challenge.
Sometimes, despite best efforts, the problem doesn't obviously match any known archetype. Here's what to do:
If direct matching fails, try transforming the problem:
Inverse the problem: Instead of finding X, find NOT X. Sometimes the complement is easier.
Change the perspective: Instead of processing left-to-right, go right-to-left. Instead of building up, tear down.
Dual the entities: Swap what you're iterating over. Instead of iterating nodes, iterate edges. Instead of iterating positions, iterate values.
Parameterize and binary search: If finding the optimal is hard, binary search on the answer and check feasibility.
Meet in the middle: For exponential searches, split in half and combine.
If you've reviewed many archetypes and still can't find a match, before assuming the problem is novel, verify: Have I correctly understood the problem? Have I identified all constraints? Often, the matching archetype is there—we just haven't decoded the problem correctly yet.
Let's practice identifying archetypes in unfamiliar problems:
Given a network of n nodes with directed edges and their travel times, find the time it takes for all nodes to receive a signal sent from node k. Return -1 if not all nodes are reachable.
Archetype Identification:
Archetype: Single-source shortest path → Dijkstra's algorithm. Answer is max of all shortest paths.
A message '12' could be decoded as 'AB' (1 2) or 'L' (12). Given a string of digits, count the number of ways to decode it.
Archetype Identification:
Archetype: Linear DP (similar to Climbing Stairs). dp[i] = ways to decode first i characters. Transition: dp[i] = dp[i-1] (if valid 1-digit) + dp[i-2] (if valid 2-digit).
Given a m×n grid with 0 (gate), -1 (wall), INF (empty room), fill each empty room with distance to nearest gate.
Archetype Identification:
Archetype: Multi-source BFS. Start BFS from all gates simultaneously (add all gates to initial queue). Each cell's first visit gives its distance.
Given an array of positive integers, determine if it can be partitioned into two subsets with equal sum.
Archetype Identification:
Archetype: Subset Sum (special case of 0/1 Knapsack). Target = totalSum/2. dp[s] = can we form sum s? Classic DP with items and capacity.
The ability to relate new problems to known problems is the culminating skill of pattern recognition. It transforms algorithmic problem-solving from creative invention to systematic recognition.
Module Complete:
You have now completed the Pattern Recognition Framework module. You possess:
Together, these skills form a complete system for approaching any algorithmic problem systematically and confidently.
The Pattern Recognition Framework is now yours. With practice, these techniques become automatic—you'll find yourself recognizing patterns within seconds of reading a problem. Continue to the next module to learn about constraint-based algorithm selection, where you'll apply these recognition skills to rapidly select optimal algorithms.