A method you can repeat
- Understand – restate the problem; work the example by hand.
- Brute force first – the simplest (even slow) idea, and its Big-O.
- Look for clues – sorted input? “shortest”? “all possible”? See the table.
- Improve – pick a better pattern or data structure; check the Big-O against the limits.
- Code it in small pieces. Watch for overflow (
long long). - Test – the example, then edge cases: n = 1, all equal, biggest values.
Think of it like this: Like a doctor: listen to the symptoms, recognise the pattern, apply the treatment that works for it.
Clue → technique → STL tool
| Clue | Technique | C++ tools |
|---|---|---|
| sorted data, find a pair / position | two pointers, binary search | lower_bound, upper_bound |
| stretch of neighbours, longest/shortest | sliding window | deque, counting arrays |
| many range-sum questions | prefix sums | vector<long long> |
| seen before? counting? pairs adding to X | hashing | unordered_map, unordered_set |
| sorted order, next bigger value | balanced BST | set, map |
| next bigger / previous smaller | monotonic stack | stack |
| k largest, always the best next | heap | priority_queue |
| fewest steps in a maze/network | BFS | queue |
| groups, islands, explore all | DFS / union-find | recursion, a DSU struct |
| weighted shortest path | Dijkstra | priority_queue with greater |
| tasks with prerequisites | topological sort | in-degree + queue |
| all combinations / arrangements | backtracking | next_permutation |
| how many ways / best total with overlapping choices | dynamic programming | vector tables |
Big-O from the limits
A computer does roughly 10⁸ simple C++ operations per second:
| n up to | You can afford |
|---|---|
| 10–20 | O(2ⁿ), O(n!) |
| 500 | O(n³) |
| 5,000 | O(n²) |
| 10⁶ | O(n log n) or O(n) |
| 10¹⁸ | O(log n) or O(1) |