What you will be able to do#
- Use a repeatable reasoning chain from representation to a defended invariant.
- Distinguish techniques that share vocabulary but require different constraint proofs.
- Test recognition with counterexamples and changed contexts rather than reproduction alone.
Move from story to invariant#
Begin with what one input item means and what part of the processed input can affect the future. Name the repeated work in a correct simple approach. A candidate technique is useful only when its preconditions hold; state the invariant, then try to break it with the smallest counterexample.
- Representation: define values, indices, identity, boundaries, and mutation rules.
- Repeated work: identify the lookup, scan, recomputation, or branching done again.
- Candidate technique: choose a structure or traversal that could retain the needed state.
- Applicability proof: connect input constraints to the safe update or discard rule.
- Invariant: state what remains true after every step.
- Counterexample: find the smallest input that would violate an unstated assumption.
Two pointers or a hash map?#
Two pointers need an order or boundary relationship that proves one move cannot discard a valid answer. A hash map is appropriate when the future needs direct membership, counts, or a complement from the processed prefix. The phrase 'find a pair' is not enough to choose either one.
For a sorted pair sum, pointer movement can discard one boundary. For an unsorted one-pass pair sum that must return original indices, a map can preserve values to indices without sorting away position information.
Sliding window or signed prefix counts?#
A variable sliding window works when moving a boundary repairs feasibility monotonically. Positive values can provide that relationship for a minimum-length sum-at-least target task. Arbitrary signed values break it: removing a negative value can increase the sum, and extending the window can decrease it.
For exact signed range totals, store counts of earlier prefix sums and look up currentPrefix minus target. The map represents earlier boundaries, so count before updating with the current boundary.
Greedy or dynamic programming?#
A greedy choice must come with an exchange argument or invariant showing that the commitment never needs revision. Dynamic programming is appropriate when choices create overlapping future states and the best answer for a state can be assembled from already solved smaller states.
The words 'minimum' and 'maximum' do not prove greedy. Denominations 1, 3, and 4 with amount 6 reject the rule 'take the largest coin first': it uses 4+1+1 instead of 3+3.
BFS or weighted shortest path?#
BFS discovers minimum edge count when every traversed move has the same cost. With nonnegative unequal weights, queue layers no longer represent total cost; a relaxation algorithm such as Dijkstra with a priority queue may be required. Negative edges require a different contract again.
Same wording, different constraint#
Use pairs like these to make the applicability proof visible before naming a pattern.
- Contiguous sum with positive values and an at-least target can support a shrinking window; exact sum with signed values needs prefix-state reasoning.
- Find a pair in sorted input can support two pointers; return original indices from unsorted input often favors a value-to-index map.
- Reach a target through unit-cost moves supports BFS; reach it through unequal nonnegative costs requires weighted relaxation.
- Choose nonoverlapping intervals to maximize count may support an earliest-finish greedy proof; choose intervals for maximum total value requires state and often dynamic programming.
Different story, same invariant#
A longest substring with at most two character classes and a longest telemetry interval with at most two event categories have different stories. Both can maintain a contiguous window whose frequency state matches exactly the active range, expanding right and shrinking left until at most two normalized categories remain.
Transfer is the ability to recognize and defend that shared invariant without needing the original story or title.
Worked example#
Why the window proof fails on signed values
Find a contiguous range with an exact target sum. Compare nonnegative input with arbitrary signed input.
- With nonnegative values, growing the right boundary cannot decrease the sum and shrinking the left boundary cannot increase it.
- With signed values, either direction can raise or lower the sum, so a local repair rule can skip a valid range.
- Represent every range as currentPrefix minus an earlier prefix and look up the needed earlier total.
Outcome: The valid alternative is a prefix-sum frequency map, not a sliding window chosen from the word 'contiguous.'
Apply the idea#
Compare finding a contiguous sum in nonnegative values with finding an exact contiguous sum in arbitrary signed values. Which assumption can fail, and what valid alternative follows?
Reveal the worked answer
The monotonic boundary assumption fails with signed values: extending a range can reduce its sum and removing a left value can increase it. A window cannot safely decide which boundary to move. Use prefix sums and a map of earlier prefix counts; at each boundary, count earlier totals equal to currentPrefix minus target before recording the current prefix.
Choose the next session#
Choose one pattern, state its invariant and anti-clues before opening a matching question, then test a changed-constraint counterexample.
Open the pattern indexSource and review record#
This original Engineering Foundry guide was checked by Codex against the recorded research scope on 2026-09-05. It has not received independent human editorial review.
Evidence IDs: SRC-DSA-ALGOMONSTER-ROADMAP