The LeetCode Game — How to Read a Problem

Review boundary and corrected contracts

Constraints are a feasibility filter, not a language-independent stopwatch. Count output materialization: enumerating all subsets copies Θ(n·2ⁿ) element references. The small benchmark is illustrative, not a reproduced performance guarantee.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Combine the input/output contract with constraints to estimate work, reject unjustified approaches and propose techniques whose preconditions actually hold.

Series: LeetCode — From Basics to Production-Ready · Session 1 / 65 · Phase 0 · Foundations

Prerequisites: Python functions, loops, lists and basic dictionary lookups. The cost models used here are explained below.

What this session IS — reading the tiny print

A typical problem provides a task, examples and Constraints. Read these together: constraints without the requested output cannot select an algorithm. A constraints block might look like this:

Constraints:
  1 <= n <= 10^5
  -10^9 <= nums[i] <= 10^9

Before coding, identify what n counts and whether the answer is one number, one witness or every solution. The same bound can describe tasks requiring very different work. Constraints help evaluate an approach; they do not reveal a unique intended algorithm.

There is no universal operations-per-second allowance. Estimate the actual operation count, allocation and output size, then compare with the stated constraints and runtime budget. At n=100,000, a full distinct-pair scan considers about five billion pairs; a linear pass or sort-based method is worth investigating before benchmarking.

Real: A map scale helps estimate a route’s distance, but neither selects the destination nor predicts traffic. Input bounds similarly help estimate work without certifying elapsed time.

For n = 100,000, compare a linear pass, roughly 1.66 million n log2(n) units,
and 4,999,950,000 distinct pairs. These are work estimates, not timing promises.
The task and its invariants decide which candidates are correct.

The naive approach and why it is slow

Take "find two numbers in a list that add up to a target". The obvious approach: try every pair.

def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

The displayed loops enumerate n(n−1)/2 distinct pairs. This is Θ(n²), but a bound alone does not certify a timeout at a particular n. Reading constraints first helps identify which growth rates need further justification.

A feasibility table, not a stopwatch

Use explicit counts rather than a universal “acceptable complexity” table. Here are representative worst-case quantities; an elementary iteration, a Python allocation and a recursive call need not cost the same.

A billion input elements requires reading a billion elements in tasks that depend on all of them. A single integer whose value is a billion is a different input. For several test cases, sum their work rather than checking only the largest case. Space and output limits can reject an approach even when its arithmetic count looks manageable.

Derivation, not a magic threshold. In the pair loop, the inner loop lengths are n-1, n-2, ..., 1, whose sum is n(n-1)/2. A doubling subsets construction has 2^n final lists; each of the n elements occurs in half of them, so their total length is n*2^(n-1) for n >= 1. A binary search halves an interval, but checking feasibility might itself scan all n inputs. Big-O hides constants and is an asymptotic upper bound: substituting n into O(n²) does not produce a measured number of seconds.

Conclusion: the contract determines valid techniques; exact or asymptotic work estimates and the environment determine which deserve implementation and measurement.

The template — a reading ritual

Use this reading ritual before implementing a candidate:

1. State the required output and whether mutation is permitted.
2. Identify every size parameter, value range and total-test-case bound.
3. Check assumptions: sortedness, uniqueness, nonnegative values, graph weights.
4. Derive a brute-force baseline and count its work and output storage.
5. Propose an improvement, explain its invariant, and estimate its cost.
6. Test correctness, then measure representative cases if runtime is uncertain.

For example: “At 100,000 elements the pair scan can visit nearly five billion pairs. I will investigate an expected-linear complement map, using additional storage, and verify that its one-pass invariant returns distinct indices.” This explains a decision without asserting a universal timeout or an interview-scoring rule.

The budget line mental model: as size grows, expensive candidates need stronger justification. Small n does not make every exponential or factorial method feasible. Negative numbers invalidate the usual sum-threshold shrinking-window proof, but not every sliding-window algorithm: a fixed-size sum works with negatives. An O(log n) requirement likewise does not prove that an arbitrary predicate is monotone.

