Problem-Solving Patterns
The cues in a problem statement that point at a technique, and the check that confirms the technique fits.
Frequency Map: First value seen before
A pattern here is a pairing: a shape that questions keep taking, and the technique that fits it. A contiguous subarray of length k points at a sliding window. Many range sums over an array that never changes points at a prefix sum. Next greater element points at a monotonic stack, dependency order points at a topological sort. The techniques themselves live in their own categories. What this group adds is the recognition step.
Every cue comes with a condition to test before committing. A sliding window needs the running answer to be repairable when one element leaves and another arrives. Binary search on the answer needs feasibility to be monotonic, so that if x works then everything past x works too. Two pointers needs a rule under which neither index ever has to move back. Skip the condition and you write code that passes the samples and fails on the case the condition would have ruled out.
The payoff is nearly always a nested loop collapsed into a single pass, or an exponent halved. A frequency map turns 'have I seen this' from a scan into a lookup. A difference array turns m range updates plus one read from m * n into m + n. Meet in the middle enumerates two halves at 2^(n/2) rather than one space at 2^n. None of it is new machinery, and all of it depends on noticing which cue is in front of you.
After this you can
- Map a question's wording onto a candidate technique in a few seconds
- State the condition a pattern requires and test it against the problem before writing code
- Choose between two plausible patterns by what the data allows: sorted, static, small n
- Read the constraints as a hint about which complexities are still on the table
- Recognise when no pattern applies and brute force is the honest starting point
In this order
Also in this category
Where people go wrong
Matching the wording instead of the structure
The word subarray suggests a sliding window, but a window only works while the running answer can be repaired in O(1) as elements enter and leave. With negative numbers and a sum-at-least-k target, shrinking the window is no longer safe and the pattern does not apply.
Binary searching an answer that is not monotonic
The search needs feasible(x) to be false up to a threshold and true from there on. If a larger x can fail where a smaller one succeeded, each probe steers into the wrong half and you get a plausible wrong number rather than an error.
Choosing a pattern before reading the constraints
n up to 20 says subsets or a bitmask. n up to 10^5 rules out anything quadratic. Values up to 10^9 rule out any table indexed by value. The constraints narrow the candidates faster than the prose does.