What the Constraints Tell You

This is the highest-value habit in the course, and it takes five seconds. Read the constraints before you think about the algorithm, because they tell you the complexity class of the answer.

Problem setters calibrate their limits so the intended solution runs in time and the obvious slow one does not. If you know the budget, you can work backwards from the limit to the shape of the solution — and from the shape to two or three candidate patterns. That is a large head start before you have understood the problem fully.

The logic: a budget of about 10⁸ steps

Take the working figure from the previous lesson: about 100 million simple steps per second. A judge usually allows one or two seconds. So the intended solution does at most around 10⁸ steps. Now plug in the limit.

If n ≤ 10⁵ and you have an O(n²) idea, that is 10¹⁰ steps — a hundred times over budget. If you have an O(n log n) idea, it is about 1.7 × 10⁶ steps — comfortably inside. You have not written a line of code, and you already know which idea to pursue.

The table to memorise

The numbers come straight from the budget. 10! = 3,628,800. 2²⁰ is about a million. 500³ = 1.25 × 10⁸. 5,000² = 2.5 × 10⁷. 10⁶ × log₂(10⁶) is about 2 × 10⁷. The borders are soft — n ≤ 11 (about 40 million permutations) is usually still fine — but the order of the rows never changes.

Read the table in the direction that matters. n ≤ 20 is not a small input; it is a licence to be exponential. A candidate who sees n ≤ 20 and hunts for a clever linear solution is solving the wrong problem.

When there is more than one variable

Many problems have two sizes. A grid is m × n. Two strings have lengths m and n. A "top k" problem has n items and a k.

Multiply them the same way. If both strings can be 1,000 characters, an O(m × n) table is 10⁶ cells — fine. If one is 10⁵ and the other 10⁵, the same table is 10¹⁰ — not fine, and the problem wants something linear. For "k ≤ n ≤ 10⁵", an O(n log k) heap solution and an O(n log n) sort are both inside the budget; the interviewer may still ask for the heap because it uses O(k) memory instead of O(n).

When n is a value, not a length

Some constraints bound a value: "1 ≤ n ≤ 10⁹, return the number of trailing zeros of n!", or "speeds range from 1 to 10⁹". There is no array of 10⁹ elements to walk through. Anything linear in that value is 10⁹ steps, which is at the edge of the budget in a compiled language and far past it in Python.

So a large value points at logarithmic or square-root work: binary search over the range of possible answers, halving, digit-by-digit maths, or a loop up to √n (about 31,623 steps for 10⁹). This is the single most useful distinction in the table, because it changes the whole family of patterns you consider.

Worked reads

"2 ≤ numbers.length ≤ 10⁵; return the two positions whose values add up to the target." 10⁵ rules out O(n²) — that is about 5 billion pairs. You need O(n) or O(n log n). That means a hash map from the Hash Maps and Sets section, or, if the array is sorted, converging two pointers from the next section.

"1 ≤ piles.length ≤ 10⁴, 1 ≤ piles[i] ≤ 10⁹; find the smallest eating speed that finishes all piles in h hours." The answer is a speed between 1 and 10⁹ — a value. Checking one speed takes O(n). Trying every speed is 10⁹ × 10⁴ steps. Binary search over the speed is about 30 checks of 10⁴ each: 3 × 10⁵ steps. The constraint named the pattern: binary search on the answer.

"1 ≤ n ≤ 16; return every valid arrangement." "Every" plus n ≤ 16 is backtracking. Do not look for a formula; the output alone may be exponential.

"1 ≤ text.length ≤ 5 × 10⁴; find the longest stretch without a repeated character." O(n²) is 2.5 × 10⁹ — too slow. "Stretch" means contiguous. A linear-time sliding window is the target.

The other things constraints tell you

Constraints also settle edge cases that would otherwise cost you interview time:

• 0 ≤ numbers.length — the empty array is legal, so handle it. 1 ≤ means you may skip that check, but say so.
• -10⁴ ≤ numbers[i] ≤ 10⁴ — negatives exist. A sliding window on sums relies on sums only growing as the window grows, and negatives break that. Prefix sums with a hash map are the usual repair.
• "All values are distinct" — removes duplicate handling from 3Sum-style problems and from binary search.
• 0 ≤ values ≤ 100 — a small value range means a counting array of 101 slots can replace sorting or a hash map.
• "Return the answer modulo 10⁹ + 7" — the count is astronomically large. That almost always means a counting dynamic programme.
• Values up to 10⁹, sums of many values — a sum can pass 2³¹. Python integers never overflow, but Java and C++ ones do; mention it if the interviewer works in those languages.

When the interviewer gives no constraints

In a live interview the problem often arrives as two spoken sentences with no limits at all. Ask: "Roughly how large can the input get — thousands, or millions?" and "Can it be empty? Can values be negative?" If the interviewer says "you decide", state your assumption out loud: "I'll assume up to about 10⁵ elements, so I'll aim for O(n log n) or better." That one sentence shows the habit, and it tells the interviewer what you are about to optimise for.

Check your understanding

0 of 3 answered

1.A problem says 1 ≤ n ≤ 18 and asks for the number of ways to choose a subset with some property. What should you conclude first?

AYou need an O(n) formula, because 18 is tinyBTrying all 2¹⁸ (about 260,000) subsets is affordable, so enumeration or backtracking is a fair starting pointCYou must use dynamic programming, because it asks for a countDThe constraint tells you nothing until you know the values

2.1 ≤ capacity ≤ 10⁹ and 1 ≤ packages.length ≤ 5 × 10⁴. Checking one capacity takes a single pass over the packages. What is the most promising plan?

ATry every capacity from 1 up to 10⁹BSort the packages and use two pointersCBinary search over the capacity, doing one O(n) check per step

3.The constraints say -10⁴ ≤ numbers[i] ≤ 10⁴. Which technique does this most directly warn you about?

ABinary search on a sorted arrayBA sliding window that grows and shrinks based on the running sumCA hash map from value to indexDSorting the array