The solving loop

Most people attack a problem by trying to recall a similar one. That works when you have seen it and fails silently when you have not — you spend fifteen minutes hunting for a memory instead of five minutes deriving an answer.

The loop below derives instead of recalls. It is slower on the problems you already know and far faster on the ones you do not, and it is what an interviewer is actually watching for.

The five-step solving loop, and the arrow back from the pattern to the waste100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

1 · Restate it in one sentence

In your own words, with the input and the output named. "Given a list of daily prices, return the largest profit from one buy and one later sell." If you cannot compress it to a sentence, you have missed a constraint.

Then get the numbers. What is the size of the input? At n ≤ 20 a brute force over subsets is fine; at n = 10⁵ you need roughly O(n log n); at n = 10⁹ you are not iterating at all. The constraint tells you the target complexity, and the target complexity narrows the pattern before you have had a single idea.

2 · Write the brute force

Not to submit it — to have something concrete to attack. Try every pair, try every subset, simulate every step. State its complexity.

This step feels like a waste of time and is the opposite. A brute force is a correct reference: when your clever version disagrees with it on a random input, the clever version is wrong. It is also the thing step 3 operates on.

3 · Find the waste

Look at what the brute force recomputes, and name it. This is the whole game, and almost every pattern in this course is an answer to one specific kind of waste:

The brute force is…	The waste	The pattern
checking every candidate answer	most candidates are ruled out by one test	binary search on the answer
re-scanning a window each step	the window barely changed	sliding window
re-summing a range	prefix sums are recomputed	prefix arrays, hash maps
re-solving the same subproblem	identical calls repeat	memoisation, DP
scanning for the maximum repeatedly	the order is rebuilt each time	heap
re-searching a sorted structure	position is already known	two pointers

Say the waste in a sentence — "I recompute the sum of a window that only lost one element and gained one" — and the pattern usually names itself.

4 · Choose the pattern, and check its precondition

Every pattern has a condition that makes it legal, and skipping the check is the single most common way a confident answer turns out to be wrong:

• Binary search needs a monotone predicate: once it flips, it stays flipped.
• Two pointers need an ordering that makes moving one side provably safe.
• Greedy needs an exchange argument: swapping in the greedy choice never makes the answer worse.
• DP needs optimal substructure: the best answer is built from best answers to subproblems.

Say the precondition aloud. If it does not hold, you have the wrong tool, and the twenty lines you were about to write would have been wasted.

5 · Test the edges before you claim it works

Run the examples in your head, then run the edges you know break code:

• empty input, and a single element
• all elements equal
• the answer at the very first or very last position
• the largest value the constraints allow, for overflow and for time

Every solution in this course ships with its test cases visible for the same reason: a claim you cannot see the evidence for is not a claim.

In an interview

Narrate the loop. An interviewer cannot grade silence, and the loop gives you something to say at every moment: "Let me restate that… brute force would be O(n²) because… the waste is that I re-scan… so I want binary search, which is legal here because the predicate is monotone in x."

That transcript is close to a perfect score even before the code, because it demonstrates the two things being measured: that you can get to an answer without luck, and that you know why the answer is correct.

The mistake that loses points: jumping to a named pattern in the first thirty seconds. When it fits, you saved five minutes. When it does not, you have committed publicly to the wrong tool and the recovery costs more than the loop would have.

Check yourself

n ≤ 20 and the problem asks for the best subset. What complexity are you aiming for, and what does that tell you?

2²⁰ is about a million — exponential is fine. The tiny constraint is a deliberate signal that you are meant to enumerate subsets, usually with recursion or a bitmask.

Your brute force is O(n²) because for each element you scan everything to its left for the largest value. Name the waste, then the fix.

The waste is rescanning a prefix whose maximum you already computed. Carry the running maximum as you go: one pass, O(n).

You have a greedy idea that passes both examples. What do you owe the interviewer before you write it?

The exchange argument — why swapping the greedy choice into any optimal solution never makes it worse. Without it, "it passes the examples" is a coincidence you have not distinguished from a proof.