Reading Constraints
Beginner · 25 min read · Data Structures Basics, Putting It Together
The problem's biggest hint: target complexity from n, int vs long, negatives, value ranges, memory, recursion depth and modulo 10^9 + 7.
Every problem ends with a few lines like 1 <= n <= 10^5. Most people skim them. They are the biggest hint in the problem: they tell you how fast your solution must be, which data type to use, which tricks are safe and which edge cases the tests will throw at you. You can do all of this before writing a line of code.
Think of the price filter on a shopping site. Set a budget of ₹2,000 and most of the catalogue disappears before you start browsing. The constraints are the problem's budget. Read them first, and most of the approaches you could try disappear too.
What a constraint block tells you
A constraint is a limit on the input. Each line answers one of five questions:
The golden rule: about 10^8 operations a second
A judge (or an interviewer judging by eye) gives you about 1 to 2 seconds. In that time, Java or C++ can do roughly 10^8 simple operations: additions, comparisons, array reads. That is 10 crore. So:
How far each complexity reaches
Turn the rule around: for each complexity, what is the largest n that fits in 10^8? The bars below answer that. Pick an n and see which complexities still reach it.
Your turn: decode a real problem
You now have the rule and the table. Here is a real problem from the course. You don't need to solve it, just read its constraints.
One problem, four constraint sets
The same question can need four different algorithms. Here it is: can you choose some numbers from the array that add up to exactly target?
Ruling out approaches: a worked example
Find two numbers in the array that add up to target, with 1 <= n <= 10^5:
Value constraints: data types, negatives, ranges
n tells you about speed. The range of each value tells you which data type to use and which tricks are safe.
Structure words that are constraints too
Some lines are not numbers but still decide the approach. The Pattern Picker covers the wording of the question itself; these are the ones found among the constraints:
Memory limits
Judges usually allow about 256 MB. LeetCode doesn't print a limit, but huge tables still fail there. Know the sizes:
Modulo 10^9 + 7
Some answers are too big for any type, like the 209-digit number of ways to climb 1,000 stairs. So the problem asks only for the remainder after dividing by 10^9 + 7. Every number you store then stays below about 10^9.
Constraints are your test plan
The constraints also list the tests the judge will run. Every bound is an edge case waiting to be tried:
When the interviewer gives no constraints
Interview problems are often stated loosely on purpose. Asking for the constraints is part of the test. Ask:
Worked examples from the problem set
Each row is a real problem from this course's judge, with its constraints exactly as the judge uses them:
The routine
Run these checks before you write code. They take a minute and save the forty minutes of writing the wrong solution:
Interview questions
- The constraints say n is at most 10^5. What complexity do you aim for, and why?
- Why might a problem have n at most 20, when it could easily allow more?
- Values go up to 10^9 and n up to 10^5. Which variables need to be long?
- Why is the modulus usually 10^9 + 7?
- An O(n²) algorithm is fast enough for n = 10^4, but your solution runs out of memory. What happened, and how do you fix it?
- When would you replace a recursive DFS with an iterative one?
Practice
Decide the approach from the constraints alone, then open the answer.
Further reading
Key takeaways
- Read the constraints before the examples: they give the target complexity, the data type, the techniques and the edge cases.
- Budget about 10^8 simple operations a second (10^7 for hash-map-heavy work or Python), and multiply all the sizes involved.
- n ≤ 20 invites subsets, n ≤ 500 allows O(n³), n ≤ 5,000 allows O(n²), n ≤ 10^5 needs O(n log n), and n ≤ 10^9 means binary search or maths.
- Sums, products and pair counts outgrow int long before the inputs do: use long and cast before multiplying.
- Negatives break sliding windows and Java's % and /; small value ranges invite counting arrays; huge ranges with few values invite compression.
- Memory is a second budget: an n × n table at n = 10^4 is 400 MB, and deep recursion overflows Java's stack.
- Modulo 10^9 + 7: long, mod at every step, add MOD after subtracting, divide with the inverse, never compare after the mod.