A method you can repeat
- Understand – say the problem in your own words. Work through the example by hand.
- Brute force first – what's the simplest (even slow) way? Write down its Big-O.
- Look for clues – sorted input? “shortest”? “all possible”? Use the table below.
- Improve – pick a better pattern or data structure. Check the new Big-O.
- Code it in small pieces.
- Test – the example, then edge cases: empty input, one item, all items the same, very big numbers.
Think of it like this: Like a doctor: listen to the symptoms (the problem), recognise the pattern (“this looks like the flu”), then apply the treatment you know works for that pattern.
Clue → technique cheat sheet
| If the problem says or has... | Try |
|---|---|
| sorted list, “find a pair” | two pointers, binary search |
| “stretch of neighbouring items”, longest/shortest window | sliding window |
| many “sum from i to j” questions | prefix sums |
| “have I seen this before?”, counting, pairs that add to X | dict / set (hashing) |
| “next bigger / previous smaller” | monotonic stack |
| brackets, undo, most recent first | stack |
| “k largest / smallest”, always the best next | heap |
| fewest steps in a maze or network | BFS |
| connected groups, islands, explore everything | DFS / union-find |
| shortest path with distances | Dijkstra |
| tasks with prerequisites | topological sort |
| “all combinations / arrangements” | backtracking |
| “how many ways”, “best total”, choices that overlap | dynamic programming |
| “best choice now never hurts later” | greedy |
Big-O from the input size
The limits in a problem quietly tell you how fast your solution must be (a computer does roughly 10⁷–10⁸ simple steps per second):
| If n is up to... | You can afford about |
|---|---|
| 10–20 | O(2ⁿ), O(n!) – backtracking |
| 500 | O(n³) |
| 5,000 | O(n²) |
| 1,000,000 | O(n log n) or O(n) |
| 10¹⁸ | O(log n) or O(1) – maths or binary search |