"n <= 20" is the problem telling you the answer is exponential

i lost twenty minutes of an interview looking for a solution that did not exist.

graph problem, find the shortest walk that visits every node. i started hunting for something polynomial — a clever greedy, a topological trick, some DP over edges. i was convinced exponential meant wrong, because in my head exponential always meant "you missed something." the interviewer let me flail for a while and then said "how big is the graph?"

twelve nodes. maximum twelve.

that's LC 847 and the intended answer is BFS over (current node, bitmask of visited) — O(2^n · n) states, flatly exponential, and correct. the bound was in the problem the whole time. n ≤ 12 is not a detail about the input. it's the setter telling you that 2^n is allowed, which means 2^n is probably required, because nobody caps n at twelve for a linear algorithm.

i had solved 400+ problems at that point and had genuinely never once read the constraints block before writing code. i treated it like the terms and conditions under the examples.

why this is actually the most information-dense part of any problem

the statement is written to be ambiguous. the examples are written to be small. but every single number in the constraints block is a decision someone made after they knew the answer, specifically to permit the intended complexity and forbid everything slower.

so the bound is a filter over the algorithm space. you can apply it before you've had a single idea.

assume roughly 10^8 simple operations per second — that's the standard working figure for a compiled language, and interpreted ones are meaningfully slower, but the table below is coarse enough that it doesn't matter.

n <= 10-11        O(n!)              permutations, brute-force assignment
n <= 20-25        O(2^n), O(2^n · n) subset enumeration, bitmask DP
n <= 100-500      O(n^3)             floyd-warshall, interval DP, matrix chain
n <= 2,000-5,000  O(n^2)             2D DP: edit distance, LCS, LIS
n <= 10^5-10^6    O(n log n)         sort, heap, binary search, segment tree
n <= 10^7-10^8    O(n)               single pass, two pointers, prefix sums
n >= 10^9         O(log n) or O(1)   binary search the answer, closed-form math

the two rows people misread are the top and the bottom. small n is not "easy problem," it's permission to be exponential. and an absurd n like 10^9 is not "impossible problem," it usually means there is no array at all and you're searching a numeric range.

reading it backwards on problems you've already solved

this is where it stopped being a trick and started being useful. every one of these is a problem most people here have done, with the real constraint attached.

subsets — nums.length <= 10. 2^10 is 1024. the bound is a permission slip: enumerate every subset, don't look for anything cleverer. ten is not an accident, it's the setter making sure 2^n fits.

combination sum — candidates.length <= 30, target <= 40. thirty candidates with unbounded reuse would explode. the thing keeping it tractable is the target bound, not the array bound. that tells you target is the axis you recurse and prune on.

coin change — coins.length <= 12, amount <= 10^4, coins[i] <= 2^31 - 1. this one is beautiful once you see it. amount is capped at ten thousand, so a DP table over amount is 12 × 10^4 ≈ 10^5, trivially fine. and coin values go up to two billion, which is the setter explicitly telling you do not index anything by coin value. the two bounds together hand you the exact shape of the DP table. i built that table for months without ever knowing why it was that way round.

partition equal subset sum — nums.length <= 200, nums[i] <= 100. why would anyone bound the individual values? because 200 × 100 caps the total sum at 20,000, so the target is at most 10,000, so an O(n · target) subset-sum DP is 2 × 10^6 and fits. nobody bounds nums[i] for fun. a second, tighter bound on the values is almost always the dimension of your DP table.

target sum — nums.length <= 20, nums[i] <= 1000. twenty says 2^20 ≈ 10^6 brute force will pass. the value bound says a DP over reachable sums also works. both are open, which is why this problem has two accepted solutions and why the constraint block is a menu here rather than an order.

sort colors — nums[i] is 0, 1, or 2. a bounded alphabet rather than a bounded size. that's never asking for a comparison sort. three distinct values means counting or a three-way partition in one pass.

