How to attack a problem you have never seen

A repeatable procedure for the first ten minutes, which is where most attempts are won or lost.

The failure this prevents

The usual way an attempt dies is that you read the problem, feel nothing, stare for a bit, then go look at the solution. Nothing was learned because nothing was attempted. The procedure below exists to guarantee you always have a next move.

1. Restate it in your own words

Say what the input is, what the output is, and what makes an output correct. If you cannot do this, you have not understood the problem yet and everything after it is guesswork. This takes thirty seconds and catches a real misreading maybe one time in five.

2. Do a small example by hand

Take an input with four or five elements and produce the answer manually, on paper or in a comment. Watch what you actually do. You are not looking for the algorithm yet, you are looking for what information you found yourself wanting.

This step is where most insights come from, and it is the step people skip. Working an example by hand exposes the question you keep asking yourself, and that question is nearly always what the efficient algorithm is built around. You cannot notice it while staring at the problem statement.

3. Write the brute force, at least in your head

Say out loud what the obvious, slow, definitely-correct approach is, and what it costs. Check every pair. Try every subset. Recompute from scratch each time.

This is worth doing even when it is far too slow, for three reasons. It gives you a correctness baseline. It gives you something to say if you run out of time. And the efficient solution is almost always the brute force with one specific piece of repeated work removed.

5. Check the edges before you code

Empty input. One element. All elements identical. Negative numbers. The target at the very start or very end. Duplicates where the problem is about distinct values.

Thirty seconds here saves a failed submission. It also tells you things about the problem: noticing that duplicates need special handling in 3sum is most of what makes 3sum harder than two-sum.

6. Now write it

Say the invariant before you write the loop. What is true every time around? For a two-pointer scan it might be everything outside the range from left to right has been ruled out. For a window it might be the window from left to right always satisfies the condition. If you can state that sentence, the loop body writes itself and the boundary conditions stop being guesswork.

Quick check· 5 min

Choose the next move

You need the number of distinct values in every window of size k across an array. Your brute force builds a set for each window from scratch, which is O(n * k). You have restated the problem and worked a small example by hand. What is the most productive next step?

Start coding the brute force; optimize later if there is timeIdentify what the brute force recomputes: consecutive windows overlap in k - 1 elements, so ask what could be carried from one window to the nextLook up which pattern this problem belongs toSort the array first so that equal values sit together

Code lab· 16 min

Brute force, then better

Both functions answer the same question: across a sequence of readings, what is the largest drop from an earlier reading to a later one? That is the largest nums[i] - nums[j] where j > i, or 0 if the sequence never goes down. Write max_drop_slow the obvious way with two loops, then write max_drop_fast in a single pass. Getting both to agree on every case is the point.

solution.py

Tests

cases = [[7, 1, 5, 3, 6, 4], [9, 4, 7, 2], [1, 2, 3], [], [5]]for case in cases:    print(max_drop_slow(case), max_drop_fast(case))

Output

Run tests to see output.

2. Do a small example by hand

3. Write the brute force, at least in your head

Say out loud what the obvious, slow, definitely-correct approach is, and what it costs. Check every pair. Try every subset. Recompute from scratch each time.

5. Check the edges before you code

Empty input. One element. All elements identical. Negative numbers. The target at the very start or very end. Duplicates where the problem is about distinct values.

Thirty seconds here saves a failed submission. It also tells you things about the problem: noticing that duplicates need special handling in 3sum is most of what makes 3sum harder than two-sum.

6. Now write it