Read constraints to pick the target complexity

Every online-assessment problem ends with a block of limits, and many people skim past it to start coding. That block is the most direct hint you will get: it tells you how fast the solution must be before you have thought of one. In a live round the limits are often missing, so you ask for them during the clarifying step. This lesson reads limits the way you would under time pressure, maps them to a target complexity and the patterns that usually reach it, and shows how to check a plan by timing it rather than trusting a rule of thumb.

Read the block before the story

Here is an original constraints block of the kind that ends a problem statement:

Read it in this order, and say the conclusions aloud in a live round:

1. The largest size. n can be 200,000, so an algorithm that looks at every pair makes about n²/2 = 2 × 10¹⁰ comparisons. That rules out O(n²) before you write anything.
2. The time limit and your language. Multiply the seconds by the number of simple steps your language does per second. A common planning figure is about 10⁸ a second for compiled code and about 10⁷ for CPython; the DSA track’s lesson on growth rates measures where those figures come from. Two seconds in Python is then a budget of a few times 10⁷ steps.
3. The other numbers. The values reach 10⁹ in size, q queries come on top of n, and the modulus says the true answer is too big to print. Each of these changes the plan, as the clues below show.

Then compare the step count of each idea with the budget. Here, n log₂ n is about 3.5 million for n = 2 × 10⁵, well inside even the Python budget, so the target is O(n log n) or better, plus a cheap answer to each query.

A target for each size

This list is an estimate, not a law: it assumes a budget of roughly 10⁸ simple steps, about a second of compiled code. Python has about a tenth of that, which moves each boundary down (for O(n²), from about 10,000 to about 3,000).

• n up to about 10: O(n!) fits, so you can try every order, with backtracking.
• n up to about 20: O(2ⁿ · n) fits, so you can try every subset, with bitmasks or backtracking.
• n in the hundreds: O(n³) fits: three nested choices, such as interval dynamic programming.
• n in the thousands: O(n²) fits: every pair, or a two-dimensional table.
• n from 10⁵ to 10⁶: aim for O(n log n): sorting, heaps, binary search.
• n of 10⁷ and more: aim for O(n) or better: one pass, hashing, two pointers, or a formula.

The patterns named here each have a module of their own later in this track. Reading the limits first tells you which modules to think about, and which ones you can rule out without trying them.

Measure instead of trusting rules of thumb

A planning figure is a guess about someone else’s computer. When it matters, measure. Here are the two correct solutions of the step-goal streak from the first lesson of this module, timed on their worst case, a streak that covers every day:

# The two correct streak solutions from the first lesson of this module, timed as n grows.
import time


def brute_force(steps, goal):  # start a streak on every day: O(n^2) when the streak is long
    best = 0
    for start in range(len(steps)):
        length = 0
        while start + length < len(steps) and steps[start + length] >= goal:
            length += 1
        best = max(best, length)
    return best


def one_pass(steps, goal):  # O(n)
    best = run = 0
    for count in steps:
        run = run + 1 if count >= goal else 0
        best = max(best, run)
    return best


def best_ms(solution, steps, runs=3):
    """The fastest of a few runs, in milliseconds: slower runs were disturbed by other programs."""
    fastest = float("inf")
    for _ in range(runs):
        start = time.perf_counter()
        solution(steps, 7000)
        fastest = min(fastest, time.perf_counter() - start)
    return fastest * 1000


print("Every day meets the goal, the worst case for the brute force.")
print(f"{'n':>9}  {'brute force':>12}  {'one pass':>10}")
brute_ms = {}
for n in [500, 1_000, 2_000, 100_000]:
    steps = [9000] * n
    if n <= 2_000:  # beyond that the brute force takes too long to wait for
        brute_ms[n] = best_ms(brute_force, steps)
    brute = f"{brute_ms[n]:9.1f} ms" if n in brute_ms else f"{'(skipped)':>12}"
    print(f"{n:>9,}  {brute}  {best_ms(one_pass, steps):7.2f} ms")
estimate = brute_ms[2_000] * (100_000 / 2_000) ** 2 / 1000  # O(n^2): 50 times the n, 2,500 times the time
print(f"Estimated brute force at n = 100,000: about {estimate:,.0f} s, against a 10 s limit for Python.")

Every day meets the goal, the worst case for the brute force.
        n   brute force    one pass
      500        7.5 ms     0.02 ms
    1,000       33.2 ms     0.05 ms
    2,000      146.9 ms     0.10 ms
  100,000     (skipped)     6.28 ms
Estimated brute force at n = 100,000: about 367 s, against a 10 s limit for Python.

Your numbers will differ from the recorded ones, and from run to run, but the shape should be the same. If one row looks out of line, run it again: other programs on the computer disturb short timings.

• Doubling n roughly quadruples the brute force’s time, because it is O(n²) on this input. The one-pass version roughly doubles, as O(n) should.
• The estimate for n = 100,000 is minutes, against HackerRank’s 10-second limit for Python. Even a limit ten times as long would not be enough.
• The one-pass version handles 100,000 days in a few milliseconds in CPython, so in Python the language was never the problem; the algorithm was.

Two habits come from this. First, choose the complexity class before you worry about the language: no time limit makes up for a class that is too slow. Second, before you submit in an online assessment, build the largest input the limits allow (here, 100,000 days that all meet the goal) and time your own solution on it. Sample tests are usually small, so they seldom tell you that a solution is too slow.

The time limit is per language on some platforms. HackerRank’s environment page lists 10 seconds for Python, 4 for Java and Go, and 2 for C and C++. A longer limit does not make an interpreted loop as fast as compiled code, so for loop-heavy plans in Python, budget with the smaller Python figure.

Clues hidden in the limits

Besides the size, other limits point at a technique. None of these is a rule, but each is worth a second look:

The overflow line is easy to check: a Java int holds values up to 2,147,483,647, according to the Java Language Specification, far below 2 × 10¹⁴. The last line hides a classic slip. If each of 10⁴ test cases clears an array of 10⁶ counters, the clearing alone costs 10¹⁰ steps, though every test case is small; clear only what the test case used.

Key takeaways

• Read the constraints block before the story: the largest size, the time limit, then the other numbers.
• Multiply the time limit by your language’s rate (planning figures: about 10⁸ simple steps a second compiled, 10⁷ in CPython) and compare each idea’s step count with that budget.
• Sizes map to targets: about 20 means exponential is allowed, a few thousand means O(n²), 10⁵ and up means O(n log n) or better.
• Limits on values, queries, counts and test cases each hint at a technique, and at a trap.
• Measure on the largest input the limits allow. The complexity class decides far more than the language does.