The constraint list is not fine print. It is the interviewer telling you which complexity they expect, and often which pattern to use. Read it first.
Candidates skip straight to the examples. The constraints are more useful. “n ≤ 20” means exponential is fine and they want backtracking. “n ≤ 10⁵” means anything quadratic will fail. Reading the bound converts a guess into a decision.
So the working rule is: estimate the operation count as a function of n, plug in the largest n in the constraints, and check it lands under about 10⁷. That is the entire method.
| Language | Rough ops per second | Implication |
|---|---|---|
| C++ or Rust | 10⁸ | The number most problem setters design against. |
| Java or Go | 10⁸ to 5 × 10⁷ | Close enough to C++ for most bounds. |
| Python | 10⁷ | One order of magnitude tighter. Assume this. |
| Python with numpy or built-ins | 10⁸ | Work pushed into C, such as sum, sort, join. |
n = 10⁵ and your solution is O(n log n), that is about 1.7 million operations, comfortably fine. If it is O(n²), that is 10¹⁰, which is hours. You can tell the interviewer your approach will not work before writing it, which is exactly the judgement they are looking for.This is the table to memorise. Find the largest n in the constraints, read across.
| n up to | Expected complexity | What that usually means |
|---|---|---|
| 10 – 12 | O(n!) | Permutations. Backtracking, travelling salesman by brute force. |
| 15 – 20 | O(2ⁿ) or O(2ⁿ · n) | Subsets, bitmask DP. The clearest signal in the whole table. |
| 50 – 100 | O(n⁴) | Four nested loops, or interval DP over pairs. |
| 500 | O(n³) | Floyd-Warshall, matrix chain, some 2D DP. |
| 5,000 | O(n²) | Two nested loops, DP over pairs of indices, edit distance. |
| 10⁵ (100,000) | O(n log n) | Sorting, heaps, binary search per element, interval sweeps. |
| 10⁶ (1,000,000) | O(n) | One pass. Windows, prefix sums, monotonic stacks, counting. |
| 10⁸ and above | O(log n) or O(1) | Binary search on the answer, or a closed-form formula. |
n ≤ 20 almost always means subsets or bitmask, because 2²⁰ is about a million and 2³⁰ is a billion. And n = 10⁵ almost always means sort it or use a hash map, because n² is 10¹⁰ and n log n is under 2 million. Recognising these two on sight saves five minutes of thinking.Constraints tell you more than the complexity. Several phrasings map almost one-to-one onto a pattern.
| Constraint text | What it is telling you |
|---|---|
| “Solve in O(1) extra space” | No hash map, no copy. Think two pointers, in-place swaps, or Floyd. |
| “Do not modify the input” | Rules out sorting and in-place tricks. Often points at cycle detection or binary search on the value range. |
| “Must be O(log n)” | Binary search. Not a hint, an instruction. |
| “The array is sorted” | Two pointers or binary search. Sortedness is never mentioned by accident. |
| “Values are in the range 1 to n” | Cyclic sort, or use the array itself as a hash table. |
| “Values may be negative” | Kills the sliding window. Think prefix sums. |
| “All values are positive” | Enables the window, and enables greedy shrinking. |
| “Return any valid answer” | No tie-break needed. Often topological sort. |
| “Answers fit in a 32-bit integer” | Irrelevant in Python. Say so, since it is aimed at other languages. |
| “Queries arrive one at a time” | A dynamic structure. Union-Find, a heap, or a prefix structure. |
| “1 ≤ k ≤ n” with n large and k small | A size-k heap, giving O(n log k) not O(n log n). |
| “The string contains only lowercase letters” | The alphabet is 26, so a fixed-size array works and the space is O(1). |
n gets, ask. Every one of those changes the answer, and asking is scored as a positive, not as ignorance.Three rules cover almost every case.
| Rule | Meaning |
|---|---|
| Sequence adds | Two loops one after another is O(n) + O(n) = O(n). Not O(n²). |
| Nesting multiplies | A loop inside a loop is O(n) × O(n) = O(n²). |
| The biggest term wins | O(n² + n log n + n) = O(n²). Drop constants and lower terms. |
def not_quadratic(nums: list[int]) -> int:
"""Two pointers, or a monotonic stack: nested syntax, linear cost."""
left = 0
total = 0
for right in range(len(nums)):
while left < right and nums[left] < nums[right]:
left += 1 # left only ever moves FORWARD
total += 1
return total
left starts at 0, only increases, and never passes n. So the inner while runs at most n times across the entire outer loop, not n times per iteration. Total: O(n). This amortised argument is the same one behind the sliding window, monotonic stacks, and cyclic sort. Interviewers ask about it directly, so have the sentence ready.def secretly_quadratic(items: list[int]) -> list[int]:
"""One loop, but each body statement is O(n)."""
out: list[int] = []
for item in items:
if item in out: # O(len(out)) list scan
continue
out.insert(0, item) # O(n) shift
return out
No nesting in sight, and it is O(n²). The lesson: look inside the loop body, not just at the loop headers. in on a list, insert(0, ...), slicing, min, max, sum and string concatenation are all linear.
| Recurrence | Solves to | Example |
|---|---|---|
| T(n) = T(n/2) + O(1) | O(log n) | Binary search |
| T(n) = T(n/2) + O(n) | O(n) | Quickselect, average case |
| T(n) = 2T(n/2) + O(1) | O(n) | Tree traversal |
| T(n) = 2T(n/2) + O(n) | O(n log n) | Merge sort, quicksort |
| T(n) = 2T(n-1) + O(1) | O(2ⁿ) | Naive Fibonacci, subsets |
| T(n) = n · T(n-1) | O(n!) | Permutations |
The difference between the second and fourth rows is the whole reason quickselect beats quicksort for finding one element: recursing into one half instead of both.
Concrete numbers, so the abstraction has weight. Each cell is the operation count.
| n | log n | n | n log n | n² | 2ⁿ |
|---|---|---|---|---|---|
| 10 | 3 | 10 | 33 | 100 | 1,024 |
| 100 | 7 | 100 | 664 | 10⁴ | 10³⁰ |
| 1,000 | 10 | 10³ | 10⁴ | 10⁶ | beyond counting |
| 10⁵ | 17 | 10⁵ | 1.7 × 10⁶ | 10¹⁰ | — |
| 10⁶ | 20 | 10⁶ | 2 × 10⁷ | 10¹² | — |
Three readings worth internalising.
log n is tiny. A billion elements is 30 steps. Never worry about a log factor.n log n is close to n. At n = 10⁵ the factor is only 17. Do not contort a solution to remove a sort.n² falls off a cliff. Fine at 5,000, hopeless at 10⁵. That is the line the table is really drawing.int in a list costs roughly 28 bytes for the object plus 8 for the pointer, so a list of 10⁶ integers is around 40 MB, not 8 MB. A list of 10⁷ is uncomfortable. This surprises people coming from C++.| Structure | Rough bytes per element | 10⁶ elements |
|---|---|---|
list of small ints | ~36 | ~36 MB |
set or dict of ints | ~100 | ~100 MB |
list of tuples of two ints | ~130 | ~130 MB |
array.array("i") | 4 | 4 MB |
bytearray | 1 | 1 MB |
Conventions for what counts as extra space:
n answers is still “O(1) extra space”.Say four things, in this order. It takes fifteen seconds and it closes the question cleanly.
| Say | Example |
|---|---|
| 1. The time, with the reason | “O(n log n). The sort dominates, the sweep after it is linear.” |
| 2. The space, and what is in it | “O(n) for the hash map. O(1) extra if you do not count the output.” |
| 3. What the variables mean | “n is the number of intervals, not the length of the timeline.” |
| 4. Whether it is worst or average case | “Average O(n). Worst case O(n²) if the hash degenerates.” |
k is. Problems with two inputs need both: string matching is O(n + m), not O(n). Being sloppy here is one of the easiest ways to look less careful than you are.list.append. Average case O(1) means it usually holds, as with a dict lookup, and an adversary could break it. Using the right word is a small, visible signal.n ≤ 20 means subsets or bitmask. n = 10⁵ means n log n at worst. Two rows, huge payoff.