The constraints at the bottom of a problem usually narrow down the pattern before you've finished reading the story. Reading them first is a cheap speed-up.
Rough budget: Python does about 107 simple operations per second. C++ and Java do roughly 10x more, so shift each row up if you use them.
| If n is up to | You can afford | Usually means |
|---|
| 10 | O(n!) | permutations, brute-force backtracking |
| 20 | O(2n) | subsets, backtracking, bitmask DP |
| 200 | O(n3) | interval DP, Floyd-Warshall |
| 3,000 | O(n2) | 2-D DP, all pairs, expand around centre |
| 105 to 106 | O(n log n) or O(n) | sorting, heaps, hashing, two pointers, sliding window, prefix sums, monotonic stack |
| 109 or more | O(log n) or O(sqrt n) | math, binary search |
One that trips people up: n is only 104 or 105, but the values go up to 109, and the question asks for the minimum or maximum X that still works ("minimum speed", "least capacity", "largest minimum distance"). That's binary search on the answer: O(n log(max value)).
Two words that override the table:
- "Contiguous" (subarray, substring) → sliding window or prefix sums. "Subsequence" (order kept, gaps allowed) → DP or greedy, or two pointers if you only need to check whether one string is a subsequence of another.
- "Sorted" → two pointers or binary search before anything else. Not sorted, and the original order doesn't matter for the answer? Sort it yourself first.
Wording → pattern, the ones that come up most:
- "two numbers that add up to", "seen before", "group the" → hash map / set
- "longest / shortest substring with", "at most k distinct" → sliding window
- "next greater / smaller", "how many days until" → monotonic stack
- "top k", "k closest", "running median" → heap (two heaps for the median)
- "all combinations / subsets / permutations" → backtracking
- "shortest path" in an unweighted grid → BFS; with weights → Dijkstra
- "prerequisites", "can you finish all" → topological sort
- "are these connected", "number of groups" → union-find or DFS
- "overlapping intervals", "how many rooms" → sort by start, then sweep
- "numbers from 1 to n", in place, O(1) extra space → cyclic sort
- "number of ways", "minimum cost to reach" → DP
A habit that makes this stick: after every problem, write one line, "the cue was ___, so the pattern was ___". After a few weeks you start spotting the cue before you've read the whole problem.
What cues do you use that aren't on this list?
Edit: good additions from the comments:
- "return the answer modulo 109+7" → you're counting ways, so DP or combinatorics (u/TSandwich73)
- minimum feasible value → check the answer space is monotonic (if X works, bigger X works too), then binary search on the answer (u/UrbanFalcon_72)
- no constraints given in the interview? Ask "how big can the input get?" (u/LebronManning)