Recap: Solving an Unseen Problem

Solving an unseen problem means taking the same six steps in the same order, so the work starts from questions rather than from code.

1. Clarify the input, the output and the limits: the size, the range and sign of the values, duplicates, the empty input, and the form of the answer.
2. Work two examples by hand, one of them an edge case, and keep their answers as tests.
3. State the brute force and its cost.
4. Find the bottleneck, the part that dominates the cost, and choose an approach that removes it within the budget.
5. Write the code.
6. Trace the examples through it, and go back to step 4 or 5 when an answer disagrees.

The limits set the budget. At roughly 10⁸ simple steps a second, the largest input decides the slowest complexity that fits, and every row is a rough guide: a solution at the edge of one is a reason to choose the faster complexity, not to measure.

Two traps undo the sequence. Skipping step 1 lets an unchosen assumption into the code, such as a maximum that starts at 0 on readings that can be negative, or an empty input nobody decided how to answer. Skipping step 3 on small limits hides the fact that the brute force already fits: at 20 items or fewer, trying every subset is often the answer. Most later topics in this subject are step 4's moves, each removing one kind of bottleneck, and the hash map, which turns a search inside a loop into one lookup, is the first of them.