Constraints decide the approach

On LeetCode and on the A2Z sheet, the limits sit at the bottom of the problem, in small type. Most beginners skip them.

They are the biggest hint on the page. The limits tell you how fast the answer must be, before you have a single idea.

From n to the Big O you need

In the last lesson you found the limits in a statement. In this lesson you use them. The method has three steps:

1. Find the largest n in the limits.
2. Look up the slowest Big O that still fits in about 10⁸ steps.
3. Think only about ideas with that Big O or faster.

The lookup table:

Read it from the left. Find your n, and the row tells you how much work you are allowed.

Small n is a hint, not a gift

Compare the same four answers at two sizes:

At n = 20, an exponential answer is about a million steps. The problem setter picked a tiny n on purpose. When n is 20 or less, the intended answer usually tries every subset.

At n = 100,000, the same idea would never finish. Even n² is 10¹⁰ steps.

When n is huge, you cannot even loop

The bar says "tight" for O(n). That means about 10⁹ steps, roughly 10 seconds at 10⁸ per second. Against a 1 second limit, treat it as too slow.

So when n reaches 10⁹, look for:

• a formula: the sum 1 + 2 + ... + n is n × (n + 1) / 2, one step;
• a binary search over the answer: about 30 halvings for 10⁹.

When numbers get too big

The limits also give the range of each value, such as -10⁹ ≤ nums[i] ≤ 10⁹. That range tells you whether your sums and products still fit in a number.

Each language has its own limit:

• Java: an int ends at 2³¹ − 1 = 2,147,483,647, about 2.1 × 10⁹. Past that, it overflows. A long goes to about 9.2 × 10¹⁸.
• Python: an int has no limit. It grows as large as the value needs, so it never overflows.
• TypeScript: a number holds every integer exactly up to Number.MAX_SAFE_INTEGER, about 9 × 10¹⁵. Past that, it rounds the last digits.

Java and TypeScript give a wrong answer at that point. Neither one warns you.

Which results each type holds exactly:

A Python int is exact in every row.

Here is the silent error, and the fix:

JavaPythonTypeScript

int a = 999_999_999;
System.out.println(a * a % 1_000_000_007); // 808348673: wrong
System.out.println((long) a * a % 1_000_000_007); // 64: right

The product a * a is about 10¹⁸. Each language handles it differently:

• In Java, two ints multiply as an int, so the product overflows before % runs. Cast one side to long first: (long) a * a.
• In Java, long c = a * a; is still wrong. The product overflows as an int, and only then becomes a long.
• In Python, the product is exact. Very large ints cost a little more time, but they are never wrong.
• In TypeScript, the product is above the safe limit, so its last digits are already wrong. A BigInt stores any integer exactly. It is slower, and 1n + 1 throws a TypeError: you cannot mix it with plain numbers.

Use long in Java when a value can pass 2.1 × 10⁹. Use BigInt in TypeScript only when it can pass 9 × 10¹⁵.

Two more signals from the same line:

• "Return the answer modulo 10⁹ + 7". The real answer is huge. Take % after every step, not once at the end.
• Sums of many values. 10⁵ values up to 10⁹ add up to 10¹⁴. In Java, keep that sum in a long, as the solutions on the sheet do.

Memory has a limit too

Many judges allow 256 MB. A Java long and a TypeScript number take 8 bytes each, and a Java int takes 4.

• An array of 10⁶ numbers is about 8 MB: fine.
• An n × n table with n = 10⁴ is 10⁸ cells, about 800 MB: too much.

In Python, each list slot points to an int object, so a number costs about 36 bytes. A list of 10⁶ ints is about 36 MB. Still fine, but the n × n table is far out of reach.

So O(n) extra memory almost always fits. O(n²) memory only fits for n up to a few thousand.

Read the limits first: Koko Eating Bananas

Here is a real problem from the sheet. Read the limits before you think about a solution.

Now read the limits, one at a time:

1. n ≤ 10⁴. Even O(n²) fits. The number of piles is not the problem.
2. nums[i] ≤ 10⁹. The speed k can be any value from 1 to 10⁹. That range is the real input size.
3. Checking one speed means adding up the hours for every pile: O(n).
4. Trying every speed costs 10⁹ × 10⁴ = 10¹³ steps. Far too slow.
5. A faster speed never needs more hours. So binary search the speed: about 30 checks instead of 10⁹.
6. Overflow check. At speed 1, the hours can reach 10⁴ × 10⁹ = 10¹³. That passes a Java int, so count the hours in a long. A Python int and a TypeScript number hold it exactly.

You picked the approach without writing any code. The binary search on answers chapter writes it.

Limits are pattern signals

In the last lesson, words in the statement pointed to patterns. The limits point too. Put the two together and most problems narrow to one or two ideas.

The habit: limits first, then ideas. It takes ten seconds, and it removes most wrong roads before you walk them.

take U forwardYouTube

Read more

• Time complexity in the USACO Guide, with its own table of input sizes and the Big O each allows
• Number.MAX_SAFE_INTEGER on MDN
• BigInt on MDN, with what you can and cannot mix
• Koko eating bananas on takeUforward, to read the limits yourself

Next: the language toolbox. Pick the lesson for the language you code in, Java, Python or TypeScript, and learn what each operation costs.