Trigger this ritual when opening a problem or when a constraint changes; the objective is understanding the whole contract, not winning a race to its smallest print.

Memory technique — the powers-of-ten peg

Remember three comparisons rather than hard acceptance thresholds:

• Twenty: subsets are not permutations. 2^20 is about one million, but 20! is about 2.43 × 10¹⁸. Even subset enumeration can be too large when every result is copied or every state does substantial work.
• Hundred-thousand: count the pairs. About five billion unordered pairs versus about 1.66 million n log2(n) units is a reason to seek better growth, not proof that a particular library call meets a time limit.
• Million: count passes and storage. Two or ten full passes are still O(n). A million Python objects can occupy much more memory than a million packed bytes.

Misconception: constraints alone determine the solution. They constrain feasibility, while the output and invariants determine correctness. The same n can accompany summing a list, sorting it or emitting all pairs; their output requirements differ.

Test: choose a bound, then invent two tasks with that bound but different output sizes. Explain why a method for one need not solve the other. Reading the entire problem carefully is compatible with checking feasibility early.

What reviewers actually ask

The following are practice choices, not measured employer frequencies or a scoring rubric. Read each linked statement for its current contract:

• Two Sum (1) · Practice selection. (Easy) — probes: can you replace the quadratic baseline with a complement map while retaining distinct indices. Follow-up: "what if the array were sorted?" (drops you into two-pointers, L07).
• Best Time to Buy and Sell Stock (121) · Practice selection. (Easy) — probes: a large price history motivates replacing all buy/sell pairs with a running minimum that only uses earlier days. Follow-up: "with multiple transactions?"
• Search in Rotated Sorted Array (33) · Practice selection. (Medium) — probes: the problem says O(log n) is expected; a full linear scan would not satisfy that asymptotic requirement; sorted-half reasoning supports binary search. Follow-up: "with duplicates" (81).
• Subsets (78) · Practice selection. (Medium) — probes: requesting every subset requires exponential output; either iterative doubling or backtracking can generate it. Follow-up: "with duplicates" (90).
• Koko Eating Bananas (875) · Practice selection. (Medium) — probes: huge value range for the answer with small n signals binary search on the answer, not on the array. Follow-up: "minimise something else under a budget."
• Median of Two Sorted Arrays (4) · Practice selection. (Hard) — probes: the problem states O(log(m+n)); a full merge would not meet that asymptotic target; partition search is one suitable approach.

Worked example 1 — reading n to pick the tool

Problem in plain words: Given a list nums and a target, return the indices of two numbers that add to target. For this example, 2 <= n <= 10^4 and bounded integer values; return any pair of distinct indices, or [] when no pair exists.

Brute-force budget. There are n(n−1)/2 distinct pairs, so at n=10,000 there are 49,995,000 comparisons in the worst case. Whether that is acceptable depends on the runtime and time budget; the hash approach avoids this growth.

The insight. Before processing index i, the map contains only earlier indices. Testing for the complement before storing x prevents reusing the same element. If a solution ends at i, its earlier value is in the map; repeated values work too, as [3, 3] with target 6 shows.

def two_sum(nums, target):
    seen = {}                      # value -> index we saw it at
    for i, x in enumerate(nums):   # one pass, O(n)
        need = target - x          # the complement that would complete the pair
        if need in seen:           # dict lookup is O(1) average
            return [seen[need], i]
        seen[x] = i                # remember x for a future partner
    return []

Complexity. Expected O(n) time under ordinary constant-cost integer hashing and expected O(1) dictionary operations; pathological collisions can make total work O(n²). Space O(n). This is a time–space trade, not a worst-case constant-time guarantee for arbitrary keys.

Follow-up they escalate to. "What if the array were already sorted — can you do it in O(1) extra space?" That drops the map for two converging pointers, which is exactly L07.

Bounded experiment: use a deterministic no-solution input so early return does not hide the full pair scan. Run after the two function definitions above.

from timeit import repeat
 
