Problem-Solving Patterns — Overview
Overview
The named algorithms in the earlier sections are instances of a smaller number of recurring strategies. Recognising the strategy is what lets you solve a problem you have never seen, and it is the difference between memorising algorithms and understanding them.
Every pattern here is a way of avoiding work that brute force would do: by exploiting structure the input already has, by reusing subresults, or by proving that whole branches of the search cannot contain the answer.
In This Section
- Two Pointers & Sliding Window — exploit sortedness or contiguity to replace a nested loop with a single pass.
- Divide & Conquer — split, solve independently, combine.
- Greedy Algorithms — take the locally best option, when that provably suffices.
- Dynamic Programming — solve overlapping subproblems once and reuse the answers.
- Backtracking — search systematically, abandoning branches that cannot work.
Recognising Which One
| Signal in the problem | Likely pattern |
|---|---|
| Sorted array; "find a pair/triple summing to…" | Two pointers |
| "Contiguous subarray/substring with…" | Sliding window |
| "Sort", "search", or a naturally halving structure | Divide & conquer |
| "Maximum/minimum number of…" with an obvious local choice | Greedy — then prove it |
| "Count the ways", "optimal value", overlapping subproblems | Dynamic programming |
| "All permutations/combinations/valid configurations" | Backtracking |
| "Shortest path", "reachable", "order of dependencies" | Graph algorithms |
| "Top k", "k-th largest", "next event" | Heap |
| "Have I seen this before", "count occurrences" | Hash table |
Greedy, DP and Backtracking Are the Same Question
All three explore a space of choices; they differ in how much of it they can safely skip.
The progression is one of decreasing confidence and increasing cost. Greedy commits immediately and is fastest. DP considers every option but never recomputes anything. Backtracking explores properly and relies on pruning to stay tractable.
Greedy algorithms are easy to write and easy to believe. The failure mode is that they produce plausible, slightly wrong answers on inputs you did not test — and unlike a crash, nothing announces it. A greedy solution needs an argument for why the local choice is safe, not merely a few passing examples. See Greedy Algorithms for what such an argument looks like.
Related Pages
- Complexity & Analysis — for judging whether a pattern's cost is acceptable.
- Data Structures — the structures these patterns lean on.