Reading the constraints backwards

The largest input a problem allows is a message about which technique is expected. Learn to read it before you write anything.

Every problem worth solving comes with limits: the list has at most this many entries, the values go up to that. Those numbers look like a detail about testing. They are usually the strongest hint available about what kind of solution is wanted, and reading them first saves writing the wrong thing.

The reasoning runs backwards from a budget. A current machine executes very roughly $10^8$ to $10^9$ simple operations per second, so a program with a one second budget can afford about $10^8$ operations. Work out what each growth class evaluates to at the given size, and cross off everything above the budget.

At $n = 10^5$, a quadratic solution needs $10^{10}$ operations, which is around a hundred seconds. An $n \log n$ solution needs about $1.7 \times 10^6$, which is instant. There is no tuning that closes that gap, and knowing it before you start is the difference between an hour of profiling and a different algorithm.

The table to keep in your head

The rows are not laws. They are what the person who set the limit was thinking. If the stated limit is $n \le 2 \times 10^5$, they have deliberately excluded $n^2$, which would be $4 \times 10^{10}$, and left room for $n \log n$, which is about $3.5 \times 10^6$. If they had wanted a quadratic solution they would have written $n \le 3000$.

The other numbers in the constraints

The size of the input is not the only limit worth reading. Several others change what is possible.

• The range of the values. If the entries are at most $10^6$, an array with one slot per possible value is affordable and turns many searches into a direct lookup. If they are at most $10^{18}$, it is not.
• The memory limit. A table of $n$ by $n$ numbers at $n = 10^5$ is $10^{10}$ entries. At 8 bytes each that is 80 gigabytes, so the algorithm is impossible for reasons that have nothing to do with time.
• How many test cases there are. A limit of $n \le 10^5$ with up to $10^4$ separate cases is not a promise of $10^5$; look for a stated bound on the total, and if the total is what is bounded, budget against that.
• Whether the values can be negative, zero, or repeated. These rarely change the growth and very often change whether your procedure is correct.

Here is a worked reading. A problem says: up to $2 \times 10^5$ items, each with a weight up to $10^9$, and you must report something about every pair. The pair count alone is about $2 \times 10^{10}$, so the answer cannot be produced by examining pairs one at a time. The weights being up to $10^9$ rules out an array indexed by weight, and also warns that a sum of weights can reach $2 \times 10^{14}$, which overflows a 32-bit integer and needs a 64-bit one. Both conclusions came from the constraints, before any algorithm existed.