Brute Force Before Optimization

What you will be able to do#

• State a correct baseline without spending the entire round implementing it.
• Identify repeated work or unnecessary candidates before selecting an optimization.
• Express time and space in relevant variables, including preprocessing, output, recursion, sorting, and library costs.

Start from correctness#

Describe the simplest approach that satisfies the complete contract. State why it is correct and what it costs. This gives you a reference for tests and makes the optimization explainable.

You do not need to code every baseline. When time is limited and the improvement is clear, explain the baseline, identify its bottleneck, confirm the better approach, and implement that approach unless asked otherwise.

Name the work you are removing#

Avoid jumping from 'quadratic' to a memorized pattern. Point to the repeated scan, lookup, sort, path enumeration, or overlapping state. Then define the information that would let later work reuse an earlier result or discard candidates safely.

1. State the baseline and why it covers every valid answer.
2. Count the expensive operation in terms of the relevant input variables.
3. Name the minimum state needed to avoid repeating it.
4. Prove the new update or discard rule.
5. Compare the new time, auxiliary space, mutation, and preprocessing tradeoffs.

Make the complexity claim complete#

Name each input variable when there is more than one. Separate preprocessing from per-query cost. Include output construction, recursion stack, copied slices or substrings, sorting, and the actual standard-library operation used.

Expected or amortized cost is not the same as worst case. Hash lookup is commonly expected O(1); dynamic-array append is amortized O(1); a heap update is O(log n). Nested loops can still be linear when each pointer advances at most n times.

Worked case: repeated range queries#

For q immutable range-sum queries over n values, summing every range independently can take O(nq) in the worst case. Build n+1 prefix boundaries once in O(n), then answer each query as prefix[right + 1] minus prefix[left] in O(1). Total time becomes O(n + q) with O(n) auxiliary storage.

The optimization is justified because the same prefix work is reused across many queries and the input does not change between them.

Countercase: one narrow query#

For one short range query, scanning only that range may be simpler and may touch less memory than building prefixes for the entire input. The asymptotic comparison depends on the range length and whether more queries will arrive.

Optimization is a response to the actual workload, not a ritual performed after every baseline.

Defend two valid approaches#

Present alternatives as contracts: 'For one query, I would scan the requested range with O(k) time and O(1) extra space. For many immutable queries, I would spend O(n) time and space once so each query is O(1).' This is stronger than naming one approach as universally optimal.

Worked example#

Apply the idea#

Defend two approaches for immutable range-sum queries: one when there is a single short query and one when there are many queries. Include preprocessing, query, and space costs.

Choose the next session#

Use the existing interview flow to state a correct baseline, identify its exact bottleneck, and confirm the optimized invariant before coding.

Source and review record#

This original Engineering Foundry guide was checked by Codex against the recorded research scope on 2026-09-05. It has not received independent human editorial review.

Evidence IDs: SRC-DSA-TECH-HANDBOOK-PLAN SRC-DSA-ALGOMONSTER-ROADMAP