koko eating bananas — piles.length <= 10^4, piles[i] <= 10^9. the array is small and the values are enormous, which is the tell that you binary search the value space, not the array. 10^4 · log(10^9) ≈ 3 × 10^5. every "minimum speed / minimum capacity / minimum days" problem has this exact fingerprint: a small n next to a huge value range. once you can spot that shape, koko and ship-packages-in-d-days and split-array-largest-sum are visibly one problem.

the direction nobody expects: constraints also tell you when to stop optimising

longest increasing subsequence — nums.length <= 2500.

2500² is 6.25 million. the O(n²) DP passes comfortably. the O(n log n) patience-sorting version is real and it's a nice thing to know, but the bound is quietly telling you it is not required.

i have watched people (me) spend fifteen minutes in an interview trying to reconstruct the binary-search version from memory, get it subtly wrong, and run out of clock — on a problem where the straightforward quadratic DP was always going to be accepted. the constraint said so.

so the inference runs both ways. small bound means you may be exponential. loose bound means you may be quadratic, and hunting for better is a time-management mistake, not diligence. say it out loud in an interview: "n is 2500 so O(n²) is fine here, i'll mention the O(n log n) approach at the end if we have time." that sentence is pure signal — it shows you're budgeting, and it protects you if you never get there.

two things i got wrong even after i started reading the block

1. multiply the constraints, don't read them one at a time. if there are 10^4 queries and n is 10^4, an O(n) answer per query is 10^8 total and you will time out with a "correct" solution. the budget is queries × n, and the moment you see two large bounds multiplied together, the problem is asking for preprocessing — prefix sums, a segment tree, precomputed answers — not a faster inner loop. i lost a contest problem to exactly this and spent an hour optimising the wrong loop.

2. "n is large" doesn't always mean O(n log n). sometimes it means O(n), and the log is the thing you can't afford. sorting is usually the first thing to try and occasionally the exact thing the bound forbids.

how this transfers to an actual interview, which is the whole point

live interviewers don't print a constraints block. so you have to go get it, and asking is the move — it reads as experience rather than stalling, because these four questions are the only ones whose answers change your algorithm:

1. "roughly how large is n?" picks your row in the table above.
2. "are the values bounded, or can they be arbitrary?" decides whether counting sort, bucketing, or a DP indexed by value is on the table.
3. "is the input sorted, or is there any structure i can rely on?" the difference between a hashmap and two pointers, and between a scan and a binary search.
4. "how many times does this get called?" the queries × n question. it's the one that turns a coding problem into a preprocessing problem, and almost nobody asks it.

and if the answer to the first one is "assume it's enormous, it won't fit on one machine" — that's a different interview and a different toolkit, but at least you found out in minute two instead of minute thirty.

the reason this scores well is that you're not asking for a hint. you're demonstrating that you know the bound determines the algorithm, which is the same reasoning you'd use choosing a data structure in real code. interviewers can tell the difference between "help me" and "let me scope this."

the practice change, which costs nothing

read the constraints block first. before the statement, before the examples.

then predict the complexity out loud, in one line — "n is 10^5 so i need n log n at worst" — and only then read what the problem actually wants.

thirty seconds per problem. what it buys you is that you never again spend twenty minutes looking for a polynomial solution to a problem that was designed to be exponential, and you never again burn your remaining clock optimising something the setter already told you was fast enough. after a few weeks the row in the table comes up before you've finished reading the bound, and you start every problem having already eliminated most of the wrong answers.

the reframe

the statement tells you what to compute. the constraints tell you how. one of those is written in prose that's trying to be interesting, and the other is a table of numbers chosen by someone who already had the solution in front of them.

i spent 400 problems reading only the interesting one.

i keep every problem's constraints on the same page as the complexity and the pitfalls on systemcraft(Google it) — 390 problems, each with the bound, the approach that bound implies, and solutions in python java c++ and js, plus 16 pattern pages so you can go from "n is 10^5, i need n log n" to the shortlist of patterns that live at that complexity. free, no signup to read.

what's a problem where the constraint gave the whole thing away for you once you noticed? mine was coin change — coins[i] <= 2^31 - 1 sitting right there telling me for months not to index by coin value, and me never once asking why that line existed.