DSA Patterns Made Simple · Heaps, Backtracking and Dynamic Programming
Which Pattern Should I Use? A One-Page Guide
A cheat sheet that maps the words in a problem statement and the input size to the right pattern, with the template to reach for. Use it on every new problem until it becomes automatic.
The problem
You know the patterns individually, but a new problem doesn't say "use a sliding window". The skill interviews test is recognition: reading the problem and picking the pattern quickly.
Real-world analogy
A mechanic doesn't try every tool on a car. A rattle near the wheel suggests one set of checks; a squeal when braking suggests another. Experience turns symptoms into a short list of likely causes. The table below is that list for coding problems.
The idea
Read the problem and look for these signals:
| If you see… | Try… |
|---|---|
| "seen before", duplicates, pair with a target (unsorted) | Hash map / set |
| same letters any order, most frequent, group by | Counting and grouping |
| sorted array, pair/triplet sum, palindrome, in-place | Two pointers |
| contiguous substring/subarray, longest/shortest with a rule | Sliding window |
| many range sums, subarray sum = k with negatives | Prefix sums |
| sorted + search, "first position where", minimise the largest | Binary search |
| linked list cycle, middle, nth from end | Fast and slow pointers |
| reverse or merge linked lists | Pointer reversal, dummy node |
| brackets, undo, next greater/smaller element | Stack / monotonic stack |
| [start, end] pairs, meetings, overlaps | Sort by start, then sweep |
| tree: depth, paths, validate | Tree DFS (recursion) |
| tree levels, nearest, minimum depth | Tree BFS (queue) |
| grid regions, connected, fewest steps | Flood fill (DFS) / BFS |
| prerequisites, order of tasks | Topological sort |
| top k, kth largest, stream | Heap |
| all subsets/permutations/combinations | Backtracking |
| number of ways, min/max cost with choices | Dynamic programming |
And use the input size to check your choice:
| n up to… | Expected complexity | Usually means |
|---|---|---|
| 10–20 | O(2ⁿ), O(n!) | Backtracking |
| 1,000 | O(n²) | Nested loops or 2D DP are fine |
| 100,000 | O(n log n) or O(n) | Sorting, heap, hash map, two pointers, window |
| 10⁹ (a value, not a list) | O(log n) | Binary search on the answer |
The code
Not every problem needs a clever pattern. This small "pattern picker" encodes the table above as keyword rules, a playful way to practise reading problem statements.
RULES = [ # checked in order; the first rule with a matching phrase wins
(["subarray sum equals", "range sum"], "prefix sums"),
(["longest substring", "contiguous", "window"], "sliding window"),
(["kth largest", "top k", "k most"], "heap"),
(["all subsets", "all permutations", "every combination"], "backtracking"),
(["number of ways", "minimum cost", "fewest coins"], "dynamic programming"),
(["prerequisite", "order of tasks"], "topological sort"),
(["grid", "island"], "BFS / DFS flood fill"),
(["level", "nearest"], "BFS"),
(["intervals", "meetings"], "sort + sweep"),
(["parentheses", "next greater"], "stack"),
(["appears twice", "duplicate", "seen before"], "hash map"),
(["sorted array", "palindrome"], "two pointers"),
]
def pick(problem):
text = problem.lower()
for phrases, pattern in RULES:
if any(p in text for p in phrases):
return pattern
return "start with brute force, then ask what it repeats"
for problem in [
"Find the longest substring without repeating characters",
"Given a sorted array, find a pair that sums to the target",
"Return the kth largest element in an unsorted array",
"Count the number of ways to decode a message",
"Can you finish all courses given each prerequisite?",
"Count the islands in a grid of land and water",
"Check whether the parentheses are balanced",
"Return true if any value appears twice (duplicate)",
]:
print(f"{pick(problem):<22} <- {problem}")
Output
sliding window <- Find the longest substring without repeating characters two pointers <- Given a sorted array, find a pair that sums to the target heap <- Return the kth largest element in an unsorted array dynamic programming <- Count the number of ways to decode a message topological sort <- Can you finish all courses given each prerequisite? BFS / DFS flood fill <- Count the islands in a grid of land and water stack <- Check whether the parentheses are balanced hash map <- Return true if any value appears twice (duplicate)
const RULES = [ // checked in order; the first rule with a matching phrase wins
[["subarray sum equals", "range sum"], "prefix sums"],
[["longest substring", "contiguous", "window"], "sliding window"],
[["kth largest", "top k", "k most"], "heap"],
[["all subsets", "all permutations", "every combination"], "backtracking"],
[["number of ways", "minimum cost", "fewest coins"], "dynamic programming"],
[["prerequisite", "order of tasks"], "topological sort"],
[["grid", "island"], "BFS / DFS flood fill"],
[["level", "nearest"], "BFS"],
[["intervals", "meetings"], "sort + sweep"],
[["parentheses", "next greater"], "stack"],
[["appears twice", "duplicate", "seen before"], "hash map"],
[["sorted array", "palindrome"], "two pointers"],
];
function pick(problem) {
const text = problem.toLowerCase();
for (const [phrases, pattern] of RULES) {
if (phrases.some((p) => text.includes(p))) return pattern;
}
return "start with brute force, then ask what it repeats";
}
for (const problem of [
"Find the longest substring without repeating characters",
"Given a sorted array, find a pair that sums to the target",
"Return the kth largest element in an unsorted array",
"Count the number of ways to decode a message",
"Can you finish all courses given each prerequisite?",
"Count the islands in a grid of land and water",
"Check whether the parentheses are balanced",
"Return true if any value appears twice (duplicate)",
]) {
console.log(`${pick(problem).padEnd(22)} <- ${problem}`);
}
Output
sliding window <- Find the longest substring without repeating characters two pointers <- Given a sorted array, find a pair that sums to the target heap <- Return the kth largest element in an unsorted array dynamic programming <- Count the number of ways to decode a message topological sort <- Can you finish all courses given each prerequisite? BFS / DFS flood fill <- Count the islands in a grid of land and water stack <- Check whether the parentheses are balanced hash map <- Return true if any value appears twice (duplicate)
Even this toy has a trap: "unsorted array" contains the words "sorted array", so the heap rule must be checked before the two-pointer rule. Real problems are messier still: "pair" in an unsorted array is a hash map problem, not two pointers. Use the table as a starting point, then check it against the input size and constraints.
Common mistakes
- Pattern-matching on one word. "Pair" + unsorted → hash map; "pair" + sorted → two pointers. Read the constraints.
- Ignoring n. n ≤ 20 almost always invites backtracking; n = 10⁵ rules out O(n²).
- Forcing a pattern. If nothing fits, write the brute force and ask what it repeats (lesson 1). The pattern usually appears.
- Never reviewing mistakes. After each practice problem, write one line: "the signal was ___, the pattern was ___".
Key points
- Recognition is the real interview skill: signals in the wording point to patterns.
- Cross-check with the input size before committing.
- Brute force first when unsure; its repetition reveals the pattern.
- Practise mixed problems, not one pattern at a time, once you know them.
Practice questions
An unsorted array and 'find two numbers that add up to the target': which pattern, and why not two pointers?
Answer
A hash map: one pass, checking whether target − x has been seen. Two pointers needs sorted input; sorting first costs O(n log n) and loses the original indexes the problem usually asks for.
A problem has n ≤ 15 and asks for every valid arrangement. What does that suggest?
Answer
Backtracking: the small n and 'every arrangement' mean an exponential search (2ⁿ or n!) is expected and fits in time, ideally with pruning.
Open in the app to mark lessons complete, take notes and track your progress.