for n in (100, 200, 400):
    nums = list(range(n))
    target = -1  # no two nonnegative values can reach it
    assert two_sum_brute(nums, target) == two_sum(nums, target) == []
    print("n", n, "pairs", n * (n - 1) // 2)
    for fn in (two_sum_brute, two_sum):
        samples = repeat(lambda: fn(nums, target), number=3, repeat=3)
        print(fn.__name__, "best seconds/call", min(samples) / 3)

The pair counts are 4,950, 19,900 and 79,800. They approximately quadruple when n doubles; the map visits twice as many elements. Timings are local observations affected by interpreter, machine, load and allocation. timeit normally disables cyclic garbage collection during measurement. No fixed speed ratio or judge result follows from this demonstration.

Worked example 2 — a tiny n inviting exponential work

Problem in plain words: Return every subset of a list of up to 10 distinct numbers. Constraints: n <= 10.

Reading the output. For n = 10, the answer has 1,024 subsets. Exponential output is inherent in the request; it is not a flaw that an algorithm generating it takes exponential time. The distinct-values assumption matters because the construction below does not deduplicate equal-value subsets.

def subsets(nums):
    result = [[]]                  # start with the empty subset
    for x in nums:                 # for each number...
        # ...double the collection: every existing subset, plus a copy that includes x
        result += [subset + [x] for subset in result]
    return result
 
# subsets([1,2,3]) -> [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

Invariant and cost. After the first i values, result contains exactly all subsets of that prefix. Each subset of the next prefix either excludes x (an existing list) or includes x (one newly concatenated list), and these cases are disjoint for distinct values. The comprehension finishes before += extends result. For n >= 1, there are exactly n*2^(n-1) stored element references, plus 2^n list objects: Θ(n·2^n) time and output space. At n = 10, this is 5,120 references across 1,024 lists. The empty input returns [[]]. These counts explain growth without promising instantaneous execution.

Follow-up. "What if the list has duplicates and you must not repeat subsets?" → sort first, skip a value when it equals the previous one at the same depth (Subsets II, 90).

Worked example 3 — the answer's range, not n, sets the budget

Problem in plain words: Koko eats bananas from piles; she eats k bananas/hour from one pile. Find the smallest k that finishes all piles within h hours. This example requires a nonempty list of positive integer piles, each at most 10^9, with len(piles) <= h and at most 10^4 piles. She cannot start a second pile in the same hour. If h < len(piles), no speed is feasible; that input is outside this function’s contract.

Why binary search applies. At positive speed k, a pile of size p needs ceil(p/k) hours, computed exactly by (p+k-1)//k. Increasing k cannot increase any pile’s hours, so feasibility is monotone. Speed max(piles) is feasible because it needs one hour per pile. Thus the interval initially contains a feasible speed and its minimum; testing a feasible midpoint keeps it as the upper bound, otherwise every speed at or below it is rejected. A large value range motivates the search, but this monotonicity and feasible bound justify it.

def min_eating_speed(piles, h):
    def hours_at(speed):                       # hours needed if she eats `speed`/hr
        return sum(((p + speed - 1) // speed) for p in piles)
 
    lo, hi = 1, max(piles)                      # speed is between 1 and the biggest pile
    while lo < hi:                              # binary search for the smallest feasible speed
        mid = (lo + hi) // 2
        if hours_at(mid) <= h:                  # mid is fast enough → try slower (fewer bananas/hr)
            hi = mid
        else:                                   # too slow → must eat faster
            lo = mid + 1
    return lo                                    # lo == hi == smallest feasible speed

Complexity. With M = max(piles), O(n·(1 + log M)) time and O(1) auxiliary space under bounded-integer arithmetic. The initial max scans the input even when M = 1; up to about 30 predicate checks suffice when M <= 10^9. Larger arbitrary-precision integers add bit-operation costs.

Follow-up. "Ship packages within D days (1011)" and "Split array largest sum (410)" are the same binary-search-on-answer shape.

Decision: Should I optimise for the constraint's budget, or just write the clearest brute force?

Name: Choose a justified feasible candidate

Gain: Makes growth, memory and assumptions explicit before implementation; passing still requires correct code and adequate resources.

Cost: More thinking up front before any code.

Pick: A baseline has prohibitive estimated work or the statement requires a tighter asymptotic bound.

Name: Write brute force first, optimise if needed

Gain: Fast to a correct answer; good for verifying with tests.

Cost: Can require too much work at the maximum input; avoid treating small-test success as evidence of scalability.

Pick: The actual operation count is small enough, or a bounded brute-force oracle will help verify a faster method.

Name: Over-optimise beyond the budget

Gain: Feels impressive.

Cost: Extra bugs and time for speed the constraints never asked for.

Pick: Only when a measured bottleneck or explicit requirement justifies the added complexity.

Verdict: Read the budget, state it, then aim for the simplest algorithm that fits it. Brute force is a fine opening move only when you say why and when you will replace it.

Where this shows up in production

Sizing also matters outside practice problems. A scan over a few dozen configuration keys may be simpler than an index. Repeated lookups over millions of rows may justify indexing, but selectivity, update rate, caching, memory and latency targets also matter. Size informs the decision rather than choosing the structure by itself.

You can now…

• Separate input length, numeric magnitude, test-case totals and output size.
• Derive pair, subset and halving counts instead of memorizing a stopwatch table.
• State a brute-force baseline, then explain an improvement’s invariant and cost.
• Explain why small n can permit subsets without permitting permutations.
• Distinguish an explicit asymptotic requirement from a guessed elapsed-time limit.

Self-check (answer follows each question).

Recall check

Q: For n = 100,000, how much work can the distinct-pair scan perform?

A: n(n-1)/2 = 4,999,950,000 pair tests. Investigate better growth if the contract permits it; the count alone is not a universal timeout proof.

Q: Does n <= 20 make both subset and permutation enumeration inexpensive?

A: No. 2^20 = 1,048,576, whereas 20! = 2,432,902,008,176,640,000. Include result-copying and per-state work too.

Q: How many Python operations fit into a second?

A: There is no portable fixed allowance. The operation, interpreter, data, allocation and hardware matter; measure representative work after checking correctness.

Q: A value can be 10^9 and the task asks for the smallest feasible k. What must be proved before binary searching?

A: Feasibility is monotone in k, the initial interval contains a feasible answer, and its predicate is correct. For Koko, per-pile hour counts never increase as speed increases.

Q: Why state the target complexity before coding?

A: It exposes cost assumptions and alternatives. It neither substitutes for a correctness argument nor proves an interview score or eventual runtime.

Q: A statement requires O(log n). Does that force binary search?

A: It excludes a full Θ(n) scan in that cost model, but does not uniquely name an algorithm. Binary search needs an ordered search space or monotone predicate. Include any preprocessing cost rather than hiding it.

Practice queue

For each, read the required output and constraints, propose a baseline, then justify a candidate improvement. The +7d/+21d labels below are optional elapsed-day review suggestions, not validated learning intervals.

• Two Sum (1) — Easy · your first constraint read. (spaced-repeat anchor: +7d)
• Best Time to Buy and Sell Stock (121) — Easy · compare pair enumeration with a running minimum.
• Contains Duplicate (217) — Easy · budget invites a set.
• Subsets (78) — Medium · tiny n invites 2^n.
• Search in Rotated Sorted Array (33) — Medium · problem states O(log n).
• Koko Eating Bananas (875) — Medium · answer range sets budget. (spaced-repeat anchor: +21d)
• Capacity To Ship Packages Within D Days (1011) — Medium · same shape as Koko.
• Median of Two Sorted Arrays (4) — Hard · the statement mandates O(log(m+n)).

Next session (L02) turns the budget table into a skill you can derive instead of memorise: counting the real cost of Python's built-in operations, so "n log n" stops being a guess.

Corrective source notes

• Python 3.14 timeit documentation — callable timings, repeat/number semantics and the default garbage-collection boundary; checked 2026-10-09.
• Pair and subset counts and the Koko monotonicity argument are derived above. They do not establish a portable throughput guarantee.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.