ASAPUtils
Read the constraints first
Before you think about an algorithm, look at how big n gets. That single number tells you
what shape the answer has to be, and it saves you from spending ten minutes on an approach that
was never going to fit.
| n up to | Allowed complexity | Typical approach |
|---|---|---|
| 10–12 | O(n!) | Permutations, brute-force backtracking |
| 15–22 | O(2ⁿ) | Subsets, bitmask DP |
| 100 | O(n³) | Floyd–Warshall, triple loop, interval DP |
| 1,000–5,000 | O(n²) | 2-D DP, all pairs |
| 10⁵–10⁶ | O(n log n) | Sort, heap, binary search, one pass with a map |
| 10⁷–10⁸ | O(n) | Single pass, prefix sums, counting |
| 10⁹+ | O(log n) or O(1) | Binary search on the answer, math, bit tricks |
If your idea is one tier slower than the table allows, it’s the wrong idea. Stop coding and think again. This is a two-second check that saves entire interviews.
Used in reverse it’s even better: n ≤ 10⁵ and you need something better than the obvious
O(n²)? The table says O(n log n) — which means sorting, a heap, or binary search. You’ve
narrowed the search space before you’ve had a single idea.
Estimating in five seconds
- Loop over the input once → O(n)
- Nested loop over the input → O(n²)
- Halve the search space each step → O(log n)
- Sort → O(n log n)
- For each element, do a log-n operation (heap push, binary search) → O(n log n)
- Recursion branching two ways, depth n → O(2ⁿ)
- Recursion on a tree, touching each node once → O(n)
Two rules people get wrong:
Not every nested loop is O(n²). The monotonic-stack pattern has a while inside a for,
but each element is pushed and popped at most once, so the total is O(n). Count total work,
not loop nesting.
Constants and lower terms drop, but the reason matters. O(2n) is O(n). Still, in an interview say “two passes, so O(n)” rather than “O(n)” — it shows you know what you built.
Space complexity
Count what you allocate that grows with the input:
- A hash map holding up to n entries → O(n)
- A 2-D DP table over two strings → O(n·m)
- A few pointers → O(1)
- Recursion depth counts. A DFS on a skewed tree of n nodes uses O(n) stack. Saying “O(1) space” about a recursive solution is a common and noticeable error.
Space is where you can often make a second improvement after you’ve got the time down — most 1-D DP solutions collapse from O(n) to O(1) once you see that the recurrence only looks back a fixed number of rows.
What to say in an interview
State it, and give the reason in the same breath:
“Sorting is O(n log n), then the two-pointer scan is O(n), so it’s O(n log n) overall. Space is O(1) beyond the sort.”
“Each element is pushed and popped at most once, so even though there’s a while loop inside the for loop, it’s O(n) total.”
The second sentence is what separates someone who understands their solution from someone who memorised it.
The three mistakes
- Not reading the constraints. You lose the free hint about what’s expected.
- Forgetting recursion stack space. It’s real memory and interviewers notice.
- Counting loop nesting instead of total work. This makes you reject correct O(n) solutions like the monotonic stack because they “look” quadratic.
Done when
You can look at any snippet and state its time and space complexity in five seconds, and you
can go the other way — read n ≤ 10⁵ and immediately say “O(n log n) or better, so probably
sorting, a heap, or binary search.”