Foundations
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.
Why it works
4. Find the repeated work
This is the actual skill. Look at the brute force and find the thing it computes more than once, then ask what you could remember so that it only gets computed once.
Nearly every pattern in this course is one answer to that question. A hash map remembers what you have already seen. A prefix sum remembers a running total so you never re-add a range. A monotonic stack remembers candidates that can still be the answer. Memoization remembers a subproblem's result. Two pointers remember that a whole region has already been ruled out.
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.
Tip
When you are properly stuck
Try these in order before asking for a hint. Solve a smaller version, say n equals 3, exactly. Solve a version with a constraint removed, then add it back. Ask whether sorting the input would help, since it costs O(n log n) and often collapses the problem. Ask what you would need to know at position i to answer instantly, then work out how to have it.
If twenty minutes of that produces nothing, take the nudge. Being stuck productively is the goal; being stuck indefinitely is not.
Why it works
7. After it passes, do not move on yet
This is the step that separates people who finish 150 problems from people who can solve problems. Close the editor and answer three questions. What is the one sentence that makes this work? What would I have needed to notice to find it myself? What other problem does this remind me of?
Two minutes. Skipping it is why the second encounter with a problem feels exactly like the first.
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?
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.
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 the tests when you are ready.