Algorithm Patterns
Two pointers, sliding window, BFS/DFS, memoisation — recognising the pattern is 80% of the solve.
90 minDifficulty 4/5cs · interviewAI-writtenWritten by a model on 16 August 2026 and not yet read by a person. Checked automatically: schema, the pedagogical rules the hand-written material is held to, and every diagram parsed for real.
Before this
Why this exists
A problem that looks unique — "find the longest substring without repeating characters" — is actually a well-known pattern, sliding window, wearing a costume. Recognising the pattern underneath a problem's specific wording is most of the actual work; the implementation, once you know which pattern applies, is usually the easy part.
The mental model
A handful of patterns cover a large fraction of interview-style problems: two pointers for sorted-array comparisons, sliding window for contiguous subarray/substring problems, BFS/DFS for graph and tree traversal, and memoisation for problems with overlapping subproblems. Learning to spot which SHAPE a problem has — not memorising specific solutions — is what transfers to a problem you've never seen before.
How it works
Two pointers: exploit that the input is sorted (or can be)
Given a sorted array, finding two numbers that sum to a target doesn't require checking every pair (O(n²)) — start one pointer at each end; if the sum is too big, move the right pointer left; if too small, move the left pointer right. Each step eliminates one candidate, giving O(n) total instead of checking every combination.
Sliding window: track a contiguous range efficiently, without restarting
Finding the longest substring without repeating characters doesn't require re-scanning from scratch for every possible starting point — grow a window's right edge, and when a duplicate is found, shrink the LEFT edge just enough to remove it, tracking the best length seen so far. This turns an O(n²) brute-force scan into O(n), because each character is added and removed from the window at most once.
BFS explores level by level; DFS explores one path to its end first
Breadth-first search visits all neighbours at the current distance before moving further out, which is exactly what guarantees it finds the SHORTEST path first in an unweighted graph. Depth-first search commits to one path as deep as it goes before backtracking, which uses less memory and suits problems like detecting a cycle or exploring all possible combinations, where shortest-path isn't the goal.
Memoisation turns exponential recomputation into linear work
A naive recursive Fibonacci recomputes `fib(30)` by recalculating `fib(28)` many times over, buried inside separate calls to `fib(29)` and `fib(30)` — this redundant recomputation is what makes the naive version exponential. Caching each subproblem's result the first time it's computed, and returning the cached value on every subsequent request for the same input, is what turns this into linear time.
The mechanism
Recognising a pattern starts with identifying the problem's SHAPE: does it involve a sorted structure and pair-finding (two pointers), a contiguous range with a changing constraint (sliding window), traversal of a graph or tree (BFS/DFS depending on whether shortest-path matters), or repeated identical subproblems (memoisation)? The shape, not the surface wording, is what determines which pattern applies.
flowchart TD
P[Problem] --> Q1{Sorted array,\nfind a pair?}
Q1 -->|yes| TP[Two pointers]
P --> Q2{Contiguous\nsubarray/substring?}
Q2 -->|yes| SW[Sliding window]
P --> Q3{Graph/tree\ntraversal?}
Q3 -->|shortest path| BFS[BFS]
Q3 -->|explore all paths| DFS[DFS]
P --> Q4{Overlapping\nsubproblems?}
Q4 -->|yes| MEMO[Memoisation]What people get wrong
- Solving algorithm problems is about memorising solutions to specific known problems.
- The transferable skill is recognising which underlying PATTERN a novel problem's shape matches — memorising 'two sum' doesn't help with a differently-worded problem that happens to share the same two-pointer shape underneath. Interview problems are frequently variations on the same handful of patterns, worded differently specifically to test whether you can recognise the pattern rather than recall a memorised solution.
- BFS is always better than DFS because it finds the shortest path.
- BFS's shortest-path guarantee only matters when shortest path is actually the goal — DFS uses less memory (proportional to depth rather than breadth) and is the natural fit for problems like exploring all combinations or detecting a cycle, where 'shortest' isn't a meaningful concept. Choosing BFS by default regardless of the actual goal wastes its advantage (memory efficiency isn't its strength) while gaining nothing when shortest-path was never the requirement.
- Memoisation always makes a recursive solution faster.
- Memoisation only helps when subproblems genuinely OVERLAP — are recomputed multiple times with identical inputs; a recursive solution where every subproblem is unique (like a straightforward divide with no repeated subranges) gains nothing from caching results nobody will ever look up again. Adding memoisation indiscriminately adds memory overhead for cache storage without necessarily providing any speed benefit, if the underlying recursion never actually repeats work.
When not to use it
- The problem involves a WEIGHTED graph, where some edges cost more than others to traverse.
- Dijkstra's algorithm (or a variant), not plain BFS — BFS's shortest-path guarantee only holds for unweighted graphs where every edge counts equally.
- The input isn't sorted and sorting it would cost more than a different approach.
- Consider whether a hash map based approach (trading space for time) solves the problem without requiring the sorted-input precondition two pointers relies on.
Terms
- Two pointers
- — A technique using two indices moving through a (typically sorted) structure to avoid checking every possible pair, reducing quadratic approaches to linear.
- Sliding window
- — Maintaining a contiguous range with two moving boundaries, expanding and shrinking it incrementally rather than re-scanning from scratch.
- Memoisation
- — Caching the result of a computation keyed by its input, so identical, overlapping subproblems are computed once and reused rather than recalculated.
- Time complexity
- — A description of how an algorithm's running time grows relative to input size, typically expressed in big-O notation.
In an interview
You're asked to find the maximum sum of any contiguous subarray of length k. What pattern applies, and why not brute force?
- sliding window — maintain a running sum for a window of size k
- slide the window by subtracting the element leaving and adding the element entering, rather than re-summing the whole window each time
- this is O(n) instead of the O(n*k) brute-force approach of summing every window from scratch
Can you recall it?
What makes sliding window faster than a brute-force approach for a contiguous subarray/substring problem, specifically?